Théorie d'algorithme

Turing gépek (TG): definíció; egyszerű példák; idő- és tárkorlátos TG; univerzális TG; többszalagos TG szimulációja 1 szalagossal, TG-k konstrukciója.

A kiszámíthatóság elméletének alapjai: Rekurzíve felsorolható és rekurzív nyelvek, parciális rekurzív és rekurzív függvények, kapcsolatuk egymással; R a RE és coRE osztályok metszete; RE-n kívüli nyelvek létezése; a megállási feladat eldönthetetlensége, nyelv-tulajdonságok eldönthetetlensége; Hilbert 10. problémája; dominóprobléma; Post feladat; Church-Turing tézis.

A RAM gép: definíció; logaritmikus költség és uniform költség

RAM-TG és TG-RAM szimulációk.

Kolgomorov bonyolultság: invariancia tétel: összenyomhatatlan szavak létezése, alkalmazások; a Kolgomorov bonyolultság kiszámíthatatlansága.

Nevezetes bonyolultsági osztályok: idő és tár kapcsolata; lineáris idő, P, FP, PSPACE, EXPTIME példákkal.

Az NP nyelvosztály: Nemdeterminisztikus Turing gépek (NTG); NP definíciója NTG-vel illetve tanúkkal; példák NP-beli nyelvekre (gráftulajdonságok: összefüggőség, színezhetőség, független ponthalmazok, Hamilton-kör stb.; lieáris egyenlőtlenség-rendszerek, összetett illetve prímszámok); jó karakterizáció (NP és coNP metszete), Pratt, Kuratowski.

NP-teljesség: Karp redukció, NP-teljesség, Cook-Levin tétel; nevezetes NP-teljes nyelvek (3-SAT, 3-színezés, független ponthalmaz, 3DM, hátizsák probléma, ládapakolás stb.).

Randomizált algoritmusok: plinomazonosság tesztelés (Schwartz lemmája); Rabin-Miller prímteszt, véletlen prímszám generálása, a nyilvános kulcsú kriptográfia elemei; az RP és Las Vegas nyelvosztályok.

Algoritmus-tervezési technikák: mohó módszer (pl. minimális költségű feszítőfa), oszd meg és uralkodj, dinamikus programozás (pl. hátizsák), korlátozás és elágazás (pl. maximális független ponthalmaz gráfban), közelítő módszerek (pl. ládapakolási heurisztikák).

Adatrendezési módszerek: rendezés összehasonlításokkal (beszúrásos, összefésülő, gyorsrendezés); kupac fogalma, kupacos rendezés; kulcsmanipulációs rendezések (láda- és radixrendezés); külső tárak tartalmának rendezése.

Alapvető adatszerkezetek: tömb, lista, verem, sor; kereső fák (bináris keresőfák, 2-3 fák, B-fák, AVL fák, szófák); hashelés (cél, alkalmazhatóság, kezelendő problémák), ütközések feloldása (láncolás, nyitott címzés), jó hash-függvények; szekvenciális keresés. Információ tömörítés.

Alapvető gráf-algoritmusok: gráfok tárolására szolgáló adatszerkezetek; legrövidebb utak keresése (Dijkstra, Floyd, Warshall módszerei); mélységi keresés és aklkalmazásai (DAG tulajdonság tesztelése, erős komponensek); topologikus rendezés; szélességi keresés; minimális költségű feszítőfa keresése (piros-kék algoritmus, Boruvka, Prim és Kruskal módszerei); az UNIÓ-HOLVAN adatszerkezet; maximális párosítás kétrészes gráfokban, folyamok hálózatokban.

Alapvető aritmetikai algoritmusok: euklideszi algoritmus, gyors hatványozás.