Számításelmélet szigorlati tételsor
A 2004. március 22-i szigorlaton lehet még eszerint vizsgázni, ha a hallgató kéri. 2004. áprilisától már az új tételsor lesz az aktuális.
 
Színmagyarázat:
Bevezetés a számításelméletbe
Algoritmusok elmélete
Formális nyelvek
két tárgyban is elôforduló témák

"A" tételsor

  1. Valós számok (tizedestört-alak és racionalitás kapcsolata), komplex számok (kanonikus és trigonometrikus alak, mûveletek, egységgyökök), kvaterniók.
  2. Számosságok, összehasonlításuk. Megszámlálható- és kontinuum számosság. Hatványhalmaz és számossága, a kontinuumhipotézis.
  3. Koordinátarendszer, vektorok, mûveletek vektorokkal, vektoriális szorzat, vegyesszorzat. Pont, egyenes, sík egyenlete, illeszkedések, és kapcsolataik lineáris egyenletekkel.
  4. Lineáris egyenletrendszer megoldhatóságának szükséges és elégséges feltétele. Lineáris egyenletrendszer megoldása Gauss-algoritmussal.
  5. Mátrix definíciója, szorzás, tulajdonságai, rang, inverz. Determináns ekvivalens definíciói, tulajdonságai.
  6. Lineáris vektortér definíciója. Lineáris kombináció, generátorrendszer, lineáris függetlenség, bázis, altér, dimenzió.
  7. Lineáris leképezések, transzformációk, ezek mátrixai. Lineáris leképezés kép-, és magtere, dimenziótétel.
  8. Négyzetes mátrix sajátértékei, sajátvektorai, ezek meghatározása.
  9. Gráfelméleti alapfogalmak, fák egyszerûbb tulajdonságai. Cayley tétele (fák száma), Prüfer-kód.
  10. Minimális költségû feszítôfa keresése: a piros-kék algoritmus, Kruskal és Prim módszere. Az UNIÓ-HOLVAN adatszerkezet.
  11. Síkbarajzolhatóság, Euler-féle poliédertétel, Kuratowski tétele. Dualitás, gyenge izomorfia, Whitney tételei, vágások tulajdonságai.
  12. Gráfok illeszkedési, kör-, és vágásmátrixai, ezek tulajdonságai. Gráfok szomszédsági mátrixa (csúcsmátrixa).
  13. Legrövidebb utak keresésére szolgáló algoritmusok (Dijkstra, Bellman-Ford, Floyd, Warshall).
  14. Euler-körök és utak, Euler tétele. Hamilton-körök és utak. Hamilton-kör keresése.
  15. Párosítások, Hall és Frobenius tétele, Tutte tétele. A magyar módszer.
  16. König-tétel, Gallai tételei.
  17. Gráfok színezése, Mycielsky konstrukciója. A 3-SZÍN feladat. Ötszíntétel síkgráfokra. Élszínezés. Perfekt gráfok.
  18. Hálózati folyamok, Ford-Fulkerson-tétel, az Edmonds-Karp-algoritmus.
  19. Menger-tételek, magasabb összefüggôség, Dirac-tétel.
  20. Oszthatóság, prímek, a számelmélet alaptétele, Euklideszi algoritmus.
  21. Kongruencia fogalma, teljes és redukált maradékrendszer, phi-függvény, Euler-Fermat-tétel, Wilson-tétel. Lineáris kongruenciák megoldása.
  22. Aritmetikai algoritmusok bonyolultsága, prímtesztelés, nyilvános kulcsú titkosírások.
  23. Félcsoport, csoport, Abel-csoport, elem rendje, ciklikus csoport, szimmetrikus csoport, Cayley tétele.
  24. Mellékosztály, részcsoport rendje és indexe, Lagrange-tétel. Normálosztó, faktorcsoport, homomorfizmus-tétel.
  25. Gyûrûk, testek, nevezetes példák.
  26. Összehasonlítás-alapú adatrendezési módszerek.
  27. Kulcsmanipulációs rendezések, összefésülésen alapuló rendezési módszerek. Külsô tárak tartalmának rendezése.
  28. Bináris keresôfák: naiv algoritmusok, S-fák.
  29. AVL fák, 2-3 fák és B-fák.
  30. Információ-tömörítés (Huffmann, Lempel-Ziv-Welch).
  31. A hashelés általános tulajdonságai (cél, alkalmazhatóság, kezelendô problémák).
  32. Ütközések feloldására szolgáló technikák hashelésnél, jó hash-függvények.
  33. A mélységi bejárás és alkalmazásai: DAG tulajdonság tesztelése, topologikus rendezés, erôs komponensek, a PERT-módszer.
  34. A szélességi bejárás és alkalmazásai (legrövidebb utak, magyar módszer, Edmonds-Karp).

