Számításelmélet új szigorlati tételsor
2004. áprilisától ez az új tételsor az aktuális.

"A" tételsor

  1. Végtelen halmazok számossága: egyenlő, kisebb-egyenlő, illetve kisebb számosságú halmaz definíciója, Cantor-Bernstein-tétel (NB). Megszámlálhatóan végtelen és kontinuum számosságú halmaz. $ \mathbb{Z}$, $ \mathbb{Q}$, $ \mathbb{R}$ számossága és ezek összehasonlítása a természetes számok számosságával. Véges ábécé feletti szavak és nyelvek halmaza, e halmazok számossága. Hatványhalmaz, Cantor-tétel ($ \ast$). $ \mathbb{N}$ hatványhalmazának számossága ($ \ast$). Kontinuum-hipotézis (NB).

  2. Determináns definíciója, alaptulajdonságai ($ \ast$), kiszámítása, kifejtési tétel ($ \ast$). Mátrixok, műveletek mátrixokkal, ezek tulajdonságai ($ \ast$). Determinánsok szorzástétele (NB). Mátrix inverze, létezésének szükséges és elégséges feltétele, az inverz kiszámítása. Mátrix rangja, a rangfogalmak egyenlősége ($ \ast$). Gráf szomszédossági mátrixa, hatványainak jelentése; gráf illeszkedési mátrixa, annak rangja ($ \ast$).

  3. Lineáris egyenletrendszer megoldása Gauss-eliminációval, megoldhatóság, a megoldás egyértelműségének feltétele. $ n\times n$-es lineáris egyenletrendszer egyértelmű megoldhatóságának jellemzése a determináns segítségével ($ \ast$), általános egyenletrendszer megoldhatóságának jellemzése a rang segítségével ($ \ast$). Térbeli koordinátageometria: sík egyenlete, egyenes egyenletrendszere, metszéspontok és metszésvonalak számítása.

  4. Vektortér definíciója, példák. Altér, lineáris kombináció, generált altér, generátorrendszer. Lineáris függetlenség, a kétféle definíció ekvivalenciája. Kicserélési tétel ($ \ast$). Bázis, vektorok bázis szerinti felírásának egyértelműsége. Dimenzió, a dimenzió egyértelműsége.

  5. Lineáris leképezés fogalma, példák. Lineáris leképezés mátrixa, vektor képének meghatározása a mátrix segítségével. Lineáris leképezések szorzata, szorzat mátrixa ($ \ast$). Lineáris leképezések magtere, képtere, ezek altér volta. Dimenziótétel ($ \ast$).

  6. Lineáris transzformációk, illetve négyzetes mátrixok sajátértékei, sajátvektorai. A sajátértékek és sajátvektorok meghatározása. Sajátaltér, ennek altér volta.

  7. Kombinatorikus leszámlálási alapfeladatok, példák. Binomiális tétel. Gráfelméleti alapfogalmak: gráf, egyszerű gráf, izomorfia, részgráf, feszített részgráf, élsorozat, út, kör, összefüggőség, összefüggő komponens, fa, feszítőfa. Fák egyszerű tulajdonságai. Cayley-tétel ($ \ast$).

  8. Minimális költségű feszítőfa keresése. Piros-kék algoritmus ($ \ast$). Prim módszere, a módszer lépésszáma naív és kupacos ($ \ast$) implementáció esetén. Kruskal algoritmusa, megvalósítása UNIO-HOLVAN adatszerkezettel, lépésszáma ($ \ast$). Boruvka módszere ($ \ast$).

  9. Legrövidebb utak keresése. Szélességi bejárás, lépésszáma. Dijkstra algoritmusa ($ \ast$), lépésszáma mátrixos ($ \ast$) és éllistás ($ \ast$) megadással. Bellman-Ford algoritmusa, lépésszáma mátrixos megadás esetén. Floyd algoritmusa, lépésszáma mátrixos megadás esetén ($ \ast$).

  10. Mélységi bejárás, lépésszáma, mélységi és befejezési számozás, az élek osztályozása irányított és irányítatlan gráfok esetén. Alkalmazások: DAG tulajdonság ellenőrzése ($ \ast$), topologikus sorrend keresése ($ \ast$), legrövidebb és leghosszabb út keresése DAG-ban, PERT módszer.

  11. Síkbarajzolhatóság, kapcsolat a gömbre rajzolhatósággal, Euler-tétel ($ \ast$), felső becslés az élek számára. Kuratowski-gráfok, ezek síkba nem rajzolhatósága, Kuratowski-tétel (NB), Fáry-Wagner-tétel (NB). Dualitás, gyenge izomorfia fogalma, absztrakt dualitás, Whitney tételei (NB).

  12. Hamilton-körök és -utak. Szükséges feltétel Hamilton-kör/út létezésére. Elégséges feltételek: Ore ($ \ast$) és Dirac tétele. Hamilton-kör keresés bonyolultsága ($ \ast$). Euler-körök és -utak, ezek létezésének szükséges és elégséges feltétele.

  13. Gráfok színezése. $ \chi(G)$ fogalma és viszonya $ \omega(G)$-hez, illetve $ \Delta(G)$-hez. Brooks tétele (NB). Mycielski konstrukciója ($ \ast$). Intervallumgráfok színezése. Perfekt gráf fogalma. Síkbarajzolható gráfok kromatikus száma ($ \ast$). 3-SZÍN nyelv bonyolultsága ($ \ast$). Élkromatikus szám, $ \chi_e(G)$ viszonya $ \Delta(G)$-hez, Vizing-tétel ($ \ast$).

  14. Páros gráfok. Párosítások páros gráfban, magyar módszer ($ \ast$), lépésszáma. König tétele ($ \ast$), Hall tétele ($ \ast$), Frobenius tétele ($ \ast$). Párosítások tetszőleges gráfban, $ \nu$ és $ \tau$ kapcsolata, Tutte tétele (csak a szükségesség bizonyításával). Gallai tételei (közülük szabadon választhatóan az egyik bizonyításával).

  15. Hálózat, hálózati folyamok. A javító utas algoritmus. Ford-Fulkerson tétel ($ \ast$), Edmonds-Karp tétel (NB). Egészértékűségi lemma. A folyamprobléma általánosításai. Menger tételei ($ \ast$). Többszörös összefüggőség, élösszefüggőség. Dirac tétele (NB).

  16. Oszthatóság, felbonthatatlan és prímtulajdonságú számok. A számelmélet alaptétele ($ \ast$). Osztók száma. A prímek számának végtelensége. Kongruencia fogalma, alapműveletek kongruenciákkal. Lineáris kongruenciák, a megoldhatóság szükséges és elégséges ($ \ast$) feltétele. Wilson tétele ($ \ast$).

  17. Teljes és redukált maradékrendszer, $ \varphi$-függvény definíciója. Euler-Fermat-tétel ($ \ast$), kis Fermat-tétel. Euklideszi algoritmus.

  18. Számelmélet és algoritmusok: alapműveletek, hatványozás az egészek körében és modulo $ m$. Prímtesztelés (feladata, Fermat-féle teszt, Carmichael számok). Nyilvános kulcsú titkosírás.

  19. Művelet fogalma, félcsoport, csoport, Abel-csoport, részcsoport, elem rendje. Példák: csoportok számokon, mátrixokon, rajzok szimmetriacsoportja, ciklikus csoport, diédercsoport, szimmetrikus csoport. Csoportok izomorfiája. Mellékosztály, Lagrange tétele ($ \ast$), elemrend és csoport rendjének kapcsolata.

  20. Gyűrű és test fogalma. Példák: $ \mathbb{Z}$, $ \mathbb{Q}$, $ \mathbb{R}$, $ n\times n$-es mátrixok, polinomok, $ \mathbb{Z}_p$. Komplex számok, algebrai és trigonometrikus alak, alapműveletek komplex számokkal. Komplex szám $ n$-edik gyöke, egységgyökök.

