2011.ősz, levelező:
HÁZI FELADATOK:
1. házi feladat - BEADÁSI HATÁRIDŐ* : NOVEMBER 12.
2. házi feladat - BEADÁSI HATÁRIDŐ* : DECEMBER 2.
3. házi feladat - BEADÁSI HATÁRIDŐ* : DECEMER 16.
Gyakorló feladatsor a vizsgához
kódja/kódjai: IBL154, IBL602
Felelős előadó: Dr. Dombi József
Felelős tanszék: Számítógépes Algoritmusok és Mesterséges Intelligencia
Levelező tagozat:
- Előadás: összesen 12/16 óra 4/6 kredit. Teljesítés módja: Kollokvium.
- Gyakorlat: összesen 6/8 óra 0 kredit. Teljesítés módja: Aláírás.
A kurzus felvételének előfeltételei: lásd a tanrendben.
Az oldal tartalma:
- Tematika
- Ajánlott és kiegészítő irodalom
- A kurzus teljesítésének feltételei
- Kötelező program
- Előadás anyaga Segédanyagok
Tematika
A mesterséges intelligencia fogalma, részterületei. A mesterséges intelligencia alapjai, története. A gyenge és az erős MI. Problémák megoldása egy ügynök (ágens) segítségével. Intelligens ügynök. Néhány egyszerű, mesterséges intelligenciához tartozó feladat.
Feladatreprezentáció állapottérrel: állapottér reprezentáció gráffal, a reprezentációs gráf fává alakítása.
Produkciós rendszer és a heurisztika: produkciós rendszer komponensei Heurisztika alkalmazása, a heurisztika fogalma, a heurisztika és a megoldás költsége, előre és visszafelé haladó működés.
Vezérlési stratégiák: Nem módosítható vezérlési stratégiák, visszalépéses vezérlési stratégia, gráf kereső vezérlési stratégia, Informálatlan és heurisztikus keresések:
- Nem informált kereső eljárások. Szélességben (depth first)/mélységben (breadth first) először, egyenletes költségű keresés. Mélységkorlátozott, iteratívan mélyülő keresés. Kétirányú keresések. Ismételt állapotok elkerülése. Kényszerek kielégítése.
- Heurisztikus keresések: legjobbat először (best fit) keresés. Az A és az A* algoritmusok, legfontosabb tulajdonságaik. Az informáltság fogalma és következményei. Monotonitás. Memóriakorlátozott keresés. Iteratívan javító algoritmusok.
Feladatmegoldás problémaredukcióval. ÉS/VAGY gráfok. Keresés és vagy gráfokon.
Kétszemélyes játékok: Grundy Tac-Tix, amoba, NIM.Hex, Othello.
A teljes játék-fa kiértékelése: A kétszemélyes játékok reprezentációja gráffal, nyerő stratégia létezése és meghatározása, nyerő stratégia meghatározása ÉS/VAGY fával.
A játékfa részleges kiértékelése: minimax eljárás az alfa-béta nyesés. Néhány játékprogram elemzése. Véletlen elemet is tartalmazó játékok.
Bizonytalansággal terhelt problémák. A statisztikus alakfelismerés alapfogalmai: a Bayes tétel használata. Bayes hálózatok. Időbeli folyamatok. Valószínűség alapjai, Alakfelismerés problémája. Veszteség függvény, Diszkriminancia függvény. ROC görbe. Bizonytalanság melletti következtetések. Bayes hálók. Percepton tanulása.
Egyszerű döntések meghozatala.
Automatikus tételbizonyítás.
Tételbizonyítás az ítéletkalkulusban: szintaxis és szemantika, a kielégíthetőségi tulajdonság, formulák ekvivalenciája, logikai következmény, a tételbizonyítás néhány módszere, Quine-, Wang algoritmusa, formális levezetés, konjunktív normálforma, rezolúció.
Elsőrendű logika alapfogalmai: szintaxis és szemantika, termek, atomi mondatok, összetett mondatok, kvantorok. A kielégíthetőségi tulajdonság. Ekvivalencia. A logikai következmény. A formulák klóz alakja. Az egyesítési algoritmus. Rezolúció.
A rezolúció hatékonyságának növelése: rezolúciós stratégiák, szélességi keresés, támogató halmaz stratégiája, lineáris input stratégia, ősre korlátozott stratégia, egységklóz stratégia, bináris rezolúció, egyszerűsítő stratégiák.
A kurzus teljesítésének feltételei
A kurzusok teljesítéseinek értékelése pontozás alapján történik. Maximálisan összegyűjthető pontszám 100, amelyből a gyakorlaton 40-et, a vizsgán 60-at lehet megszerezni.
A gyakorlat teljesítésének (az aláírás megszerzése) feltételei:
- A gyakorlaton szerezhető maximális pontszám: 40 pont.
- Ebből legalább 20 pont szükséges a gyakorlat teljesítéséhez.
A gyakorlati pontszám a következőkből tevődik össze:
- Időközönként házi feladatok kerülnek kiosztásra. Ezek megoldását a feladatokhoz rendelt határidőkre kell benyújtani. A helyes megoldásokért a hallgató megkapja az adott feladatra járó pontot (a feladat pontértéke annak nehézségétől függ). A feladat megoldásoknak önálló munkáknak kell lenni, a közösen készült megoldások írói vizsgára nem bocsáthatók. A feladat megoldások csak papíron, kézzel írottan fogadhatók el. A feladatok beadása nem halasztható, utólagos pótlása, javítása nem megengedett. A feladatok 50%-át teljesíteni kell. Elérhető pontszám: 5 pont.
- A szorgalmi időszak végén egyeztetett időpontban egy zárthelyi dolgozat megírására kerül sor. A dolgozat során minimálisan 7 pont elérése kötelező a maximálisan szerezhető 15 pontból. A dolgozat megírása kötelező. A sikeres dolgozat nem javítható. Sikertelen dolgozat a kihirdetett időpontban javítható. A legalább 30%-ra megírt javító dolgozat minősül sikeresnek. Ebben az esetben azonban az eredeti dolgozat pontszámát viszi tovább vizsgára a hallgató függetlenül a javító dolgozatban elért pontszámtól.
- A hallgatóknak egy programozási feladatot is kell megoldani ennek két leadási határideje (mérföldkő) van. Az első fázisban 5 pontot lehet elérni, amennyiben az első fázis sikertelen, akkor a 2. fázisban nem vehet részt a hallgató. A 2. fázisban a feladat megoldásának jósága függvényében 10 pont adható.
- Csak az a hallgató vizsgázhat az ETR-ben meghirdetett vizsganapokon, aki a gyakorlatból a minimum 20 pontot megszerezte.
A vizsga (kollokvium) teljesítésének feltételei:
- A vizsga írásbeli. A maximális pontszám 60. A vizsga sikeres, ha a hallgató 30 pontot elért a 60-ból és az összpontszáma 50 felett van. A vizsgán +5 pont szerezhető, az alábbi könyv adott fejezeteinek elolvasása esetén, ha a vizsgán ezekre a fejezetekre vonatkozó kérdésekre helyesen válaszol a hallgató.
- Steven Pinker: Hogyan működik az elme (1-2. fejezet)
A kollokvium érdemjegyének meghatározása a gyakorlaton és a vizsgán a fenti feltételeket kielégítő szerzett pontok összege alapján történik a következő ponthatárok szerint:
- 0 - 50 pont : elégtelen (1)
- 51 - 60 pont : elégséges (2)
- 61 - 80 pont : közepes (3)
- 81 - 90 pont : jó (4)
- 91 - 100 pont : jeles (5)
A vizsgáról való igazolatlan hiányzás a TVSZ. 17.§ (6) szabályozásának megfelelően elégtelen jegyű vizsgának minősül. Vizsgáról való hiányzás igazolását köteles a hallgató a hiányzást követő legelső vizsgáját megelőzően bemutatni.
Kötelező program
A kötelező program azonos a nappali tagozatosok számára meghirdetett feladattal. A feladat kiírása megtalálható Jelasity Márk honlapján. A nappali tagozatos gyakorlatvezetők kezelik a Bíró rendszert. Minden további információért hozzájuk kell fordulni. (Ormándi Róbert, Gulyás Gergely...)
A feladat az Othello (más neveken Reversi, Fonákollós, Színcserélő) játék egy változatát játszó ágens írása. A feladatot Java nyelven kell teljesíteni. Az implementáció során egy Java interfészt kell implementálni, amelyet az ágenst automatikusan kiértékelő rendszer fog használni. Az interfész, dokumentáció, példa ágensimplementációk, valamint a kiértékelő innen letölthető. Figyelem: a lent megadott időpontig a kiírás némileg változhat! Az archívumban az OLVASSEL.txt nevű fájl tartalmazza a részletes információkat a beadással kapcsolatban.
A játékot egyik oldalán világos, a másikon sötét korongokkal játszuk. Az egyik játékos színe a világos, a másiké a sötét. Sötét kezd. A játék célja, hogy a saját színű korongokkal a lehető legtöbb mezőt foglaljuk el a táblán, az ellenfél korongjainak közrefogásával és átfordításával.
A tábla hagyományosan egy 8x8-as szabályos négyzetrács. A mi esetünkben azonban a tábla alakja szabálytalan, dinamikusan véletlenül generált, azaz minden egyes játék során más lehet (játék közben már nem változik). A tábla egy 10x10-es négyzetrácsból keletkezik úgy, hogy bizonyos mezőket kivágunk. A belső 4x4-es terület azonban mindig hiánytalanul megmarad. Az ábra egy lehetséges táblát szemléltet, a kezdőállással együtt (kék: kivágott mezők). A kezdőállás is mindig az ábrán illusztrált állás.
A pontos szabályok a következők.
1.A kezdőállást a mellékelt ábra szemlélteti.
2.A játékosok felváltva helyeznek korongokat a saját színükkel felfelé a tábla valamely szabad mezőjébe, sötét kezd.
3.Közrefogáson azt értjük, hogy a lehelyezett korong vízszintes, függőleges vagy átlós irányban egy vonalban van egy másik, saját színű koronggal, és közöttük megszakítás nélkül csak az ellenfél korongjai vannak.
4.Csak olyan mezőbe helyezhető korong, ahol az ellenfél legalább egy korongját az éppen lehelyezett korong és valamelyik, a táblán lévő, saját színű korong közrefogja.
5.Minden, a lehelyezéssel közrefogott korongot át kell fordítani, minden irányban.
6.Ha egy játékos nem tud lépni, akkor megint a másik játékos jön. De ha tud lépni (azaz van lépés ami eredményez átfordítást) akkor kötelező lépni.
7.A játéknak akkor van vége ha egyik játékos sem tud lépni. A végeredmény a táblán levő korongok megszámolásával adódik.
További speciális szabályokról és feltételekről a kiadott csomag dokumentációja is rendelkezhet. Kérdések esetén a fórum használata javasolt: http://www.inf.u-szeged.hu/rgai/forum/.
A menetrend a következő:
október 31. A csomag ami tartalmazza az interfészeket és egyéb osztályokat a programozáshoz, véglegessé válik. Kisebb hibajavítások még lehetnek, amikről itt információkat közlünk.
november 14. Megnyílik a lehetőség a programok beadására a BÍRÓ-ban.
november 28. Eddig a napig (beleértve ezt a napot) produkálni kell egy elfogadható verziót. Azaz ha eddig nem sikerült elfogadható verziót produkálni, ezután nincs több lehetőség, és a kötelező program sikertelen.
november 30. A második forduló kezdete, amelynek során korlátlan számú feltöltés áll rendelkezésre. Figyelem, új feladat lesz a BÍRÓ-ban, legalább egyszer tehát megint fel kell tölteni, akkor is ha az elfogadott program nem vátozik. Rangsor kerül kialakításra ami itt frissül.
december 12. Utolsó lehetőség a programok beadására akkor, ha valaki még versenyben van (azaz időben volt elfogadható verzió). A végső rangsor ezután alakul ki.
Vissza az oldal tetejéreAjánlott irodalom
- S. Russell, P. Norvig: Artificial Intelligence, A Modern Approach, Prentice Hall, 1995. Magyar fordítása: Mesterséges intelligencia modern megközelítésben, PANEM, 2000
- Mesterséges Intelligencia (Szerk. Futó Iván), Aula Kiadó, 1999
- Fekete I., Gregorics T., Nagy S.: Bevezetés a mesterséges intelligenciába, LSI Oktató Központ
Kiegészítő irodalom
- Barr, E. A. Feigenbaum: The handbook of Artificial Intelligence, I., Addison Wesley 1989
- E. Rich, K. Knight: Artificial intelligence, McGraw-Hill, 1991
- P. H. Winston: Artificial Intelligence, Addison-Wesley 1992
- M. Ginsberg: Essentials of Artificial Intelligence, Morgan Kaufman, 1993
- Mérő László: Új észjárások (Tercium kiadó 2001.)
- Dennett: Darwin veszélyes ideálja
- Steven Pinker: Hogyan működik az elme
Előadás anyaga
Fogadóóra: kedd 11-12, Árpád tér 2. 211 szoba.
Előadásjegyzet doc formátumban.
Russel-Norvig könyv Bizonytalanság és Bayes hálók rész pdf formátumban.
Fekete, Gregorics, Nagy: Bevezetés a mesterséges intelligenciába könyv logika rész pdf formátumban.
Utolsó módosítás: 2009. 10. 02.