ÜTEMTERV

Algoritmusok és vizsgálatuk c. tárgyhoz (GEMAK121M)

Mérnök informatikus mesterszak számára

Óraszám: heti 3+1, (aláírás+kollokvium, 5 kredit)
2009/10-es tanév I. félév.

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

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

3. hét: Egyetemi Sportnap

4. hét: Algoritmikus eldönthetőség. Szimuláció fogalma, szimulációs tételek. Gödel-tétel, Church-tézis. Rekurzív és rekurzívan felsorolható nyelvek, rekurzív illetve parciálisan rekurzív függvények. Nevezetes nyelvek (Az R, Re, coR, coRE nyelvosztályok és ezek kapcsolata) és bonyolultságuk.

5. hét: Néhány algoritmikusan eldönthetetlen probléma. Idő és tárkapacitásos- univerzális Turing-gépek fogalma. Idő-tár tétel. A Turing gép időigénye. A Turing kiszámíthatóság, Church-Turing tézis. 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. 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, 2009. szeptember 3.

(Dr. Házy Attila)

a tárgy jegyzője