ÜTEMTERV

Számításelmélet c. tárgyhoz (GEMAK234B)

BSc programtervező informatikus alapszak számára

Óraszám: heti 2+0, (aláírás+kollokvium, 3 kredit)
2007/08-as tanév I. félév.

Előfeltétel: legalább elégséges jegy

Adatstruktúrák és algoritmusok (GEMAK121B) tárgyból

1. hét: Számítási modellek. A Turing gép fogalma működése.

2. hét: Egyetemi Sportnap

3. hét: A RAM-gép. Boole-függvények és logikai hálózatok.

4. hét: Algoritmikus eldönthetőség. Gödel-tétel, Church-tézis. Rekurzív és rekurzívan felsorolható nyelvek. Nevezetes nyelvek és bonyolultságuk.

5. hét: Néhány algoritmikusan eldönthetetlen probléma. Idő-tár tétel. A Turing gép időigénye. Polinomiális idejű algoritmusok.

6. hét: Nemdeterminisztikus algoritmusok, nemdeterminisztikus Turing gépek, Az NP és a coNP nyelvosztály. Példák NP-beli nyelvekre. A tanu-tétel.

7. hét: Nemdeterminisztikus algoritmusok bonyolultsága.

8. hét: 1. zárthelyi dolgozat megírása.

9. hét: NP-teljesség, Cook-tétel. Néhány NP-teljes probléma

10. hét: Karp redukció, Cook-Levin tétel.

11. hét: Közelítő és randomizált algoritmusok. Prímtesztelés.

12. hét: Információs bonyolultság. A Kolmogorov bonyolultság és alkalmazásai. Az entrópia.

13. hét: 2. zárthelyi dolgozat megírása.

14. hét: A bonyolultság alkalmazásai. A kriptográfia alapfogalmai, az RSA-kód

15. hét: Párhuzamos algoritmusok. Párhuzamos bonyolultságelmélet.

A tárgy lezárásának módja: aláírás, kollokvium

Az aláírás feltétele:

• Az előadások felkészült, rendszeres látogatása.

• A félév során a két zárthelyi dolgozat (8. és 13. héten) legalább elégséges szintű megírása. A zárthelyi dolgozatok megírása mindenki számára kötelező. A zárthelyi dolgozatok elméleti kérdéseket (tételek, definíciók) illetve számolási feladatokat tartalmaznak.

• Ha valamelyik zárthelyi dolgozat nem sikeres, akkor azt az utolsó héten lehet pótolni a megfelelő tananyagrészekből. Ha ez sem sikeres, akkor a későbbiekben az egész féléves anyagból kell pótolni.

A vizsga írásbeli. A félévközi zárthelyi dolgozatok eredménye beleszámít a vizsgajegybe.

Meg nem engedett eszközök használata esetén a vizsga elégtelen és további vizsga abban a vizsgaidőszakban csak szóban, bizottság előtt, a tanszék által megadott időpontban lehetséges.

Miskolc, 2007. szeptember 4.

(Dr. Házy Attila)

a tárgy jegyzője