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: 2023. január 12.

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

    Mérnökinformatikus MSc

    Számításelmélet mellékspecializáció
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMA14   2/1/0/v 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. Csima Judit,      egyetemi docens, SZIT  

    Dr. Friedl Katalin,   egyetemi docens, SZIT 

    Dr. Katona Gyula,   egyetemi docens, SZIT 

    5. A tantárgy az alábbi témakörök ismeretére épít Alapvető adatszerkezetek és algoritmusok (a BSc Algoritmuselmélet tantárgyának anyaga)
    6. Előtanulmányi rend
    Kötelező:
    NEM
    (TárgyEredmény( "BMEVISZMA00", "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZMA00", "FELVETEL", AktualisFelev()) > 0)

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

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

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

    A tantárgy célja az algoritmikus gondolkodás fejlesztése, további módszerek, technikák megismerése. A hallgatók betekintést kapnak nem csak a klasszikus, de az újabb és jövőbeli eszközökkel kapcsolatos eredményekbe, kérdésekbe is. Az aktuális témák és időzítésük a hallgatói érdeklődés függvényében valamennyire változhatnak. Cél, hogy mindenki, általában angol nyelvű anyagok alapján, két témakört önállóan is feldolgozzon, majd prezentálja a többieknek.

     

    A tantárgy követelményeit eredményesen teljesítő hallgatóktól elvárható, hogy:  

     (1) ismerjék meg a tárgyalt módszereket, képesek legyenek oktatói segítséggel egy kisebb témakört önállóan is feldolgozni,  

     (2) átlássák a módszerek helyességét és ezt világos módon el is tudják magyarázni, 

     (3) képesek legyenek egy nagyobb anyagból kiválasztani az érdekes és releváns részeket, 

     (4) felismerjék az egyes anyagrészek közötti kapcsolatokat, alkalmazási lehetőségeiket valós problémákra.

     

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

    A témák listája és sorrendje a hallgatók érdeklődésének függvényében változhat. Ez itt egy lehetséges változat. Az aktuális féléves anyag és beosztás a honlapon megtalálható.

    1. A várható témakörök megbeszélése, annak felmérése, ki milyen témákkal szeretne mélyebben foglalkozni. A kvantumalgoritmusok alapjai.
    2. Hatékony keresés kvantumalgoritmussal. A kvantumtitkosítás alapmódszere.
    3. Interaktív bizonyítások – az NP osztály kiterjesztése. Az AM és az IP osztályok, IP=PSPACE, a PCP alapötlete.
    4. Kommunikációs bonyolultság alapfeladata, determinisztikus és nemdeterminisztikus változata, ezek kapcsolata. Példa, amikor a véletlen segíthet.
    5. Gyakorlati mintaillesztő algoritmusok: Boyer-Moore.-algoritmus és egyéb heurisztikák.
    6. Párhuzamos algoritmusok: a PRAM modell különböző változatai. Algoritmus néhány alapvető függvényre. Bináris fa alapú algoritmusok. A processzorszám csökkentése, Brent-elv.
    7. Batcher párhuzamos rendező algoritmusa. Párhuzamos prefix-számítás és alkalmazásai. A rang meghatározása.
    8. Elosztott algoritmusok: elméleti modell. Vezetőválasztás gyűrűben szinkron és aszinkron esetben. Általánosítás tetszőleges összefüggő gráfra. Alsó becslés.
    9. Elosztott algoritmus hibák esetén. A vonalhiba esete. Algoritmus leállási hibákra. Tetszőleges (bizánci) hibák kezelése. A maximálisan tolerálható hibás processzorok száma.
    10. Hálózati topológiák pl. rács, CCC, pillangó, Benes-hálózat gráfelméleti tulajdonságai (legrövidebb utak, átmérő, vágások, összefüggőségi szám), egymásba ágyazhatóságuk, algoritmikus szempontok.
    11. Véletlen gráfok különböző modelljei, alaptulajdonságuk (pl. fokszámok, utak, összefüggőség). Véletlen gráfok mint hálózati modellek.
    12. On-line algoritmusok: modell, hatékonyság mérése. A listaelérési feladat, dinamikus adatszerkezetek, k-szerver probléma, népszerű ütemező eljárások elemzése.
    13. Paraméteres bonyolultság: NP-nehéz de kis paraméterérték mellet gyorsan megoldható feladatok. Keresőfa korlátozása és a kernelizációs módszer. W[1]-teljesség.


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

    A tananyag nagyobb részét szeminárium-szerűen, hallgatók által tartott órákkal dolgozzuk fel. A témák sorrendje, pontos köre évről évre változhat valamennyit. Az aktuális szabályokat, menetrendet az első órán megbeszéljük. 

    10. Követelmények
    • Jelenlét az órákon (a TVSZ-ben előírt mértékben). 
    • A jelenlét mellett aktív, odafigyelő  részvétel is elvárt. 
    • Az előre egyeztetett témákból felkészülés és  az előadások megtartása. Ez mindenkinek két témát jelent, egyet a félév első, egyet a második felében.
    12. Konzultációs lehetőségek

    Az előadóval való egyeztetés szerint.

    13. Jegyzet, tankönyv, felhasználható irodalom

    Thomas H. Cormen,  Charles E. Leiserson , Ronald L. Rivest,  Clifford Stein: Új algoritmusok Scolar Kiadó, 2003  

    A. Gibbons, W. Rytter: Efficient Parallel Algorithms, Cambridge University press, 1988 

    J. Flum, M. Groha: Parametrized Complexity Theory, Springer 2006 

    H. Attiya: Distributed Computing lecture notes 

    További, az interneten elérhető jegyzetek, anyagok

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra42
    Félévközi készülés órákra36
    Felkészülés zárthelyire 
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása52
    Vizsgafelkészülés20
    Összesen150
    15. A tantárgy tematikáját kidolgozta

    Dr. Friedl Katalin egyetemi docens, SZIT