Azaz: (a) határozzuk meg a feladat állapotterét

(1)

1. Egy ember kecskét, farkast és káposztát szeretne átvinni egy folyón, de csak egy csónakot talál, amelybe rajta kívül csak egy tárgy fér. Hogyan tud a folyón úgy átkelni, hogy

(a) a farkas ne falja fel a kecskét, (b) a kecske ne egye meg a káposztát?

(bekövetkezne, ha ezek felügyelet nélkül együtt maradnának)

Reprezentáljuk a feladatot keresési feladatként. Azaz:

(a) határozzuk meg a feladat állapotterét;

(b) adjuk meg az elfogadható állapotokat;¹

(c) írjuk fel az operátorokat (műveleteket) és építsük fel a gráfot;

(d) határozzunk meg egy utat – azaz megoldást a feladatra.

2. Öten szeretnének egy hídon átmenni a sötétben. A híd egyszerre csak két embert bír meg és az átjutáshoz szükség van egy lámpára. Az öt részvevő sebessége különbözik: 1, 3,6,8, illetve 12 időegységre van szükségük ahhoz, hogy átjussanak a másik partra. Amennyiben ketten mennek a hídon, a haladási sebességük megegyezik a lassabban haladónak a sebességével.

Ha a lámpában harminc időegységre elegendő olaj van, keressünk egy módozatot arra, hogy mindenki átjusson.

(a) Határozzunk meg egy állapotteret a feladatnak.

(b) Írjunk egy algoritmust, mely talál megoldást.

3. Hatan szeretnének átmenni egy folyón, három kannibál és három misszionárius. Rendelkezésre áll egy csónak, mely legtöbb két embert bír el. A kannibálok csak akkor nem eszik meg a misszionáriusokat, ha nincsenek többen azoknál a folyó egyik partján.

Találjunk egy módszert arra, hogy mind a hatan átjussanak a másik partra.

(a) Határozzunk meg egy állapotteret a feladatnak.

(b) Írjunk egy algoritmust, mely talál megoldást.

4. Három korsónk van: egy nyolcliteres, egy ötliteres, illetve egy háromliteres - egyiken sincs szint- jelölés. A korsókat mérésre használjuk: egy edényt meg tudunk tölteni egy másik edényből, azonban addig kell töltsük a folyadékot (bort), ameddig az egyik edény megtelik vagy kiürül (például a teli háromliteres korsóból az üres ötliteresbe töltés során kiürítjük a kisebb korsót).

Feladat, hogy a teli nyolcliteres kancsóban levő folyadékot osszuk kettőbe: a nyolc- és ötliteres kancsókban legyen négy-négy liter folyadék.

(a) Határozzuk meg a feladat állapotterét;

(b) Írjuk meg a „töltögetés” szabályait: rögzítsük a feltételeket, melyekkel egy adott állapotban egyik korsóból a másikba lehet tölteni, illetve határozzuk meg azt, hogy mennyit.

