Igyekszem azt feltenni ide, ami az előadáson történik, de lehetnek benne hibák. Az anyag az, ami az előadáson elhangzik.

1. elõadás (szeptember 16.)

Tudnivalók a félévről;
Bevezető az algoritmusokról, hatékonyságuk mérése: ordó, omega, theta; Rekurziós formulákból zárt képlet kinyerése;
Néhány példa: mobilátjátszók frekvenciakiosztása, Artúr király házasítása, szuperforrás keresésére két algoritmus és alsó becslés is a legjobb algoritmus lépésszámára;
Rendezési reláció és rendezett halmaz definíciója, a rendezési feladat ismertetése

2. elõadás (szeptember 19.)

Keresés rendezett halmazban (lineáris és bináris keresés), alsó becslés a lépésszámra;
Buborékrendezés, összehasonlítások és mozgatások száma; Beszúrásos rendezés, összehasonlítások és mozgatások száma lineáris és bináris keresés esetén;
Alsó becslés összehasonlításalapú rendezések esetén az összehasonlítások számára;
Rendezett sorozatok összefésülése, össszefésüléses rendezés, összehasonlítások és mozgatások száma;
Kupac adatszerkezet, ennek implementációjaként bináris kupac;

3. elõadás (szeptember 26.)

Bináris kupac, az építés, a beszúrás és a mintör, ezek költségei; kupacos rendezés.
Gyorsrendezés
k-adik elem kiválasztása (lineáris algoritmus ismertetése nem)
Kulcsmanipulációs rendezések: ládarendezés

4. elõadás (október 1.)

Radixrendezés
Párhuzamos rendezés: Batcher-féle páros-páratlan összefésülés
Bináris fák bejárásai: pre-, in- és posztorder
Bináris keresőfák, keresés, beszúrás, törlés, faépítés

5. elõadás (október 3.)

Kiegyensúlyozott fák: AVL-fák (szintszám, forgatások, műveletek), HB[k]-fák, súlyra kiegyensúlyozott fák
Kis mese az önszerveződő fákról

6. elõadás (október 15.)

Önszerveződő fák: S-fa
2-3 fák: szintszám, műveletek
B-fák: szintszám, műveletek, miért jó

7. elõadás (október 17.)

Hash: alapelv, megoldandó problémák
Vödrös hash
Nyílt címzés:lineáris próba, álvéletlen próbálás (kvadratikus maradék próba), kettős hash
Hash függvények
Szekvenciális keresés
Gráfalgoritmusokról általában, gráfok megadásai: mátrixos és éllistás

8. elõadás (október 18.)

Legrövidebb utak kereséséről általában
Dijkstra algoritmus, utak nyomonkövetésével is, lépésszám mátrixos és éllistás megadás esetén
Bellman-Ford algoritmus, utak nyomonkövetése is, lépésszám mátrixos megadással

9. elõadás (október 29.)

Floyd algoritmusa legrövidebb utak keresésére, utak nyomonkövetése is, lépésszám mátrixos megadással
Tranzitív lezárás, Warshall algoritmus
Gráfbejárások, mélységi és szélességi bejárás elve
Szélességi bejárás, az élek osztályozása irányított és irányítatlan gráf esetén
Legrövidebb utak meghatározása szélességi bejárással, ha minden élsúly azonos

10. elõadás (október 31.)

Mélységi bejárás, számozás, az élek osztályozása irányított és irányítatlan gráf esetén
Irányított, körmentes gráfok (DAG), a DAG-ság tesztelése mélységi bejárással
Topologikus sorrend, elkészítése, legrövidebb és leghosszabb utak keresése DAG-ban

11. elõadás (november 12.)

Minimális feszítőfa keresése: piros-kék algoritmus
Prim algoritmusa naív és kupacos implementációval
Kruskal algoritmusa, megvalósítás Únió-Holvan fákkal

12. elõadás (november 14.)

Kruskal módszerének javítása, Boruvka módszere
Maximális párosítás keresése páros gráfban a magyar módszerrel, az algoritmus lépésszáma

Turing-gép definíciója, működése, elfogadás és kiszámítás Turing-géppel
Példák
Rekurzív és rekurzívan felsorolható nyelvek, R és RE nyelvosztály
Church-Turing tézis

13. elõadás (november 21.)

Rekurzív és parciálisan rekurzív függvény fogalma
Nem rekurzívan felsorolható nyelv létezése
Turing-gépek kódolása, univerzális Turing-gép létezése
Nehéz nyelvek bonyolultsága: diagonális nyelv, univerzális nyelv, megállási nyelv, Hilbert 10. problémája, Dominó-probléma, Post megfeleltetési feladat, környezetfüggetlen nyelvtanok egyértelműsége

14. elõadás (november 26.)

A coX nyelvosztály definíciója
Kapcsolat az R, RE, coR és coRE nyelvosztályok között; L rekurzívan felsorolható pontosan akkor, ha egy Turing gép felsorolja a szavait kimenetként
Tár és időkorlátok, tár és időkorlátos Turing-gépek, TIME(t(n)) és SPACE(s(n)) osztályok definíciója, P, PSPACE, EXPTIME definíciója
k-szalagos Turing-gép szimulálása 1-szalagossal, az idő és tárkorlát változása eközben
Tár-idő tétel állítása és ennek következményei

15. elõadás (november 28.)

Tár-idő tétel bizonyítása és a tétel további következményei
Nemdeterminisztikus Turing-gépek, elfogadott nyelv, időkorlátosság
Az NP nyelvosztály definíciója, P, NP és coNP kapcsolata
Felismerés súgással
Tanú tétel és bizonyítása

16. elõadás (december 5.)

Tanú tétel következményei, példák NP-beli nyelvekre: 3-SZIN, H, SIK, prímek
Karp-redukció, értelmezése, példa: 3-SZIN visszavezetése 4-SZIN-re
Karp-redukció tulajdonságai
NP-teljesség

17. elõadás (december 10.)

Cook-Levin tétel, a bizonyítás vázlata
Az alábbi nyelvek és NP teljességük: 3-SAT, k-SAT, 3-SZIN, k-SZIN, MAXFTLEN, MAXKLIKK, H, IH, Utazóügynök

18. elõadás (december 12.)

Miért érdekesek az NP-teljes nyelvek?
További NP-teljes problémák: 3DH, X3C, Hátizsák, Részhalmaz-összeg, Partíció, Ládapakolás
Általános algoritmustervezési technikák:
dinamikus programozás: korábbi példák (Bellman-Ford, Floyd, Cocke-Younge-Kasami formális nyelvekből), hátizsák probléma megoldása kis súlyok esetén
közelítő algoritmusok (minimális lefogó ponthalmaz, ládapakolás FF és FFD algoval).

19. elõadás (december 13.)

Randomizált algoritmusok, példa a prímtesztelés Fermat-féle prímtesztttel
Kolmogorov bonyolultság: adott Turing-gépre vett bonyolultság, Invariancia tétel, a Kolmogorov-bonyolultság definíciója, a C függvény nem-rekurzivitása, összenyomhatatlan szavak, ilyenek létezése
RAM-gépek, költségszámításuk: uniform és logaritmikus költség, szimuláció Turing-gép es RAM-gép között