"B" tételsor

  1. A Turing-gép fogalma, mûködése. Rekurzív nyelvek, függvények, rekurzíve felsorolható nyelvek, parciálisan rekurzív függvények fogalma.
  2. Univerzális Turing-gépek; a diagonális nyelv, példák eldönthetetlen nyelvekre (univerzális, megállási nyelv, Hilbert 10. problémája, Post megfeleltetési feladata). Church-Turing-tézis.
  3. Kolmogorov-bonyolultság (invariancia-tétel, összenyomhatatlanság, C kiszámíthatatlansága).
  4. Idô- és tárkorlátos Turing-gépek, nevezetes nyelvosztályok (P, PSPACE, EXPTIME).
  5. A közvetlen elérésû gép és kapcsolata a Turing-gépekkel; uniform és logaritmikus költség.
  6. Nemdeterminisztikus Turing-gépek, az NP- és coNP-nyelvosztály, tanú-tétel.
  7. Karp-redukció, NP-teljesség, a Cook-Levin-tétel.
  8. Nevezetes NP-teljes nyelvek (3-SAT, 3-SZÍN, MAXFTLEN, 3DH, X3C, H, RH, Ládapakolás, EP).
  9. Dinamikus programozás, elágazás és korlátozás, közelítô módszerek.
  10. Randomizált algoritmusok, az RP-nyelvosztály.
  11. A formális nyelv fogalma, generatív nyelvek, Chomsky-nyelvosztályok, a nyelvek számossága.
  12. Reguláris nyelvek és véges automaták, ekvivalenciájuk. Determinisztikus és nemdeterminisztikus véges automaták.
  13. Minimálautomaták és azok unicitása.
  14. Két irányban mozgó automaták. Nyelvi mûveletek és a véges automaták zártsága ezekre a mûveletekre.
  15. Reguláris kifejezések és reguláris halmazok; ekvivalenciájuk a reguláris nyelvekkel.
  16. Környezetfüggetlen nyelvek, levezetési fák, egyértelmû és nem egyértelmû nyelvek.
  17. Nyelvtanok átalakítása, nyelvtanok rekurzivitása, normálformák.
  18. Veremautomaták, állapottal és üres veremmel elfogadó valamint mélységbe látó automaták, és ekvivalenciájuk.
  19. A környezetfüggetlen nyelvtanok és a veremautomaták ekvivalenciája.
  20. Determinisztikus és nemdeterminisztikus nyelvek. A mûveletekre való zártság a környezetfüggetlen nyelvek esetében.
  21. A fordítás fogalma, véges fordítók és veremfordítók.
  22. Szintaxis-vezérelt fordítási sémák, jellemzô és szigorúan jellemzô nyelvtanok.
  23. A nyelvosztályok zártsága a véges fordítás mûveletére.
  24. Általános elemzôk. A Coke-Younger-Kasami-módszer.
  25. Az Earley-algoritmus.
  26. Balelemezhetô nyelvtanok és nyelvek, az LL(k)-elemzôk. Faktorizálás.
  27. Jobboldali elemzés; LR(k)-elemzôk; prefix tulajdonságú nyelvek.
  28. Egyszerûsített jobboldali elemzés, erôs és gyenge precedencia-nyelvtanok, operátor precedencia elemzôk.
  29. A Turing-gép és a 0-osztályú nyelvek. A számítástechnikai nyelvészet algoritmikusan eldönthetetlen problémái.
  30. Környezetfüggô illetve nem csökkentô nyelvtanok, a lineárisan korlátozott automata.

BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM -- SZÁMÍTÁSTUDOMÁNYI ÉS INFORMÁCIÓELMÉLETI TANSZÉK