Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Válogatott fejezetek az algoritmusok köréből 1

    A tantárgy angol neve: Selected Topics in Algorithms 1

    Adatlap utolsó módosítása: 2006. július 1.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    Villamosmérnöki Szak

    Műszaki Informatika Szak

    Választható tárgy

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    TE915029 őszi 2/0/0/v 3 1/1
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Rónyai Lajos

    tanszékvezető egyetemi tanár

    Algebra Tanszék

    5. A tantárgy az alábbi témakörök ismeretére épít

    Algoritmusok elmélete, diszkrét matematika

    6. Előtanulmányi rend
    Kötelező:
    TárgyEredmény( "BMEVIMA2207" , "jegy" , _ ) >= 2

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

    Ajánlott:

    Tematikaütközés miatt a tárgyat csak azok vehetik fel, akik korábban nem hallgatták a következő tárgyakat:

    7. A tantárgy célkitűzése

    A hallgatók megismertetése néhány modern algoritmustervezési technikával, hatékony algoritmussal.

    8. A tantárgy részletes tematikája

    Ahogy a tárgy címe is sugallja, válogatást szeretnénk nyújtani a rendkívül gazdag, a számítástudomány élvonalába tartozó ismeretkörből. Az anyag összeállításánál figyelembe vesszük a mindenkori hallgatóink kéréseit is.

    Törzsanyag: mintaillesztés szövegben (Knut-Morris-Pratt-, Boyer-Moore-, Rabin-Karp–algo-ritmusok). Sorozatillesztés betűnként (általános módszerek, Ukkonen-algoritmus). Sorozat-illesztés általános hézagmodellel, többszörös illesztés. A szöveg-indexelés alapjai: invertálás, lenyomatok, vektorteres indexelők, az LSI-technika. Randomizált algoritmusok: Schwartz-Zippel és alkalmazásai, egzisztencia-bizonyítások (Erdős-módszer), az IP-nyelvosztály, Karger-Klein-Tarján–algoritmus feszítőfa keresésre. A kommunikációs bonyolultság elemei.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    (előadás, gyakorlat, laboratórium):

    előadás

    10. Követelmények

    a. A szorgalmi időszakban:

    b. A vizsgaidőszakban: vizsga

    1. Elővizsga: lehetséges
    11. Pótlási lehetőségek

    vizsgák pótlásának ált. szab. szerint

    12. Konzultációs lehetőségek

    az előadókkal egyeztetett formában

    13. Jegyzet, tankönyv, felhasználható irodalom
    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

    (a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra):

    Kontakt óra

    30

    Félévközi készülés órákra

    15

    Felkészülés zárthelyire

    Házi feladat elkészítése

    Kijelölt írásos tananyag elsajátítása

    ..

    Vizsgafelkészülés

    45

    Összesen

    90

    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Rónyai Lajos

    tansz. vez. egy. tan.

    Algebra Tanszék