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ó    

    Algoritmusok és bonyolultságuk

    A tantárgy angol neve: Algorithms and Complexity

    Adatlap utolsó módosítása: 2018. július 24.

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

    Matematikus szak, MSc képzés

    Diszkrét matematika blokk

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZM031 4 3/1/0/f 5  
    3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin,
    A tantárgy tanszéki weboldala http://cs.bme.hu/algbony
    4. A tantárgy előadója Dr. Friedl Katalin egyetemi docens
    5. A tantárgy az alábbi témakörök ismeretére épít

    Alapvető algoritmikus technikák

    6. Előtanulmányi rend
    Kötelező:
    NEM ( TárgyTeljesítve("BMEVISZM143") )

    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:
    Ezt a tárgyat nem vehetik fel, akik a VISZM143 kódú “ Algoritmusok és bonyolultságuk – informatikusoknak” című tárgyat teljesítették.
    7. A tantárgy célkitűzése

    A tantárgy célja az algoritmikus gondolkodás továbbfejlesztése, a BSc-hez képest további módszerek, technikák megismerése. A hallgatók betekintést kapnak a témakör modern irányzataiba, az új és jövőbeli eszközök (párhuzamos számítások, kvantumszámítógépek) által megoldható kérdésekre, felvetett problémákra.

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

    • A kódoláselmélet algoritmikus kérdései
    • Geometriai algoritmusok (legközelebbi pontpár, konvex burok meghatározása)
    • Párhuzamos algoritmusok (PRAM modellek, egyszerű függvények kiszámítása az eltérő modellekben, Brent-elv, párhuzamos rendezés, prefix számítások)
    • Elosztott algoritmusok (a vezetőválasztás algoritmusai, egyezségre jutás, illetve ennek lehetetlensége különböző típusú hibák esetén: vonalhiba, leállási hiba, bizánci hiba)
    • Interaktív bizonyítások (az NP kiterjesztése interaktív algoritmusok segítségével, interakció egy erős és egy gyenge fél között, az AM és az IP nyelvosztály, jellemző példák, IP=PSPACE, a PCP elmélet kapcsolata a közel optimális megoldás megtalálhatóságával)
    • On-line algoritmusok (modell, hatékonyság mérése, listaelérési feladat, ütemezési problémák)
    • Paraméteres bonyolultság (NP-nehéz, de paraméteresen megoldható feladatok, korlátos mélységű keresőfák, a gráfminor tétel és következményei, W[1]-teljesség)
    • A kvantumalgoritmusok alapjai (számítási modell, lépés mint unitér transzformáció, illetve vetítés, no-cloning tétel, egyszerű algoritmusok, prímfaktorizáció, keresés, kvantumszámítás és titkosítás)

    A gyakorlaton az előadás anyagához kapcsolódó feladatokat oldunk meg, melyek az ismertetett algoritmusok, módszerek jobb megértését teszik lehetővé és rávilágítanak bizonyos alkalmazási lehetőségekre.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) előadás + gyakorlat
    10. Követelmények

    • Szorgalmi időszakban:  5 kiszárthelyi (10-15 perces) és  1  zárthelyi dolgozat. A 3 legjobb kis zh adja a jegy 40%-át, a zárthelyi dolgozat a 60%-át.

    • Vizsgaidőszakban: -

    11. Pótlási lehetőségek

    A kis zh-k nem pótolhatóak.

    A zárthelyi dolgozathoz egy pótlási lehetőség lesz  a  szorgalmi időszakban és egy  a pótlási héten.

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

    Előzetes egyeztetés szerint.

    13. Jegyzet, tankönyv, felhasználható irodalom T. Corman, C. Leiserson, R. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, 2003.
    H. Attiya: Distributed Computing (lecture notes)
     J. Flum, M. Grohe: Parameterized Complexity Theory, Springer 2006.
    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra56
    Félévközi készülés órákra44
    Felkészülés zárthelyire50
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés 
    Összesen150
    15. A tantárgy tematikáját kidolgozta

    Dr Friedl Katalin egyetemi docens