Mesterséges intelligencia

Levelező informatika tanár szak

Vizsgakérdések
2005.


  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.)
  1. Mit nevezünk állapottér reprezentációnak?
  2. Hogyan feleltethető meg egy állapottér reprezentációhoz egy gráf reprezentáció?
  3. Mit nevezünk delta-gráfnak?
  4. Milyen komponensei vannak egy kereső (más néven produkciós) rendszernek?
  5. Mit nevezünk optimális megoldásnak?
  6. Csoportosítsd a keresőrendszerek vezérlési stratégiáit!
  7. Definiáld a visszalépéses keresőrendszert!
  8. Milyen esetekben kell a visszalépés műveletét alkalmazni a visszalépéses keresés során?
  9. Visszalépéses keresés esetén hol van szerepe a heurisztikák alkalmazásának?
  10. Add meg a visszalépéses keresés rekurzív algoritmusának első változatát!
  11. Miben tér el a visszalépéses keresés algoritmusának első és második változata?
  12. 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?
  13. Mit nevezünk keresőgráfnak, illetve optimális feszítőfának?
  14. Mikor kerül a gráfkeresés során egy csúcs a NYÍLT halmazba?
  15. Mi alapján választunk ki egy csúcsot kiterjesztésre a gráfkeresés során?
  16. Add meg a gráfkeresés algoritmusát !
  17. 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!
  18. Mondd ki a gráfkereső algoritmusra vonatkozó "invariáns" lemmát!
  19. 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?
  20. Miként definiáljuk a h heurisztikus függvényt? Mit jelent a h* függvény?
  21. Melyek a neminformált gráfkereső algoritmusok?
  22. Mit nevezünk A algoritmusnak, és milyen tétel módható ki róla?
  23. Mit nevezünk A* algoritmusnak?
  24. 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?
  25. Mit nevezünk Ac (következetes) algoritmusnak?
  26. Jellemzed a következetes algoritmust! (Milyen tételek mondhatók ki róla?)
  27. 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.)
  28. Bizonyítsd be, hogy a következetes algoritmus egyben A* algoritmus!
  29. Bizonyítsd be, hogy az A* algoritmusok halmaza bővebb, mint az Ac algoritmusok halmaza! (Adj egy megfelelő példát!)
  30. Sorold fel a teljes információjú kétszemélyes játékok jellemzőit!
  31. 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?
  32. Mi a játékgráf, illetve játékfa?
  33. Hogyan kell meghatározni egy nyerő stratégiát a játékgráf megcímkézésével?
  34. Hogyan választunk lépést a minimax algoritmussal?
  35. Miként alkalmazható a minimax algoritmus nyerő startégia meghatározására teljes játékfa esetén?
  36. Mit nevezünk alfának az alfa-béta algoritmusban, és mi az alfa-vágás?
  37. Mit nevezünk bétának az alfa-béta algoritmusban, és mi a bétavágás-vágás?
  38. Mit nevezünk atomi formulának 0-ad rendű logikában?
  39. Mit nevezünk termnek első rendű logikában?
  40. Mit nevezünk atomi formulának első rendű logikában?
  41. Mikor érvényes, kielégíthető, illetve kielégíthetetlen egy logikai formula?
  42. Mikor nevezünk ekvivalensnek két logikai formulát?
  43. Definiáld két klóz rezolvensét 0-ad rendű logikában!
  44. 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.)
  45. Mit nevezünk konjunktív normál formának (KNF)?
  46. Add meg a rezolúció alap algoritmusát!
  47. Hogyan kell egy 0-ad rendű logikai formulát KNF-re alakítani? (Milyen lépésekben történik az átalakítás?)
  48. Add meg a kvantorok szemantikus jelentését!
  49. Mely azonosságokkal csökkenthető elsőrendben a negáció hatásköre!
  50. Hogyan alkalmazzuk logikai tételek bizonyítására a rezolúciót?