A vizsga időpontja:2005. december 1., 10 óra, Északi tömb Harmónia terem
Az alábbi kérdések közül kell majd 15-re röviden válaszolni. Az eredményes
vizsgához legalább 40 pontot el kell
érni a 75-ből. (Egy kérdés 5 pontot ér.)
Mit nevezünk állapottér reprezentációnak?
Hogyan feleltethető meg egy állapottér reprezentációhoz
egy gráf reprezentáció?
Mit nevezünk delta-gráfnak?
Milyen komponensei vannak egy kereső (más
néven produkciós) rendszernek?
Mit nevezünk optimális megoldásnak?
Csoportosítsd a keresőrendszerek vezérlési
stratégiáit!
Definiáld a visszalépéses keresőrendszert!
Milyen esetekben kell a visszalépés műveletét
alkalmazni a visszalépéses keresés során?
Visszalépéses keresés esetén hol van szerepe a heurisztikák alkalmazásának?
Add meg a visszalépéses keresés rekurzív algoritmusának
első változatát!
Miben tér el a visszalépéses keresés algoritmusának
első és második változata?
Miként definiáljuk a gráfkeresés során a g költségfüggvényét? Mit
jelent a g* függvény?
Mit nevezünk keresőgráfnak, illetve optimális
feszítőfának?
Mikor kerül a gráfkeresés során egy csúcs a NYÍLT halmazba?
Mi alapján választunk ki egy csúcsot kiterjesztésre a gráfkeresés során?
Add meg a gráfkeresés algoritmusát !
Bizonyítsd be, hogy ha létezik célcsúcs egy
véges reprezentációs gráfban, akkor a gráfkereső algoritmus egy célcsúcs
megtalálásával terminál!
Mondd ki a gráfkereső algoritmusra vonatkozó "invariáns" lemmát!
Mi a küszöbcsúcs? Csökkenő kiértékelő függvény használatakor, mi teljesül a
küszöbcsúcsok kiterjesztésekor?
Miként definiáljuk a h heurisztikus függvényt? Mit jelent a h*
függvény?
Melyek a neminformált gráfkereső algoritmusok?
Mit nevezünk A algoritmusnak, és milyen tétel módható ki róla?
Mit nevezünk A* algoritmusnak?
A* algoritmus esetén milyen állítás mondható
ki egy n kiterjesztendő csúcs f(n) értékére? Mi az állítás következménye?
Mit nevezünk Ac (következetes) algoritmusnak?
Jellemzed a következetes algoritmust! (Milyen tételek mondhatók ki róla?)
Bizonyítsd be, hogy az egyenletes keresés egy csúcsot csak egyszer terjeszt
ki! (Felhasználhatók a nevezetesek algoritmusokra kimondott állítások.)
Bizonyítsd be, hogy a következetes algoritmus egyben A* algoritmus!
Bizonyítsd be, hogy az A* algoritmusok halmaza bővebb, mint az Ac
algoritmusok halmaza! (Adj egy megfelelő példát!)
Sorold fel a
teljes információjú kétszemélyes játékok jellemzőit!
Mit nevezünk nyerő stratégiának egy teljes
információjú kétszemélyes játék esetén, és milyen tétel mondható ki vele
kapcsolatban?
Mi a játékgráf, illetve játékfa?
Hogyan kell meghatározni egy nyerő stratégiát
a játékgráf megcímkézésével?
Hogyan választunk lépést a minimax algoritmussal?
Miként alkalmazható a minimax algoritmus nyerő startégia meghatározására
teljes játékfa esetén?
Mit nevezünk alfának az alfa-béta algoritmusban, és mi az alfa-vágás?
Mit nevezünk bétának az alfa-béta algoritmusban, és mi a bétavágás-vágás?
Mit nevezünk atomi formulának 0-ad rendű logikában?
Mit nevezünk termnek első rendű logikában?
Mit nevezünk atomi formulának első rendű logikában?
Mikor érvényes, kielégíthető, illetve kielégíthetetlen
egy logikai formula?
Mikor nevezünk ekvivalensnek két logikai formulát?
Definiáld két klóz rezolvensét 0-ad rendű
logikában!
Bizonyítsd be , hogy a rezolvens klózzal bővített
klózhalmaz kielégíthetőségi tulajdonsága nem változik! (Rezolúciós módszer
helyességét bizonyító tétel.)
Mit nevezünk konjunktív normál formának (KNF)?
Add meg a rezolúció alap algoritmusát!
Hogyan kell egy 0-ad rendű logikai formulát KNF-re alakítani? (Milyen lépésekben történik az
átalakítás?)
Add meg a kvantorok szemantikus jelentését!
Mely azonosságokkal csökkenthető elsőrendben a
negáció hatásköre!
Hogyan alkalmazzuk logikai tételek bizonyítására a rezolúciót?