Jelenlegi hely

Az Informatika Doktori Iskola felvételi vizsga tematikája

Érvényes 2005-től

Automaták és nyelvek

Nyelvek és műveletek nyelveken. Reguláris nyelvek és véges determinisztikus és nemdeterminisztikus automaták. Környezetfüggetlen nyelvek és veremautomaták. A környezetfüggetlen nyelvek zártsági tulajdonságai. A pumpáló lemma és nem környezetüggetlen nyelvek. A Chomsky hierarchia. Az általános nyelvtanok ekvivalenciája a Turing gépekkel. Környezetfüggő nyelvtanok és lineárisan korlátos automaták.

Kiszámíthatóság elmélete es algoritmusok bonyolultsága

Turing-gépek és változataik. A Turing gépek ekvivalenciája az egyéb számítási modellekkel. Church tézise. Rekurzív és rekurzívan felsorolható nyelvek. Eldönthetetlen problémák. Algoritmusok idő- és tárigénye. Idő és tárkorlátos Turing gépek. Bonyolultsági osztályok. Alapvető összefüggések az idő - és tárbonyolultsági osztályok között. A P és NP osztályok. NP-teljes problémák. A PSPACE osztály. Az L és NL osztályok.

Logika a számítástudományban

Az elsőrendű logika alapfogalmai. Normálformák. A Herbrand elmélet. Kompaktsági tétel. Az elsorendű logika eldönthetősége. Az elsőrendű logika rezolúciós kalkulusa. A logikai programozás alapjai.

Operációkutatás

Lineáris programozási feladat és kapcsolata a konvex poliéderekkel. A szimplex algoritmus különböző változatai. Dualitás. Egészértékű programozás. Hozzárendelési és szállítási feladatok. Nemlineáris programozás.

Számítógépes tanuláselmélet

Tudásreprezentáció, a PROLOG, a logikai programozás elméleti alapjai. Döntések, statisztikai döntések, Bayes-féle modell. Rendszerek paraméter-identifikációja, paraméterek meghatározása tanulással, optimalizálással, identifikáció. Genetikus algoritmusok elmélete, neurális hálózatok.

Számítógépes grafika

Grafikai primitívek, megjelenítésük, vágásuk. Területi primitívek kitöltése, vágása. Görbék és felületek, spline-ok. 3-D megjelenítés, takarás, árnyékolás, sugárkövetés.

Számítógépes képfeldolgozás

A képfeldolgozás alapjai: képfüggvény, képmátrix, mintavételezés, kvantálás. Képek transzformációja, szűrése, helyreállítása. Képek kódolása, leírása.

Mesterséges intelligencia

Problémamegoldás, megoldás-tér, problémaredukció, játékfák, keresési módszerek. Alakfelismerés, Bayes-döntések. Diszkriminancia függvények, veszteségfüggvény, Bayes hálók.

Programozási nyelvek, programok tervezése

Programozási paradigmák és ezek legfontosabb tulajdonságai. Assembly programozás. Imperatív programnyelvek, alprogramok, vezérlési struktúrák, típusok. Strukturált programok, alprogramok, modulok. Objektumorientált programozás alapelvei (C++, JAVA). Logikai programozás (Prolog). Funkcionális programozás. Párhuzamos programozás. UML alapú programtervezés.

Fordítóprogramok

A fordítás fázisai. Lexikális, szintaktikus és statikus szemantikai elemzés. Elméleti modellek (reguláris, környezet-független, attributum nyelvtanok ). Kódgenerálás. Kódoptimalizálás.

Számítógépes hálózatok

Hálózati architektúrák. A kommunikáló rendszerek alapeleme, a protokoll. Protokollok életciklusa. Internet protokollok. Az SDL leírónyelv. Hálózati alkalmazások.

Adatbázisok, Információs Rendszerek

Adatmodellezés, relációs adatmodell. Műveletek a relációs modellben. Normalizálás, normálformák. Az SQL adatbázisnyelv. Objektumorientált adatbáziskezelés. Osztott adatbáziskezelés. Az SSADM módszertan elemei.

Operációs rendszerek

Processzusok. Processzusok ütemezése, kommunikációja. Beviteli és kiviteli (I/O) alrendszer. Memóriagazdálkodás. Fájlrendszerek.