Ü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)
2012/13-as 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:     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. 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 tanú-tétel.

7. hét:     Nemzeti ünnep

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

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

10. hét:   NP-teljesség, Cook-tétel. Néhány NP-teljes probléma, 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 tartalmazhatnak.

• 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, 2012. szeptember 3.

(Dr. Házy Attila)

a tárgy jegyzője