Algoritmusok és bonyolultságuk

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.