(c) Írjunk egy kereső programot, mely adott számhármasra – a fentiekben ez (3, 5, 8) – talál egy lépés-sorozatot, mely a cél-állapotba visz. . (http://www.inf.unideb.hu/~jeszy)

5. Fedjünk le egy sakktáblát 21 darab 3×1-es téglával ( alakjuk ) úgy, hogy csak egy kocka maradjon üresen.

(a) Ábrázoljuk a feladatot: adjuk meg az állapotteret, a kezdőállapotot, valamint írjunk felté- telt a cél-állapotra.

(b) Írjunk egy függvényt (predikátumot), mely egy állapotból generálja a lehetséges lépéseket.

(c) Írjunk programot (predikátumot), mely talál egy megoldást.

(d) Keressünk megoldásokat, melyek a(8, 8)-as koordinátájú mezőt hagyják üresen.

1Javaslat: kizárással vagy logikai formulával.

(2)

(e) Ábrázoljuk grafikusan a megoldásokat. . (http://www.inf.unideb.hu/~jeszy)

6. Egy 2^N ×2^N méretű sakktáblát szeretnénk lefedni három négyzetből álló téglákkal, melyek háromszög alakúak a következő minta szerint:

(a) Bizonyítsuk be, hogy minden2^N×2^N tábla – egy négyzet üresen hagyásával – lefedhető a téglákkal (forgatás és transzláció felhasználásával).

(b) A hiányzó négyzet pozíciójának a függvényében adjuk meg a tábla egy lefedését.

(c) Vizsgáljuk meg, hogy egyedi-e a lefedés.

(d) Mennyire bonyolult egy szokványos Prolog visszalépő algoritmus? Keressünk egy jobb algoritmust!

7. A mellékelt ábrán egy sötét és világos mezőkből álló táblára egy csuklókkal összekapcsolt testré- szekből álló kígyót helyeztünk. A kígyó előre és hátra mozoghat (tehátnincs feje) egy mezőnyit.

Minden lépésben egy mezőn csak egy testrész (csukló) lehet. A kígyót úgy kell mozgatni, hogy a testének minden része sötét mezőkre kerüljön.

Az előző feladatokhoz hasonlóan építsük fel a feladat állapotterét; ír- junk függvényt, mely egy állapot összes következő állapotát megadja, majd generáljuk azt a lépés-sorozatot, mely a mellékelt állapotból olyan állapotba visz, ahol nincs a fehér mezőkön kígyó. Írjunk egy szimulátort, mely megjeleníti az eredményt.

. (http://www.inf.unideb.hu/~jeszy)

8. A mellékelt ábrán látható nyolc korongot kell csökkenő sorrendbe helyezni egymásra úgy, hogy csak az oszlop felső n korongját lehet mozgatni. A mozgatás azt jelenti, hogy felcseréljüka felső nkorong sorrendjét (aznlehet természetesen nyolc is).

(a) Határozzuk meg a feladat állapotterét.

(b) Írjunk függvényt, mely egy állapot összes kö- vetkező állapotát visszatéríti.

(c) Generáljuk a mellékelt állapotból a rendezett ál- lapotba vivő lépés-sorozatot. Keressük meg a legrövidebbet.

(d) Írjunk egy szimulátort, mely megjeleníti a lépé- seket.

3 4 1 7 28 56

8 76 5 4 3 2 1

9. Tekintsünk egy számsort, melyet egy körön helyeztünk el.

A kör mentén a számok növekvő sorrendbe vannak téve, a sorrend az óra járásával ellenkező. A számokat egyszerre négyesével tudjuk mozgatni, úgy hogy a négy szám egymás melletti. A mellékelt ábrán a[2, 1, 20, 19]számsort választot- tuk ki, ezt helyettesítjük a[19, 20, 1, 2]számsorral ugyanazon pozíciókon, balról jobbra.

Feladat: az egész számsort rendezzük növekvő sorrendbe, az irány egyezzen meg az óra járásával.

2 1 3 4 5 6 7

8 9 10 11 12 13

14 15 16 17 18 20 19

(a) Ábrázoljuk a feladatot: jelöljük ki a változókat.

(b) írjunk függvényt, mely teszteli azt, hogy jó-e a megoldás.

(c) Írjunk egy algoritmust, mely egy kezdő-pozícióból megkeresi azon lépéseket, melyekkel el tudunk jutni egy végső pozícióba.

(d) Írjunk egy szimulátort, mely megjeleníti a lépéseket.

(3)

10. Legyen a következő tudásbázis:

Fáradt =⇒ ¬Focizik Focizik =⇒ Egészséges

¬Egészséges =⇒ Fáradt

¬Focizik =⇒ ¬Szomjas

¬Szomjas =⇒ ¬Iszik Ismerve azt, hogyIszik, vezessük le, hogyEgészséges.

11. Adott a mellékelt gráf, melyben azA csomópontból szeretnénk eljutni a H csomópontba.

Írjuk fel a meglátogatott csomópontokat sorrendben, ha a ke- resési stratégia a

(a) szélességi keresés, és csomópontokat balról jobbra terjesz- tünk ki;

(b) szélességi keresés, és csomópontokat jobbról balra terjesz- tünk ki;

(c) mélységi keresés, és csomópontokat balról jobbra terjesz- tünk ki.

A

B C D

E F G H

I J

12. Adott a mellékelt gráf.

Milyen sorrendben járja be a mélységi keresési stratégiával aC- ből a I-t kereső algoritmus a gráfot, ha:

(a) A keresés során az azonos szinten lévő csomópontok kö- zül mindig a 12-től induló, óramutató járásával ellenkező irányba haladunk?

(b) Mi lesz a bejárási sorrend, ha az irányt az óramutató járá- sának megfelelőre változtatjuk?

(c) Írjuk fel a csúcsok bejárási sorrendjét, ha az I-ből az A- ba szeretnénk eljutni a szélességi bejárást és az óramutató járásával megegyező irányt használjuk.

A B D C

E F

G

H

I J K

L M

N O

13. Adott a mellékelt gráf.

Milyen sorrendben járja be a mélységi keresési stratégiával a B-ből a H-t kereső algoritmus a gráfot, ha a

(a) keresés során az azonos szinten lévő csomópontok kö- zül mindig a12-től induló, óramutató járásával ellenkező irányba haladunk?

(b) Mi lesz a bejárási sorrend, ha az irányt az óramutató járásának megfelelőre változtatjuk?

A

B C D

E F G H

I J

14. Írjuk fel a fenti gráf esetére a csúcsok bejárási sorrendjét, ha azI-ből azA-ba szeretnénk eljutni a szélességi bejárást és az óramutató járásával megegyező irányt használjuk.

(4)

15. Legyen a következő tudásbázis:

(a) Azangolnak piros házavan.

(b) Aspanyolnak kutyájavan.

(c) Ajapán detektív.

(d) Afrancia teátiszik.

(e) Afehér házazöld házjobb oldalán van.

(f) Aközépsőházbantejetisznak.

(g) Anorvégháza balról azelső.

(h) Asárga házadoktoré.

(i) Adoktorszomszédjánaklovavan.

(j) Azangolszomszédjaművész.

(k) Aművész szomszédjának rókájavan.

(l) Azügyvéd paradicsomlevetiszik.

(m) Amérnöknek macskájavan.

(n) Azöld házban kávétisznak.

(o) Anorvégházával szomszédos házkék.

Válaszoljunk a következő kérdésekre: (1)Ki iszik sört? (2) Kinek van zebrája?

A feladatban a mutatók legyenek a nemzetek nevei: [Angol, Japán, Norvég, Francia, Spanyol]. Ekkor minden entitáshoz tudunk rendelni egy házszínt, egy állatot, egy foglalkozást, valamint egy italt. A tények leírásához szükséges a szomszédsági kapcsolatoknak is a kódolása. Ugyanis abban az esetben, ha ismerjük egy-egyház pozícióját, a többi attribútumot meg tudjuk feleltetni egy-egy oszlopnak.

Egy megoldás tehát az, hogy a különböző helyek szerint végezzünk backtracking-et.

16. Formalizáljuk és oldjuk meg rezolúcióval Ásványi Tibor, ELTE

• A következő tények alapján:

– Ha süt a nap, akkor Péter strandra megy;

– Ha Péter strandra megy, akkor úszik.

– Péternek nincs lehetősége otthon úszni.

lássuk be, hogy ha süt a nap, akkor Péter nem marad otthon. (Miért kell a harmadik mondat?)

• Egy dolgozó elhatározásai

– ha nem emelik a fizetését, akkor elmegy a munkahelyéről máshová dolgozni, vagy kevesebb időt tölt bent és külön munkát vállal.

Kiderült, hogy sem a fizetését nem emelik, sem a munkaidejét nem tudja csökkenteni.

Lássuk be, hogy a dolgozó nem marad a munkahelyén.

• Ha János nem találkozott akkor éjjel Dénessel, akkor vagy Dénes a gyilkos vagy János hazudik. Ha nem Dénes a gyilkos, akkor János nem találkozott akkor éjjel Dénessel, és a gyilkosság éjfél után történt. Azonban ha a gyilkosság éjfél után történt, akkor Dénes gyilkos vagy János hazudik.

Helyes arra következtetnünk, hogy Dénes gyilkos?

• Nincs olyan autókereskedő, aki használt autót vásárolna a családjának. Vannak tehetős emberek, akik használt autót vásárolnak a családjuknak. Lássuk be, hogy van olyan tehetős ember, aki nem autókereskedő.

• Kockákból és gúlákból tornyokat építünk. Minden kockán van valamilyen test. Lássuk be, hogy minden kocka fölött van gúla.

17. Ábrázoljuk a következő szövegrészletet szemantikus hálókkal:

Az aorta egy 2.5cm átmérőjű artéria. Az artéria egy ér-típus. Egy érnek általában izomrostos fala van és általában 0.4cm átmérőjű. A véna is egy vérér-típus, azonban sima szövetes fallal.

Az erek mindig cső-szerűek és vér van bennük. Ez alól kivétel a nyirokér, mely nem vért, hanem nyirokfolyadékot szállít.

18. Ábrázoljuk a következő szövegrészletet szemantikus hálókkal:

A pázsitfűfélék családja az egyszikűek osztályának tagja, melyek nehezen rághatók és emészthe- tők. Ugyancsak a pázsitfűfélék családjába tartoznak a gabonafélék is, például a búza, árpa vagy a rizs. Ezen fűfélék többnyire egyévesek, de számos évelő faj is akad; ilyen például a bambusz.

(5)

19. Keressünk az ALFA-BETA vágással egy optimálisnak tűnő lépést a MAX játékos számára az alábbi játék-gráfban (magyarázzuk meg a döntést az aktuális α illetve β értékekkel mindegyik vágás esetén).

MAX

MIN

MAX

MIN

MAX 6 5 -1 3 -2 -4 5 8 3 7 9 2 -1 -2 -8 7

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17 18 19 20 21 22 23 24

25 26 27 28

29 30

Élek, ahol vágunk: 4,28

MAX

MIN

MAX

MIN

MAX 5 6 7 4 5 3 6 6 9 7 5 9 9 6

1 2 3 4 5 6 7 8 9 10 11 12 13 14

15 16 17 18 19 20 21 22 23

24 25 26 27 28 29

30 31 32

24 25 26 27 28 29

30 31 32

Élek, ahol vágunk: 5,9,29

(6)

MAX

MIN

MAX

MIN

MAX -3 6 2 -2 5

5 8 9 2 1 -1

5 -2 4 8

1 2 3 4 5

6 7 8 9 10 11 12 12

13 14 15 16 17 18 19

20 21 22

Élek, ahol vágunk: 2,3,10,19

22. Keressünk az ALFA-BETA vágással egy optimális lépést a MAX számára az alábbi játék-gráfban.

Magyarázzuk meg a vágásokat!

MAX

MIN

MAX

MIN

MAX 3 5 6 1 2 4

7 5 1 2 7 5 4 2

1 4

1 2 3 4 5 6

7 8 9 10 11 12 13 14 15 16

17 18 19 20 21 22

23 24

Élek, ahol vágunk: 5,6,10,11,21,22

23. Egyszerű kugli-játék. Az egyszerűsített kuglijátékban minden bábu (teke) egy sorban van elhelyezve, ez – közelítően – merőleges arra az irányra, ahonnan a kugligolyó érkezik. A golyó mérete akkora, hogy vagy egyszerre egy bábút vagy két szomszédosat képes leütni. Vesztes az a játékos, aki nem üt le – nem tud leütni – bábut.

Feladat:

(a) Határozzuk meg a játék állapotterétK =3bábúra;

(b) Határozzuk meg, hogy az kezdő játékos nyer vagy veszít.

(c) Számítsuk ki, hogy a kezdő játékos nyertes-eK =7bábú esetén.

(d) Írjunk programot, mely meghatározza, hogy a kezdő játékos nyer-e tetszőlegesK esetén.

(7)

24. Az amőba-játék Az amőba-játékban a feladatunk egy négyzetekből álló mezőre felváltva raj- zolni köröket és kereszteket úgy, hogy előbb nekünk gyűljön kiJ =5darab azonos jel egy sorban vagy egy átló mentén. Tegyük fel, hogy egy K×K méretű mezőn játszunk, ahol K > 4. Ha a K értéke nagy, akkor a játékot nem tudjukteljesen kiterjeszteni, közelítő becsléseket kell hasz- nálnunk. HaJ =K =3, akkor bizonyítható, hogy racionális játék során nem lesz győztes.

Feladatok:

(a) Implementáljuk az amőba játékot, ahol be tudjuk állítani a J és K értékeket, valamint tudjuk ellenőrizni, hogy egy állapotban egyik játékos nyert-e vagy mehet tovább a játék.

(b) A J =K=3 esetre implementáljuk a BOT játékost, aki racionálisan játszik.

(c) Implementáljuk az automata játékost a K = 4, J = 4 konfigurációra. Ezekre a paraméte- rekre a játékos kezdése mindig nyerést jelent. Ha mi kezdünk és nem játszunk jól, akkor is a BOT játékos nyer. Használjunk minél több heurisztikát, mellyel gyorsíthatjuk a progra- munkat.

(d) Próbáljuk kiterjeszteni a játékot aK=5 ésJ =4 esetre.

(e) Írjunk programot aJ =5 esetre, amikor aK mérete nagyobb, mint8.

25. Kártyajáték. (Filep László. Játékelmélet. 29. old.) Két kártyajátékos a következő játékot játssza: az I. játékos kap egy piros 1-est, 2-est, 3-ast és egy fekete 5-öst, a II. játékos pedig kap egy fekete 1-est, 3-ast, 5-öst, és egy piros 5-öst (a piros 5-ösbőlkétdarab van, nem elírás; valószínűleg két pakli kártyával játsszák). A játék menete a következő: mindkét játékos egyszerre felmutat 1-1 lapot: ha a lapok azonos színűek, akkor I. nyeri a két kártyán lévő szám különbségének abszolút értékét; ellenkező esetben (különböző színű kártyák esetén) II. nyeri a különbségek abszolút értékét.

(a) Írjuk fel a nyereségmátrixot az I. játékos szempontjából.

(b) Keressük meg az játékosok tiszta stratégiáit.

(c) Mennyi a játék értéke? Igazságos-e a játék?

26. Orosz rulett. (Filep László. Játékelmélet. 30. old.) Két gengszter kirabol egy bankot, ahonnan 6000$-t zsákmányolnak. Mindkettő magáénak akarja az egész összeget, ezért elhatározzák, hogy egy játékkal eldöntik kinek mennyi pénz jut. Először elosztják két egyenlő részre, azaz mindkét gengszternél 3000–3000$ marad. Ebből 1000–1000$-t betesznek egy táskába, majd a következő kétlépéses játékot játsszák:

• Az I. gengszter választ: vagy beszáll az orosz rulettbe, vagy egyszerűen beteszi a fennmaradó 2000$-ját a táskába és megvárja a játék kimenetelét.

• Ha úgy dönt, hogy játszik, akkor csak 1000$-t tesz a táskába, megpörgeti a hatlövetűt, amelybe 1 golyót helyeztek, a fejéhez tartja és elsüti; a túlélés valószínűsége ⁵₆, a halálé pedig ¹₆.

• Ha meghal, akkor a másik nyeri a táskában levő pénzt, azt ami az I. gengszternél maradt (1000$) elküldi az I. gengszter családjának.

• Ha életben marad, akkor a II. gengszter következik, aki hasonló módon jár el.

(a) Rajzoljuk fel a játékfát, azaz rajzoljuk fel a játék során előálló helyzeteket. A fa leveleihez rendeljük a nyereségeket az I. gengszter szempontjából (a kezdeti3000$-hoz viszonyítva).

(b) Írjuk fel a nyereségmátrixot az I. gengszter szempontjából.

(c) Keressük meg az I. és II. gengszter tiszta stratégiáját.

(d) Mennyi a játék értéke? Igazságos-e a játék?

27. Legyen egy zéró-összegű játék nyereségmátrixa a következő:







1 2 −1

−2 3 2

2 −1 1







(8)

• Állapítsuk meg az X játékos tiszta stratégiáját;

1 v 3

• Írjuk fel a játék értékét a játékosok kevert stratégiájának a függvényében;

x1y1−5x2y1+y1+5x1y2+3x2y2−2y2−2x1+x2+1

• Keressük meg azX játékos optimális kevert stratégiáját;

x1=1/4; x2=1/4; x3=2/4

• Számítsuk ki a játék értékét;

3/4

• Keressük meg azY játékos optimális kevert stratégiáját;

y1=11/28; y2=9/28; y3=8/28

• Ellenőrizzük a játék értékének a helyességét az Y szerinti újraszámolással.







−1 1 −1

−2 0 2

5 −1 −1







1 v 3

−6x1y1−10x2y1+6y1+2x1y2−2x2y2+3x2−1

x1=3/8; x2=3/8; x3=2/8

1/8

y1=3/16; y2=9/16; y3=4/16







1 0 −1

−2 3 0

0 −1 1







1 v 3

3x1y1−x2y1+5x2y2+3x1y2−2x1−x2−y1−2y2+1

x1=7/18; x2=3/18; x3=8/18

1/18

y1=7/18; y2=5/18; y3=6/18

(9)

30. Tizenegyes rúgások.

A tizenegyesek rúgásakor feltételezzük, hogy ajátékosjobbra, balra, valamint középre rúghatja a labdát. Akapusvéd: balra vagy jobbra vetődhet, illetve maradhat a helyén, amitK-val jelölünk.

A „játék” null-összegű és teljes információs, ahol:

• a kapus a lövés előtt mozdul el;

• a játékos szintén a kapus mozdulata előtt dönt.

B K J

B 5 8 9

K 8 4 8

J 9 8 5

Ismételt „kísérletezés” eredménye a fenti mátrix, ahol a számok a 10 rúgott büntetőből a gólok száma, azaz a játékosnyereségmátrixa. A fenti mátrix alapján:

(a) Írjuk fel a játék értékét;

V =xxx^TMMM yyy, majd azx3=1−x1−x2, illetve azy3=1−y1−y2

felhasználásával a következő kifejezést kapjuk:

V = −8y1x1−4y1x2+4y1−7y2x2+3y2+4x1−4x1y2+3x2+5

(b) Keressük meg azX játékos optimális kevert stratégiáját;

y1=2/5,y2=1/5,y3=2/5.

(c) Mennyi lesz a „játék” értéke? Értelmezzük az eredményt!

V =36/5=7, 1/5– optimális stratégia esetén ennyi az átlagos gólok száma10rúgásból.

(d) Hasonlítsuk össze az eredményt atisztastratégia értékével.

A játékos tiszta stratégiájának az értéke: 5, kisebb a kevert stratégia által elért eredménynél.







0 3 −2

−2 1 2

4 −1 0







3

−2x1y1−8x2y1+4y1+6x1y2−y2−2x1+2x2

x1=4/24; x2=11/24; x3=9/24

7/12

y1=3/12; y2=5/12; y3=4/12







3 0 −1

−1 1 0

0 −1 2







(10)

1 v 2 v 3

6x1y1+4x1y2+x2y1+4x2y2−3x1−2x2−2y1−3y2+2

x1=1/4; x2=1/2; x3=1/4

1/4

y1=1/5; y2=9/20; y3=7/20







0 −2 0 3

−2 0 3 −1

1 1 0 −1

1 2 −1 0







• Állapítsuk meg az X ésY játékosok tiszta stratégiáit;

X: 3 v 4 ;Y: 1.

−4x1y1−7x1y2−2x1y3−2x2y1−x2y2+5x2y3+x3y1+2x3y3+3x1−x2−x3+y1+2y2−y3

A rendszer, amit megoldunk:

2x2+4x1−x3=1 7x1+x2=2

−2x1+5x2+2x3=1

A megoldások: x1=5/19; x2=3/19; x3=7/19; x4=4/19

5/19

y1=17/57; y2=9/57; y3=20/57; y4=11/57







0 −2 0 2

−2 0 3 0

1 1 0 −3

1 0 −2 0







• Állapítsuk meg az X ésY játékosok tiszta stratégiáit;

X: 1 v 2 v 3 v 4 ;Y: 1 v 2.

−3x1y1−4x1y2−3x2y1+5x2y3+3x3y1+4x3y2+5x3y3+2x1−3x3+y1−2y3

(11)

A rendszer, amit megoldunk:

3x1+3x2−3x3=1 4x1−4x3=0 5x2+5x3=2

A megoldások: x1=1/15; x2=5/15; x3=1/15; x4=8/14

−1/15

y1=1/3; y2=1/4; y3=1/5; y4=13/60







2 4 −1 7 0 4 5 2 8 1 3 0 3 5 1 1 3 −2 2 1 1 3 −2 2 1







(a) Határozzuk meg a domináns stratégiákat és töröljük a mátrixból a dominált stratégiákat.

(b) Állapítsuk meg a tiszta stratégiákat.

(c) Számítsuk ki a játék értékét.







−1 −1 −1 −1 −1 −2

0 0 0 0 0 0

2 2 −4 0 0 −3

−2 −1 0 1 3 −6

2 −1 3 3 2 0

0 3 0 0 1 0







(c) Számítsuk ki a játék értékét.







2 2 2 2 2 2 6 4 2 4 3 3 6 5 3 5 4 4 6 9 9 −3 3 4 6 5 6 1 4 4 6 5 5 0 4 4







(c) Írjuk fel a játék értékét a játékosok kevert stratégiájának a függvényében.

(d) Keressük meg azX játékos optimális kevert stratégiáját.

(e) Számítsuk ki a játék értékét.

(f) Keressük meg azY játékos optimális kevert stratégiáját.

(g) Ellenőrizzük a játék értékének a helyességét az Y szerinti újraszámolással.

(12)

38. Két érmét dobunk fel, a dobások mindegyike fej – F – vagy írás – I. Tekintsük az {A, B, C} eseményeket az alábbiak szerint:

A = „az első érme fej”

B = „a második érme fej”

C = „csak egyérme fej”

A B C P(A, B, C)

0 0 0 0

... ... ... ... A jobb oldalon található táblázatot töltsük ki az együttes valószínűségekkel.

A táblázat alapján vizsgáljuk meg azA⊥B,B⊥C,C⊥Afüggetlenségeket, majd javasoljunk egy grafikus modellt, mely leírja a szerkesztett valószínűségi táblát.

Vizsgáljuk meg az {A, B}⊥C függetlenségi feltételt is, majd javítsunk a táblán. Ellenőrizzük a modellt.

39. Egy éjjel a riasztó megszólal a lakásban.

Mekkora a valószínűsége annak, hogy betörés történt, ha tudjuk, hogy:

• A riasztó 96%-os valószínűséggel megszólal betörés esetén;

• A riasztó 1%-ban hamis riasztást végez;

• Statisztikai adatok szerint1/1000 az esélye annak, hogy betörjenek.

Magyarázzuk meg az eredményt a következőkkel:

• Írjuk fel a keresett – feltételes – valószínűséget;

• Írjuk fel a teljes valószínűségi táblát;

• Alkalmazzuk a Bayes-képletet.

40. Tekintsük az alábbi irányított gráfokat. Amennyiben minden csomópont egy változót tartalmaz, a gráfok élei pedig a dependenciákat jelentik, állapítsuk meg az együttes valószínűségi változó megadásához szükséges – feltételes vagy nem – valószínűségeknek a számát.

(a) (b) (c) (d) (e)

Mekkora a teljes specifikációhoz szükséges valószínűségi tábla és a grafikus modellekhez szükséges

„elemi” valószínűségek számának az aránya. Mit tudunk megállapítani a gráfokról – melyek tartalmaznak kevesebb „információt”?

41. Legyen a következő valószínűségi tábla:_.

A \ B 0 1

0 0.08 0.12

1 0.32 0.48

(a) Írjuk fel a fenti tábla alapján az alábbi grafikus modellt. Milyen következtetést tudunk levonni?

A B

P(A) . . .

A P(B|A) 0 . . . 1 . . .

(b) Ellenőrizzük, hogy azA esemény független-e a B-től a p(A, B) =p(A)p(B) reláció alapján.

(13)

42. Legyen a következő valószínűségi tábla:

. C =0

A \ B 0 1

0 0.32 0.08

1 0.32 0.08

C=1

A \B 0 1

0 0.144 0.036 1 0.016 0.004

.

ahol a nyolc valószínűség azA,B, illetve Cesemények együttes előfordulásainak a gyakoriságai.

(a) Állapítsuk meg, hogy a következő kijelentések igazak-e:

• AésB események függetlenek;

• AésC események függetlenek;

• C ésB események függetlenek.

(b) A fentiek alapján javasoljunk egy grafikus modellt és állapítsuk meg a szükséges feltételes valószínűségeket.

43. Legyen a következő valószínűségi tábla:

. C=0

A \B 0 1

0 0.32 0.144 1 0.32 0.016

C=1

A\ B 0 1

0 0.05 0.09

1 0.05 0.01

.

ahol az előbbi feladathoz hasonlóan az együttes valószínűségeket adtuk meg.

(a) Állapítsuk meg, hogy a következő kijelentések igazak-e:

• AésB események függetlenek;

• AésC események függetlenek;

• C ésB események függetlenek.

(b) A fentiek alapján javasoljunk egy grafikus modellt és állapítsuk meg a szükséges feltételes valószínűségeket.

44. Tekintsük a mellékelt grafikus modellt.

Számítsuk ki a következő feltételes valószí- nűségeket:

x₁ x₂ x₃

x4

x₅ P(x₅)

1/5 X5 P(X4|X5)

0 2/9 1 7/10

X₄ P(X₃|X₂) 0 1/2 1 1/3

X₄ P(X₃|X₂) 0 2/3 1 1/10

45. Legyen a következő grafikus modell:

Láz Hűlés

P(L) 1/5

L P(H|L) 0 1/10 1 7/10 (a) Mekkora valószínűséggel állítható, hogy:

. ha lázas vagyok, akkor meg vagyok hűlve.

0.70

(14)

(b) Írjuk fel a valószínűségi változók együttes eloszlás–tábláját;

L\H 0 1

0 0.72 0.08

1 0.06 0.14

(c) Fordítsuk meg az irányítottságot a grafikus modellben;

Láz Hűlés

P(H) 0.22 H P(L|H)

0 1/13

1 7/11

(d) Mekkora valószínűséggel állítható, hogy:

. ha nemvagyok meghűlve, akkor lázas vagyok;

1/13=0.0769

• Mekkora valószínűséggel állítható, hogy:

. Ha meg vagyok hűlve és tüdőgyulladásom van, akkor nemvagyok lázas.

0.05

• Mekkora valószínűséggel állítható, hogy:

. hanem vagyok meghűlve, akkor lázas vagyok.

Hűlés Tüdőgy.

Lázas P(H)

0.20

P(T) H T P(L|H, T) 0.05

0 0 0.10 0 1 0.60 1 0 0.75 1 1 0.95

• Számítsuk ki az(H, T)együttes eloszlását, ha tudjuk hogy L=0;

H\T 0 1 H

0 0.9144 0.0214 0.9358 1 0.0635 0.0007 0.0642

T 0.9779 0.0221 -

• Független aH aT-től ha feltételezzük, hogy L=0? Miért?

NEM.

Ellenőrizzük például, hogyP(H, T)6=P(H)P(T), azaz0.00076=0.0014.

(15)

47. Tekintsük a mellékelt grafikus modellt (Barber D. 2011, 48. oldal).

A grafikus modell ábrázolja egy cég (vagy projekt) főnöke és egy alkalma- zottja „releváns” állapotait. Amint az ábra mutatja, a vezető dühös, ha az alkalmazottlassúa munkahelyén. Az alkalmazott akkor lassú, ha előző es- tebulizott, illetve akkor, ha általában nem szereti a munkáját, azazunott a munkahelyén. Látjuk azt is, hogy a buli fejfájásteredményezhet.

Buli Unott

Lassú Fejfájás

Dühös főnök P(B)

1/8

P(U) 1/10 B P(F|B)

0 1/50

1 3/4

B U P(L|B, U) 0 0 1/100 0 1 8/10 1 0 8/10 1 1 99/100

L P(D|L) 0 1/100 1 97/100

Azt tapasztaljuk egy alkalommal, hogy az alkalmazottnak fáj a feje és ugyanakkor a főnöke dühös. Számítsuk ki annak a valószínűségét, hogy az alkalmazott bulizott.

A keresettfeltételesvalószínűség: P(B=1|F=1, D=1)^def= P(B|F, D)ahol a negációt implicit jelöljük plF-fel, ellenkező esetben a logikai változó értékeigaz. A Bayes-képletet használvaP(B|F, D) = ^P_P^(B,F,D)_(F,D) , majd kiszámítjuk külön-külön a számlálóban és a nevezőben szereplő valószínűségeket, használva a Bayes-háló struktúrát.

P(B, F, D) =P(F|B, D)P(B, D) =P(F|B) X

L,U

P(B, U, L, D)

=P(F|B)P(B) X

L,U

P(D|L)P(L|B, U)P(U)

= 3 4 1 8

₁

100 2 10

9 10+ 1

100 1 100

1 10+ 97

100 8 10

9 10+ 97

100 99 100

1 10

= 29859 400000

A nevező kiszámításához felírjuk atejles valószínűség képletét:

P(F, D) =P(B,F, D) +P(B, F, D) = 29859

400000+ 8351 5000000

A keresett valószínűség:P(B|F, D) = ⁷⁴⁶⁴⁷⁵₇₆₃₁₇₇ =97.812%.

Betörés Földrengés

Riasztó

János hívás Mária hívás

P(B) 0.01

P(F) 0.02 B F P(R|B, F)

0 0 0.001 0 1 0.30 1 0 0.94 1 1 0.95 R P(J|R) 0 0.05 1 0.90

R P(M|R) 0 0.01 1 0.70

Számítsuk ki a következő valószínűségeket:

• P(R|B, F);

0.94

• P(R);

P(R) =P(R, B, F) +P(R, B, F) +P(R, B, F) +P(R, B, F)

=0.0163

(16)

• P(J, M);

P(J, M) =P(J, M, R) +P(J, M, R) =P(J, M|R)P(R) +P(J, M|R)P(R)

=P(J|R)P(M|R)P(R) +P(J|R)P(M|R)P(R)

=0.0108

• P(J, M);

=0.0531

• P(B|J, M).

P(B|J, M) =P(B, R|J, M) +P(B, R|J, M)

=P(B|R)P(R|J, M) +P(B|R)P(R|J, M)

=0.3070

• Értelmezzük majd számítsuk ki a következő valószínűségeket:

P(B, F|R) , P(B, F|R) , P(B, R|R), P(B, F|R)

Vizsgáljuk meg, hogy a Betörés és a Földrengés események függetlenek-e, ha tudjuk, hogyvolt riasztás. Magyarázzuk meg az eredményt.

A következő átalakítást végezzük el:

P(B, F|R) = P(B, F, R)

P(R) = P(R|B, F)P(B)P(F) P(R)

ahol az először a Bayes-képletet, majd aB ésResemények függetlenségét használtuk fel (függetlenség akkor, ha azReseményt nem ismerjük). A fentiek ismeretében kiszámítjuk aP(B, F|R),P(B, F|R),P(B, F|R), illetve aP(B, F|R) valószínűségeket, majd megvizsgáljuk, hogy az előállt valószínűségi tábla független változókat tartalmaz-e (nem).

• Értelmezzük majd számítsuk ki a következő valószínűségeket:

P(M|B), P(J|M) , P(M|F)

• Kinek a hívása nyomán aggódunk inkább a betörés lehetőségén? Fogalmazzuk meg a kérdést valószínűségi nyelvezetet használva. Igazoljuk a válaszunkat.

49. Egy tüdőkórházban a következő diagnosztikai modellt javasolták (Barber D. 2011, 49. oldal):

A

T R

B

V

G S

D P(A)

0.005

P(D) 0.25

T R P(V|T, R) 0 0 0

0 1 1 1 0 1 1 1 1 D P(R|D) 0 0.005 1 0.1

A P(T|A) 0 0.05 1 0.01 V P(G|V) 0 0.05 1 0.99

D P(B|D) 0 0.2 1 0.6

V B P(S|V, B) 0 0 0.1 0 1 0.7 1 0 0.7 1 1 0.9

A változók a következőket jelentik:

A – volt Ázsiában (mely TBC-t valószínűsít);

T – TBC-vel fertőzött;

D – Dohányzik;

R – Tüdőrák diagnózis;

V – vagy TBC-s vagy tüdőrákos;

S – légszomj, melyet mindhárom betegség okozhat;

G – pozitív röntgenfelvétel;

B – hörghurut, melyet jelen esetben a dohányzás elősegíthet;

(a) A modell alapján állapítsuk meg a következő események (feltételes) függetlenségét:

i. A⊥D; R⊥B; R⊥B | D;

ii. T ⊥R | G; A⊥D | R; A⊥D| R, B

(17)

(b) Értelmezzük és számítsuk ki a következő – feltételes – valószínűségeket:

P(R), P(R|V), P(R|V), P(V|A), P(G|T), P(T|G), P(R|D, G) 50. A diagnosztizáló modell mellékelt egy-

szerűbb változata alapján számítsuk ki a következő (feltételes) valószínűsége- ket:

(a) A páciensneklégszomja van;

(b) A röntgenfelvételnegatív;

(c) Dohányzó páciensnek van lég- szomja;

(d) Negatív röntgenfelvételesetén légszomjvalószínűsége;

R

B

G

S D P(D)

0.25 D P(R|D) 0 0.005

1 0.1

R P(G|R) 0 0.05 1 0.99

D P(B|D) 0 0.2 1 0.6

R B P(S|R, B) 0 0 0.1 0 1 0.7 1 0 0.7 1 1 0.9

Becsüljük az alábbi – marginális – valószínűséget:

p(R) =p(R|D)p(D) +p(R|D)p(D) =0.02875, (a)p(S) =P

∀i,j,kp(S|R=i, B=j)p(R=i|D=k)p(B=j|D=k)p(D=k) =0.29095 (b)p(G) =1−p(G) =1−P

∀ip(G|R=i)P(R=i) =0.922975 (c)p(S|D) =P

∀i,jp(S|R=i, B=j)p(R=i|D)p(B=j|D) =0.2226 (d)p(S|G) = P

∀i,j,kp(S, R=i, D=j, B=k, G)

/p(G) =0.21782

51. A Dempster–Schafer modell.

Három azonos kockát dobunk és a következő eredményeket kapjuk:

K₁ = (1, 1, 6) K₂= (1, 2, 3) K₃ = (1, 2, 5) K₄= (1, 2, 6) K₅ = (1, 3, 4) K₆ = (1, 3, 5) K₇= (1, 3, 6) K₈ = (1, 4, 5) K₉= (1, 5, 5) K₁₀= (1, 5, 6) K₁₁= (2, 3, 5) K₁₂= (2, 3, 6) K₁₃= (2, 4, 5) K₁₄= (2, 4, 6) K₁₅= (2, 6, 6) K16= (3, 5, 5) K17= (3, 3, 4) K18= (4, 4, 5) K19= (4, 5, 6) K20= (6, 6, 6) Az ismétlések szerint többszörözve, valamint ismerve aBel(A) =P

A∈Cm(C), illetve P l(A) = P

A∪C6=∅m(C), számítsuk ki aBel({1}),Bel({6}), illetve a P l({1}),P l({6}) értékeket, ha (a) Csak az elsőöt eseményt vesszük figyelembe;

(b) Mind a 20 eseményt figyelembe vesszük.

Mindkét esetben a halmazokategyenlőarányban súlyozzuk (az elsőben a súly1/5, a másodikban 1/20).

52. Bizonyítsuk be, hogy aBel(Z) függvény szubadditív, illetve azt, hogy aP l(Z) függvény szupe- radditív.

53. Tekintsük az m : 2^{1,2,3,4,5,6} → [0, 1] függvényt, mely egy kockához tartozó bizonytalanságot kódolja (Dempster-Schafer rendszer) a következők szerint:

m(∅) =0, az összes többi részhalmaz egyenlő súlyú: 1/31.

• Számítsuk ki a következő halmazokBel ésP lértékeit: {1, 2},{1, 2, 3},{3, 4, 5, 6}.

• Számítsuk ki a fenti halmazokra a Bel és P l értékeket, ha a rendszerben lenullázzuk az összes olyan halmaznak a súlyát, mely több, mint egy elemből áll és tartalmazza az{1, 2, 3}

részhalmaz legalábbegy elemét (a maradék halmazok súlyai egyenlőek).

54. Egy gyilkosság során a következő információk birtokába jutunk:

• Három lehetséges gyilkosunk van: Tamás,Péter, ésKati;

• Egy spion állítása szerint a (bér)gyilkost a maffiavezér a következők szerint sorsolta ki:

50%-ban Tamás vagyPéter, a fennmaradó félben pedig Tamás vagyKati.