Jelenlegi hely

Az Informatika Doktori Iskola felvételi vizsga tematikája

Az Informatika Doktori Iskola felvételi vizsga tematikája

Érvényes 2018-tól

Algoritmusok és adatszerkezetek

Rendezési algoritmusok (kiválasztó, beszúró, kupacrendezés, gyorsrendezés). Bináris keresőfák. Problémamegoldó stratégiák (mohó algoritmusok, dinamikus programozás). Gráf-algoritmusok (szélességi és mélységi keresés, topologikus rendezés, erősen összefüggő komponensek, minimális feszítőfák, legrövidebb utak keresése).

Automaták és nyelvek

Reguláris nyelvek és véges automaták. Környezetfüggetlen nyelvek és veremautomaták. Pumpáló lemmák, zártsági tulajdonságok és eldöntési kérdések. A Chomsky hierarchia. Az általános nyelvtanok ekvivalenciája a Turing gépekkel.

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

Turing-gépek és ekvivalenciájuk egyéb számítási modellekkel. A Church-Turing tézis. Rekurzív, rekurzívan felsorolható és eldönthetetlen problémák. Algoritmusok idő- és tárigénye RAM vagy Turing-gépen. Nemdeterminizmus. Idő- és tárbonyolultsági osztályok, alapvető összefüggések. A P és NP osztályok, a Cobham-Edmonds tézis. Visszavezetések, teljesség, NP-teljes problémák. A PSPACE, L és NL osztályok.

Logika a számítástudományban

Az elsőrendű logika alapfogalmai. Skolem normálforma. A kompaktsági tétel. Rezolúciós módszer az elsőrendű logikában: ground rezolúció és elsőrendű rezolúció. 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.

Közelítő számítások

Hibafajták, a hibaszámítás alapfeladata, számábrázolás, kerekítés. Numerikus stabilitás, kondicionáltság. A lineáris egyenletrendszerek direkt és iteratív módszerei. Az utóbbiak konvergenciája. A konjugált gradiens módszer. A sajátértékek meghatározásának számítógépes eljárásai, LR módszer, hatványmódszer. Függvényközelítések, interpoláció, spline. Érintő-, szelő- és húrmódszer. Kvadratúra formulák, numerikus integrálás, véges differenciák. A kvadratúra formulák pontossági rendje. Numerikus derivált, automatikus differenciálás, intervallum aritmetika.

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. Éldetektálás, sarokpontok és pontmegfeleltetések, szegmentálás, regisztráció.

Mesterséges intelligencia

Problémamegoldás, megoldás-tér, informálatlan és informált keresés (A*). Játékfák, keresési módszerek, minimax algoritmus, alfa-béta vágás. Heurisztikus optimalizálás: evolúciós módszerek, szimulált hűtés.

Gépi tanulás

Az induktív tanulás alapproblémaja, változatai: felügyelt tanulás, felügyelet nélküli tanulás, megerősítéses tanulás. Döntési fák. Statisztikai tanulás, naiv-Bayes, Bayes hálók. Lineáris modellek (SVM, logreg). Folytonos tanuló algoritmusok, veszteségfüggvény, sztochasztikus gradiens módszer. Dimenziócsökkentés, klaszterezés, komplex hálozatok bányászata. Mesterséges neurális hálózatok, konvolúciós hálózatok.

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.

Jelek és rendszerek

A jel, mint információhordozó. Egydimenziós jelek ortogonális transzformációja. A jel spektruma, a mintavételezés hatása a jel spektrumára. Idősorok vizsgálata FFT segítségével. A jel energiája és teljesítménye. Az LTI rendszerek leírása idő, frekvencia és operátortartományban. Tipikus tagok (P, D, I, PT1, PT2) jellemzői. Valós szűrők frekvenciaátviteli karakterisztikái, a Bode diagram. A Tustin transzformáció. Diszkrétidejű rendszerek IIR és FIR alakok.

Irányítástechnika

A szabályozási kör hatásvázlata. A szabályozásokkal szemben támasztott minőségi követelmények. A stabilitás fogalma és vizsgálata, stabilitási kritériumok. Az ideális és a valós PID szabályozó, a valós PID szabályozó diszkrétidejű megvalósítása. PLC-k hardver felépítése és működése.

Rendszerelmélet

Elérhetőség, irányíthatóság, megfigyelhetőség és rekonstruálhatóság. Kalman-felbontás, kanonikus alakok. Pólusáthelyezés állapotvisszacsatolással. Minimálisrendű állapotmegfigyelő. Nemlineáris rendszerek stabilitása, Ljapunov módszerek, La Salle-tétel. Csúszó szabályozás.

Intelligens rendszerek

A fuzzy irányítási rendszerek felépítése. A Mamdani féle fuzzy irányítás. A Takagi-Sugeno féle fuzzy irányítás. A neurális hálózatok helye és szerepe az intelligens rendszerekben. A neurális hálózat mint univerzális approximátor, Hibavisszaterjesztés algoritmusa. Genetikus algoritmus működése és szerepe az intelligens rendszerek fejlesztésében.

Beágyazott rendszerek

Beágyazott rendszerek felépítése. Analóg és digitális komponensek, szenzorok, aktuátorok, jelkondicionálás, adatkonverterek, processzorok, perifériák. A beágyazott szoftverfejlesztés elvei, eszközei. Valós idejű rendszerek, folyamatok, operációs rendszerek.

Méréstechnika és jelfeldolgozás

Méréselméleti alapok, műszerek felépítése, tulajdonságai. Digitalizálás, analóg jelek mintavételezéses mérése. Digitális jelfeldolgozás, mintavételezett jelek spektrális analízise, időfüggő spektrális analízis, konvolúció és dekonvolúció. Digitális szűrők. Digitális jelszintézis. Lock-in méréstechnika, moduláció és demoduláció. Adatgyűjtő rendszerek, szoftver-definiált műszerek.

felveteli_tematika_2018-v3.pdf