A műszaki informatika szakos hallgatók

Bevezetés a számításelméletbe c. tárgyának vizsgatételei (2004/2005-ös tanév)

II. keresztfélév

1. Euler-körök és -utak, Euler tétele. Hamilton-körök és -utak. Hamilton-kör létezésének tanult szükséges feltétele, annak bizonyítása, hogy e feltétel nem elégséges.

2. Elégséges feltételek Hamilton-kör létezésére: Dirac, Ore, Pósa és Chvátal tétele, e tételek egymáshoz való viszonya, az Ore tétel bizonyítása.

3. Gallai-azonosságok. Páros gráfok fogalma, karakterizációja.

4. Párosítás és teljes párosítás fogalma, Hall-tétel, Frobenius-tétel, Kőnigtétel.

5. Kromatikus szám fogalma és becslései a klikkszám, illetve, a maximális fokszám függvényében. Brooks tétele (biz. nélkül), Mycielski konstrukciója.

6. Élgráfok és színezésük. Kőnig tétele páros gráfok élszìnezéséről, Vizing tétele (biz. nélkül), síkgráfok színezése, ötszíntétel.

7. Perfekt gráfok, perfektség bizonyítása nevezetes speciális esetekben: páros gráfok, ezek komplementere, páros gráfok élgráfja, ezek komplementere, összehasonlítási gráfok.

8. Perfekt gráf tétel, Lovász erősebb tétele (biz. nélkül), erős perfekt gráf tétel (biz. nélkül). Mantel és Turán tételei.

9. Hálózati folyamok, Ford-Fulkerson tétel, egészértékűségi lemma, maximális folyam keresése algoritmikusan, Edmonds-Karp tétel (biz. nélkül).

10. Menger-tételek, magasabb összefüggőség. PERT-módszer. Gráfok tárolása.

11. Oszthatóság, felbonthatatlan és prímszámok, legnagyobb közös osztó, euklideszi algoritmus. A számelmélet alaptétele, osztók száma és összege, nevezetes tételek prímszámokról.

12. Kongruencia fogalma, teljes és redukált maradékrendszer, φ−függvény, tulajdonságai, Euler-Fermat tétel, kis Fermat tétel.

13. Lineáris kongruencia megoldása, Wilson-tétel.

14. Csoport fogalma, ciklikus csoport, diédercsoport, szimmetrikus csoport, Cayley-tétel.

15. Részcsoportok, mellékosztályok, Lagrange tétele, elem rendjének viszonya a csoport rendjével.

16. Normálosztók, jellemzéseik, faktorcsoport, homomorfizmus-tétel.

17. Gyűrűk, testek, nevezetes példák, véges integritási tartomány test voltának bizonyítása, kvaterniók ferdeteste.

18. Aritmetikai algoritmusok bonyolultsága, prímtesztelés.

19. Nyilvános kulcsú titkosírások.