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: 2014. október 3.

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

    Mérnökinformatikus szak, MSc képzés

    Számításelmélet mellékspecializáció

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMA00 1 2/1/0/f 4  
    3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin, Számítástudományi és Információelméleti Tanszék
    A tantárgy tanszéki weboldala http://cs.bme.hu/algbony
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Csima Judit

    egyetemi docens

    Számítástudományi és Információelméleti Tanszék

    Dr. Friedl Katalin

    egyetemi docens

    Számítástudományi és Információelméleti Tanszék

     

    Dr. Katona Gyula

     

     

    egyetemi docens

     

    Számítástudományi és Információelméleti Tanszék

    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árgyEredmény( "BMEVISZM143" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZM143", "FELVETEL", AktualisFelev()) > 0)

    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 korábbi változatot (VISZM143) vagy a  VISZM031 kódú “ Algoritmusok és bonyolultságuk – matematikusoknak” 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, 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. Cél, hogy mindenki egy általa választott témakört önállóan is feldolgozzon.

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

    1)      A várható témakörök, előadások megbeszélése. 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. PCP (Probabilistically checkable proofs)

    2)      Kommunikációs bonyolultság: hogyan lehet együttműködve számolni minimális információcserével. Kapcsolata a függvény mátrixával (mátrix felbontás, rang). Nemdeterminisztikus bonyolultság, és kapcsolata a determinisztikus bonyolultsággal. Példák véletlent használó protokollokra,  hatékonyságuk.

    3)      Geometriai algoritmusok a síkban: Fordulási irány megállapítása osztás nélkül. Hatékony algoritmusok a konvex burok meghatározására. A legközelebbi pontpár megtalálása.

    4)      A keresés és rendezési algoritmusok továbbfejlesztése: Listában a középső (k-adik) elem megtalálása összehasonlításokkal. Algoritmus a listabeli elemek nagyság szerinti sorszámának meghatározására (rang számolása). Intervallumok hatékony tárolása.

    5)      Mintaillesztés: KMP-algoritmus, Boyer-Moore- algoritmus. Mintaillesztő automata. Mintaillesztés hibák esetén. A szerkesztési távolság  és annak meghatározása dinamikus programozással.

    6)      Párhuzamos algoritmusok: A PRAM-modell különböző változatai, egyszerű függvények hatékony számolása az eltérő modellekben. Bináris fa alapú algoritmusok. A processzorszám csökkentése: Brent-elv.

    7)      Párhuzamos algoritmus a rendezési feladatra (Batcher). A prefix-számítás eljárása és ennek alkalmazásai. A rang meghatározása párhuzamosan.

    8)      Elosztott algoritmusok: az elméleti modell. Algoritmusok a  gyűrűben való vezetőválasztásra szinkron és aszinkron esetben. Általánosítás  tetszőleges gráfra. Alsó becslés az üzenetek számára. Az egyezségre jutás feladata.

    9)      Elosztott algoritmusok hibákkal. A vonalhiba esete. Algoritmus processzorok leállási hibája esetén.  Rosszindulatú (bizánci) hibák kezelése. Felső becslések az egyezséget még lehetővé tevő hibák számára.

    10)   Hálózati topológiák gráfelméleti szempontból: 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ő modellek, ezek alaptulajdonságai (fokszámok, utak, összefüggőség). A véletlen gráfok, mint hálózati modellek.

    12)   Paraméteres bonyolultság: NP-nehéz, de paraméteresen megoldható feladatok. Keresőfa  mélységének korlátozása. A gráfminor tétel és következményei. Kernelizációs módzserek. W[1]-teljesség.

    13)   On-line algoritmusok: modell, hatékonyság mérése, listaelérési feladat. Egyszerű, sokat használt ütemező algoritmusok és elemzésük.

    14)  Kvantumszámítás: elméleti modell, lineáris algebrai eszköztár. Egyszerű algoritmusok (teleportálás, Deutsch-Józsa). A Fourier-transzformáció haszna. Prímfelbontás. Titkosítás kvantumeszközök esetén.

         

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

    A tananyagot részben szeminárium-szerűen, hallgatók által tartott órákkal dolgozzuk fel. A témák sorrendje, és az érdeklődéstől függően a pontos köre is évről évre változhat valamennyit. Az aktuális menetrendet az első órán megbeszéljük.

    10. Követelmények

    aktív részvétel az órákon, valamint előadás, beszámoló tartása.

     

    A vizsgaidőszakban: nincs

    Elővizsga:

    11. Pótlási lehetőségek Beszámoló 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.

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

    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ákra28
    Felkészülés zárthelyire 
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása50
    Vizsgafelkészülés 
    Összesen120
    15. A tantárgy tematikáját kidolgozta

      Név:

    Beosztás:

    Tanszék, Int.:

      Dr. Friedl Katalin

    egyetemi docens

    Számítástudományi és Információelméleti Tanszék