Algoritmusok és bonyolultságuk

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.