A Számítástudományi szigorlat szóbeli részének rendje
2000 év őszi félév

1. A szigorlat tárgyai:
   
   
   1. Formális nyelvek és szintaktikus elemzésük,
   2. Bevezetés a bonyolultságelméletbe,
   3. Bevezetés a mesterséges intelligenciába,
   4. Fordítóprogramok.
   
   
2. A szóbeli szigorlat menete:
   
   A szigorlati jegyre a bizottság ajánlatot tesz, amely az 1.tárgyból letett kollokvium és a 2.,3. és 4. tárgyakból letett írásbeli elővizsgák jegyeinek kerekített átlaga. Ha az írásbeli elővizsgák valamelyikének eredménye elégtelen, akkor az átlag is elégtelen.
   
   Amennyiben a hallgató a megajánlott jegyet nem fogadja el vagy az elégtelen, szóbeli vizsga következik az előre kiadott tételek alapján. A hallgató abból/azokból a tárgyakból kap tételt és tesz szóbeli vizsgát, amelynek/amelyeknek az írásbeli/kollokviumi eredményét javítani szeretné.
   
   A szóbeli vizsga letétele után a bizottság az átlagot újra számolja és az így kapott átlag lesz a szigorlati jegy. Ha a szóbeli vizsgák valamelyikének eredménye elégtelen, akkor az átlag is elégtelen.
   
   
   
3. Általános szabályok:
   
   
   
   • Szóbeli szigorlat napjai: január 8,10,15,17,22,24
   • Egy szigorlati napra legfeljebb 35-en jelentkezhetnek.
   • Szóbeli szigorlat kezdete: 8 óra.
   • Csak az szigorlatozhat aki arra írásban jelentkezett és akinél nála van a leckekönyve.
   • Szóbeli szigorlatot halasztani csak indokolt esetben és legkésőbb a szigorlatot megelőző napon lehet.
   • Egy másik napra a szóbeli szigorlat csak akkor halasztható el, ha arra a napra a létszám még nem telt be.
   • A szigorlattal kapcsolatos kéréseket emailben csak kivételesen indokolt esetben fogadunk el.

Szigorlati tematika a szóbeli vizsgához a

Bevezetés a bonyolultságelméletbe
tárgyhoz.

1. Polinom idejű algoritmus az elérhetőség és maximális folyam problémára.
2. Idő és tárkorlátos Turing gépek. Lineáris felgyorsítás és a tár lineáris összehúzása.
3. Univerzális Turing gép és a megállási probléma. Összefüggések a rekurzív és rekurzívan felsorolható nyelvek között.
4. Néhány nevezetes eldönthetetlenségi eredmény.
5. Megengedett bonyolultsági függvények és bonyolultsági osztályok. Alapösszefüggések bonyolultsági osztályok között. Az L, NL, P, NP, PSPACE és EXP osztályok. Hierarchia tételek.
6. Savitch, valamint Immerman és Szelepcsényi tételei.
7. A visszavezetés fogalma és alaptulajdonságai. Visszavezetések az elérhetőségi probléma, a hálózat kiértékelés, a hálózat kielégíthetőség és a SAT problémák között.
8. Teljesség. A hálózat kiértékelés P-teljessége. Cook tétele. A 3SAT NP-teljessége.
9. Néhány NP-teljes gráfelméleti és egyéb probléma.
10. A coNP osztály és a prímtesztelés.
11. Az L és NL, valamint a PSPACE osztályok. NL-teljes es PSPACE-teljes problémák.

Formális nyelvek és szintaktikus elemzésük

1. Generatív nyelvtan és a véges automata fogalma. Alapvető összefüggések.
2. A reguláris kifejezések, a 3típusú nyelvek és az automatával felismerhető nyelvek ekvivalenciája.
3. Pumpáló lemma reguláris nyelvekre és a reguláris nyelvek osztályának zártsági tulajdonságai (reguláris műveletek, Boole műveletek).
4. Környezetfüggetlen nyelvek levezetési módjai (általános, bal-- és jobb oldali) és ezek kapcsolata. Derivációs fa fogalma, levezetések és derivációs fák közötti kapcsolatok.
5. Veremautomata fogalma, különböző felismerési módok, a környezetfüggetlen nyelvek és a veremautomaták ekvivalenciája.
6. Pumpáló lemma környezetfüggetlen nyelvek osztályának zártsági tulajdonságai (reguláris műveletek, Boole műveletek).
7. Az általános felülről lefelé haladó elemzési algoritmus.
8. Az LL(k) és az erősen LL(k) nyelvtan definíciója. Az erősen LL(k) nyelvek elemzése.
9. Az általános alulról felfelé haladó elemzési algoritmus.
10. Az LR(k) nyelvtan definíciója és elemzési algoritmusa.

Mesterséges Intelligencia

1. MI definíciói, részterületei. Néhány példa MI problémákra. Vízöntés feladat.
2. Informálatlan keresések; szélességben először keresés, mélységben először keresés.
3. Keresőprogramok megvalósításának kérdései, heurisztikus keresések, hegymászó algoritmusok.
4. A* algoritmus és tulajdonságai (bizonyításokkal).
5. Jobban informáltság fogalma, következménye.
6. Monotonitás fogalma, következménye.
7. És/vagy gráfok, címkézésük. Játékfák, kiértékelésük.
8. Alakfelismerés problémája.
9. Tudásábrázolási alaptechnikák.
10. Következtetések, rezolúció.

Fordítóprogramok tételek

1. A fordítóprogramok fő részei, lexikális elemzés.
2. Attributum nyelvtanok definíciója.
3. Attributum kiértékelés, L-attributum nyelvtan.
4. Többmenetes kiértékelők, ASE.
5. Egyszerű értékadó utasítás típus ellenőrzése.
6. OAG definíció.
7. Attributum nyelvtanok osztályozása.
8. OAG implementáció.
9. Kódgenerálás.
10. Optimalizálás.