Számítástudomány eloadás

Péntek 12:10-13:40 Északi Tömb 1.71 Pócza Jeno terem

Vizsga

Péntekenként 9:00-tol Déli Tömb 3-607-ben

Idei Tételsor: pdf
A vizsga menete: Eloször két beugró feladat, egy nyelvrol meg kell mondani, hogy reguláris-e és két bonyolultsági osztályról a defjüket, viszonyukat. Ha egyik sem megy, egyes. Ha egyik megy, másik helyett adok újat, ha az sem megy, egyes. Ezután kezdodik a tételhúzás, egyet kell kidolgozni, de persze többibol is kérdezhetek ezt-azt.

Hasznos linkek:

Eloadáshoz kapcsolódó legfrisebb jegyzet: .pdf Kommentelos verzió: .html
Tavalyi eloadás: .html Hetenkénti várható téma: .html
Gyakorlatok: Dani Sanyi Tamas
Turing eredeti cikke: .html Alapveto bonyolultsági osztályok: .html Turing-gép szimulátor: .html
Ajánlott olvasmányok: Christos H. Papadimitriou: Számítási bonyolultság, Sanjeev Arora és Boaz Barak: Computational Complexity: A Modern Approach .html
Egyéb kapcsolódó ismeretterjeszto könyvek: Raymond Smullyan könyvek, pl.: To Mock a Mockingbird, Roger Penrose: A császár új elméje, Douglas L. Hofstadter: Gödel, Escher, Bach

Órák témái:

1. óra (febr. 15): Turing, Turing-gep def, Univerzalis T-gep letezese
2. óra (febr. 22): Tobbszalagos gep szimulalasa Egyszalagossal, RAM-gep def es ekvivalenciaja T-geppel
3. óra (marc. 1): Eldonthetetlenseg, Domino-problema defje es kiparkettazhatatlansagos lemma
4. óra (marc. 8): Domino-problema eldonthetetlensege, Tar es ido alapok, Linearis gyorsitas
5. óra (marc. 22): P, EXP, PSPACE es viszonyuk, Idohierarchia, Nemdeterminizmus, Tanu
6. óra (apr. 5): NP, NPSPACE es viszonyuk det osztalyokhoz, NP-beli nyelvek
7. óra (apr. 12): NP-teljesseg, SAT, Cook-tetel
8. óra (apr. 19): Lefogási, Lefedési és Partíció feladat, 3COL, Független ponthalmaz, Részletösszeg probléma
9. óra (apr. 26): RND algok es osztalyok, Poliazonossag es kovetkezmenyek, Alprim def es primteszteles nem alprim esetben
10. óra (maj. 3): Prímtesztelés, Grafizomorfizmus problema, Interaktiv protokollokrol mese, One-time pad, Nyilvanos kulcsu kripto celja