ÜTEMTERV

Algoritmusok és vizsgálatuk c. tárgyhoz (GEMAK121M, GEMAK234-B)

Mérnök informatikus (mesterszak) és Programtervező informatikus (alapszak)

hallgatók számára

Óraszám: heti 2+2, (aláírás+kollokvium, 5 kredit)
2022/23-as tanév I. félév.

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

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: 1. zárthelyi dolgozat megírása.

7. hét: Nemdeterminisztikus algoritmusok, nemdeterminisztikus Turing gépek, Az NP és a coNP nyelvosztály.

8. hét: Példák NP-beli nyelvekre. A tanú-tétel.

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: 2. zárthelyi dolgozat megírása.

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

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 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, 2022. szeptember 7.

(Dr. Házy Attila)

 a tárgy jegyzője