Bevezetés a számításelméletbe (kieg)
tárgy vizsgatételei

(2003/2004 I. félév)
  1. 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, erdő. Fák egyszerű tulajdonságai.
  2. Cayley-tétel, Prüfer-kód.
  3. Minimális súlyú feszítőfa keresése: Kruskal algoritmusa, Prim algoritmusa.
  4. Legrövidebb utak keresése: szélességi bejárás, Dijkstra algoritmusa.
  5. Bellman-Ford algoritmusa, Floyd algoritmusa.
  6. Mélységi bejárá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,
  7. PERT módszer.
  8. Euler-körök és séták.
  9. Hamilton-körök és -utak. Hamilton-kör létezésének szükséges feltétele. Elégséges feltételek: Ore és Dirac tétele.
  10. Párosítások, javító utak. Tutte tétele (biz.nélkül). Páros gráfok fogalma, jellemzése. Párosítások páros gráfokban: Hall és Frobenius tétele.
  11. Gallai tételei, König-tétel.
  12. Hálózati folyamok. A javító utas algoritmus. Ford-Fulkerson tétel, Edmonds-Karp tétel (biz.nélkül). Egészértékűségi lemma.
  13. Gráfok színezése, kromatikus szám fogalma, viszonya a maximális fokszámhoz és a klikkszámhoz, Brooks tétele (biz. nélkül), Mycielski konstrukciója.
  14. Élszínezés, élgráfok, Vizing-tétel (biz. nélkül). Síkgráfok ötszíntétele.
  15. Síkbarajzolhatóság, kapcsolat a gömbre rajzolhatósággal, Euler-formula, felső becslés egy síkgráf éleinek számára.
  16. Kuratowski-tétel (csak az egyik irányt kell bizonyítani), Fáry-Wagner-tétel (biz. nélkül). Dualitás, gyenge izomorfia, Whitney tételei (biz. nélkül).
  17. Bonyolultságelmélet: P, NP, coNP osztályok és ezek viszonya. Polinomiális visszavezetés, példák. NP-teljesség fogalma. Példák NP-teljes problémákra.
  18. Oszthatóság, legnagyobb közös osztó, legkisebb közös többszörös, prímek. A számelmélet alaptétele (biz.nélkül). Osztók száma és osztók összege.
  19. Kongruencia fogalma, teljes és redukált maradékrendszer, fi-függvény, Euler-Fermat tétel, Fermat-tétel.
  20. Euklideszi algoritmus. Prímtesztelés: Fermat-teszt, Miller-Rabin-teszt.