``B'' tételsor

  1. Rendezési feladat. Buborékrendezés, lépésszáma ($ \ast$). Beszúrásos rendezés, lépésszáma. Rendezett sorozatok összefésülése, az összefésülés lépésszáma, összefésüléses rendezés, lépésszáma ($ \ast$). Alsó korlát az összehasonlítás alapú rendezésekre ($ \ast$). Gyorsrendezés, lépésszáma ($ \ast$). Ládarendezés, radixrendezés ($ \ast$), lépésszámuk ($ \ast$).

  2. Kupac adatszerkezet, műveletek, lépésszámuk, kupacépítés ($ \ast$). Kupacos rendezés, lépésszáma. Lineáris és bináris keresés rendezett halmazban, a keresés lépésszáma, alsó korlát. Bináris keresőfák, műveletek, lépésszámuk.

  3. AVL-fák, szintszám ($ \ast$), műveletek ($ \ast$), lépésszámuk ($ \ast$). 2-3 fák, szintszám, műveletek, lépésszámuk. B-fák, műveletek ($ \ast$), lépésszámuk ($ \ast$).

  4. Vödrös hash-elés, a műveletek lépésszáma ($ \ast$). Nyitott címzésű hash-elés: lineáris és kvadratikus maradék próba ($ \ast$), kettős hash-elés. Jó hash-függvények ($ \ast$). A hash-elés alkalmazhatósága, összehasonlítva a keresőfákkal.

  5. A Turing-gép fogalma, működése. A többszalagos Turing-gép szimulálása egyszalagossal, az idő és tárkorlát változása ($ \ast$). A Chomsky nyelvosztályok kapcsolata a Turing-gép változataival ($ \ast$). Univerzális Turing-gépek létezése ($ \ast$). Church-Turing-tézis.

  6. Rekurzív és rekurzívan felsorolható nyelvek és rekurzív, illetve parciálisan rekurzív függvények. Az R, RE, coR és coRE nyelvosztályok kapcsolata. Nevezetes nyelvek, bonyolultságuk: diagonális nyelv, univerzális nyelv ($ \ast$), megállási nyelv, dominó probléma ($ \ast$), Post megfeleltetési feladata (NB), környezetfüggetlen nyelvtanokkal kapcsolatos eldönthetetlen feladatok ($ \ast$).

  7. Kolmogorov-bonyolultság: adott Turing-gépre vett bonyolultság, invariancia-tétel, a Kolmogorov bonyolultság definíciója, a definíció értelmessége. Összenyomhatatlanság, összenyomhatatlan szavak létezése ($ \ast$), a C függvény bonyolultsága ($ \ast$).

  8. Idő- és tárkorlátos Turing-gépek. Tár-idő-tétel ($ \ast$). Nevezetes nyelvosztályok: P, PSPACE, EXPTIME, ezek kapcsolata.

  9. Nemdeterminisztikus Turing-gépek, idő és tárbonyolultságuk. NP és coNP nyelvosztály, ezek kapcsolata P-vel és R-rel. Tanú-tétel ($ \ast$). Példák NP és coNP-beli nyelvekre.

  10. Karp-redukció, a Karp-redukció tranzitivitása. NP-teljesség. Cook-Levin-tétel ($ \ast$). További nyelvek NP-teljessége: 3-SAT ($ \ast$), 3-SZÍN ($ \ast$), MAXFTLEN, X3C (NB), H (NB), RH (NB), Ládapakolás (NB).

  11. Dinamikus programozás: elve, példák a korábbi algoritmusok közül, hátizsák probléma megoldása kis súlyok esetén, az algoritmus lépésszáma. Közelítő algoritmusok: elv, algoritmus a ládapakolási feladatra ($ \ast$).

  12. Véges automata. Véges automaták determinizálása és teljesen specifikálása. Minimálautomata, konstrukciója, unicitása ($ \ast$). Kétirányban mozgó véges automata, kapcsolata az egyirányban mozgó véges automatával ($ \ast$).

  13. Generatív nyelvtanok, Chomsky-nyelvosztályok. A generatív nyelvek számossága. Bal- és jobb-reguláris nyelvtanok, kapcsolatuk ($ \ast$), reguláris nyelvek. Véges automaták és reguláris nyelvek kapcsolata.

  14. Reguláris nyelvek zártsági tulajdonságai: metszet, unió ($ \ast$), komplementer, konkatenált, tranzitív lezárt ($ \ast$). Pumpálási lemma reguláris nyelvekre ($ \ast$). Reguláris halmazok, kapcsolatuk a reguláris nyelvekkel ($ \ast$).

  15. Környezetfüggetlen nyelvek. Környezetfüggetlen nyelvtanok jólfésült alakra hozása. Chomsky-normálformára hozás. Greibach-normálforma ($ \ast$). Rekurzió és balrekurzió kiküszöbölhetősége.

  16. Veremautomaták. Állapottal és üres veremmel elfogadó veremautomaták, ezek kapcsolata. Mélységbe látó veremautomata, kapcsolata a nem mélységbe látó veremautomatával ($ \ast$). Környezetfüggetlen nyelvtanok és veremautomaták kapcsolata ($ \ast$), környezetfüggetlen nyelvtanból veremautomata konstruálása.

  17. Pumpálási lemma környezetfüggetlen nyelvekre ($ \ast$). A környezetfüggetlen nyelvek zártsági tulajdonságai: metszet, unió, komplementer, konkatenált ($ \ast$), tranzitív lezárt ($ \ast$). Determinisztikus környezetfüggetlen nyelvek. A determinisztikus környezetfüggetlen nyelvek zártsági tulajdonságai: metszet, unió, komplementer ($ \ast$).

  18. A fordítás fogalma. Véges fordító. Reguláris ($ \ast$) és környezetfüggetlen nyelvek zártsági tulajdonságai a véges fordítás esetén. Veremfordító, szintaxis vezérelt fordítási séma, kapcsolatuk ($ \ast$).

  19. Levezetési fa környezetfüggetlen nyelvtanok esetén. Környezetfüggetlen nyelvtanok és nyelvek egyértelműsége. A környezetfüggetlen nyelvtanok elemzésének célja. Cocke-Younger-Kasami algoritmusa. Az Earley-algoritmus.

  20. Balelemzés. Az LL(k)-elemzés algoritmusa (erős és gyenge). LL(k) nyelvtanok ($ \ast$) és nyelvek ($ \ast$).

  21. Jobbelemzés. Az LR(k)-elemzés algoritmusa. LR(k) nyelvtanok ($ \ast$) és nyelvek ($ \ast$). Prefix tulajdonságú nyelvek, kapcsolatuk az LR(k)-elemzéssel ($ \ast$).

  22. A precedenciaelemzés algoritmusa. Erős és gyenge precedencia-nyelvtanok, erősen és gyengén precedencia-elemezhető nyelvek kapcsolata ($ \ast$). Az operátor precedencia elemzés.