Alapvető algoritmikus technikák

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

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.

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.

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.

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

A vizsgaidőszakban: nincs

Elővizsga:

Előzetes egyeztetés szerint.

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.