MSc Algoritmuselmélet
2017, ősz
Jelölések:
!!: Fontos definíció, TUDNI KELL
!: Alapösszefüggés
!*: [általában] Tétel, kimondani tudni kell, ha van triviális iránya,
akkor azt is tudjuk azonosítani, de bizonyítása
(amennyiben szerepelt előadáson) csak
akkor, ha a többi dolog már jól megy
**: Csak akkor, ha a többi dolog jól megy
Tematika:
- Dinamikus programozás, példák:
legnagyobb konvex részhalmaz keresése síkbeli
ponthalmazban, legnagyobb független halmaz
keresése fában.
-
Hálózat, folyam, folyam értéke, vágás, vágás
kapacitása, javító út. !!
-
Folyamok alaptétele, MFMC tétel !*
-
Ford-Fulkerson-algoritmus !!:
egész kapacitású hálózatok, az algoritmus ciklizálása.
-
Edmonds-Karp algoritmus:
reziduális hálózat, fázisok !*
-
Dinic algoritmus. **
-
Amortizációs analízis: bankár/fizikus nyelvezet.
Példák: számláló, konvex burok meghatározása.
-
Fibonacci-kupacok:
Szolgáltatások és megvalósításuk. !!
Amortizációs analízis !*
-
Karakter vs szótár alapú kódolás,
LZW tömörítő algoritmus. !!
-
Számelméleti algoritmusok.
Hatványozás vs moduláris hatványozás !!,
Pratt prímség bizonyítási sémája !*
Hatványszámok tesztelése,
Kis-Fermat tétel polinomokra !!
AKS prímtesztelési algoritmus **
-
Turing-gép alapdefiníciója. !!
-
Eldönthető és felsorolható nyelvek. !!
-
Számítási problémák, eldöntési problémák, nyelvek. !!
-
Idő és tárigény, bonyolultsági osztályok. !!
-
Bonyolultsági osztályok kapcsolata. !*
-
Nem-determinizmus, mindkét szemlélete. !!
Nem-determinisztikus gépek által
elfogadott nyelvek. !!
Nem determisznisztikus nyelvosztályok. !!
-
Nem determisznisztikus nyelvosztályok viszonya
a többi nyelvosztályhoz. !*
-
Irányított elérhetőség problémája. !!
-
Turing-gépek kódolása, univerzális Turing-gép. !!
-
Megállási probléma és eldönthetetlensége. !*
-
Példák: Párosítás, irányított elérhetőség,
Hamilton-kör, prímtesztelés, faktozízáció
elhelyezése az ismert nyelvosztályok között. !!
-
Karp-redukció (definíció) és tulajdonságai
(polinom idejű és logaritmikus tár esetben
tranzitívitás).
-
Teljes problémák. Konkrét esetek: NL-, P-, NP-teljesség.
-
Irányított elérhetőség NL-teljes. !!
Hálózat-kiértékelés P-teljes. !*
Hálózat-kielégíthetőség NP-teljes. !*
-
További NP-teljes problémák: logika, gráfelmélet, számelmélet. !!
-
Savitch-algoritmus irányított elérhetőségre
és következményei. !*
-
Immerman-Szelepcsényi tétel kimondása.
-
Véletlen biteket használó Turing-gépek és
bonyolultsági osztályaik. !!
-
Egy/két irányú hibák. !!
Hibajavítás ismételgetésekkel. !*