Caricare documenti e articoli online 
INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.


 
Non ricordi la password?  ››  Iscriviti gratis
 

EIA - ESERCIZI + SOLUZIONI

informatica



EIA - ESERCIZI + SOLUZIONI


1) Supponiamo di avere i seguenti valori di probabilità:


P(raffreddore) = P(R) = 1/100


P(naso che cola / raffreddore) = P(N/R) = 3/4


P(N/ R) = 1/60


Utilizzare il teorema di Bayes per ricavare il valore di P(R/N). Non si vuole il valore numerico finale ma solo l'espressione aritmetica corrispondente.




Per il teorema di Bayes abbiamo:

P(R/N) = P(N/R) P(R)

P(N)


Noi non conosciamo il valore di P(N) però sappiamo che la probabilità di un evento X è data dalla formula:


P(X) = P(X/H1) P(H1) + P(X/H2) P(H2) + ... + P(X/Hn) P(Hn)


dove compare l'insieme necessario di eventi incompatibili H1, H2, ..., Hn


Nel nostro caso abbiamo:


H1 = [avere il raffreddore] = R


H2 = [non avere il raffreddore] = R


che sono eventi esaustivi e mutuamente esclusivi le cui probabilità sono:


P(H1) = P(R) = 1/100


P(H2) = P( R) = 1 - P(R) = 1 - 1/100 = 99/100 (in quanto per ogni evento X si ha: P(X) + P X) = 1)


Pertanto abbiamo:


P(N) = P(N/R) P(R) + P(N/ R) P( R) = 3/4 x 1/100 + 1/60 x 99/100 =




Sostituendo nella formula di Bayes abbiamo:


P(R/N) = P(N/R) P(R) = 3/4 x 1/100___ = 3/400____

P(N) 3/400 + 99/60000 3/400 + 99/60000



2) Rappresentare le seguenti frasi nella logica dei predicati:


Tutti amano qualcuno

" X Y Ama (X,Y)


Non tutti gli studenti seguono Geografia

X (studente (X) segue (X, Geografia)


Un solo studente è stato bocciato in Algebra

X (studente (X) bocciato (x, Algebra) " Y (studente (Y)

bocciato (Y, Algebra) X = Y



3) Dato il seguente albero di ricerca, determinare in quale ordine vengono visitati i nodi applicando gli algoritmi Hill climbing, Best first e A*. Vicino a ogni nodo c'è il costo stimato per giungere al nodo finale H. I rami sono etichettati con il costo per andare da un nodo all'altro. Avvalorare le seguenti tabelle:


Hill climbing:  Current state


Best first e A*: Coda a priorità Nodo cancellato e visitato

A:40



12 13 10



B:30 C:25 D:27


5


E:15


3 5



F:9 G:10


2


H:0


Hill climbing:  Current state

A

C

E

F


a questo punto l'algoritmo si blocca non potendo andare avanti


Best first: Coda a priorità Nodo cancellato e visitato

A A

B C D C

B D E E

B D F G F

B D G G

B D H H


A*: Coda a priorità Nodo cancellato e visitato

A A

B C D D

B C C

B E E

B F G F

B G G

B H H

4) Dato il seguente grafo, determinare in quale ordine vengono visitati i nodi applicando gli algoritmi BFS e DFS (stato iniziale A, stato finale G). Assumiamo che i nodi vengono inseriti nella coda o nello stack in senso orario a partire dall'alto. Avvalorare le seguenti tabelle:

coda   nodo cancellato nodo visitato lista visited


stack  nodo cancellato nodo visitato lista visited


A





B C D




E F G



BFS:

coda   nodo cancellato nodo visitato lista visited

A A A A

D C B   D D A D

C B A   C C A D C

B A A G B  B B A D C B

A A G B A C G F E A A D C B

A G B A C G F E    A A D C B

G B A C G F E   G G A D C B G



stack  nodo cancellato nodo visitato lista visited

A A A A

D C B   B B A B

D C A C G F E   E E A B E

D C A C G F B   B A B E

D C A C G F   F F A B E F

D C A C G B B A B E F

D C A C G  G G A B E F G


5) Rappresentare le seguenti frasi nella logica dei predicati:


a) C'è qualcuno che è amato da tutti

Y " X Ama (X,Y)


b) Ogni comune ha un solo sindaco

" X comune (X) Y sindaco (Y, X) " Z sindaco (Z, X)

Y = Z)


c) Essere nonno di X equivale ad essere genitore del genitore di X

" X, Y nonno (Y, X) Z genitore (X, Z) genitore (Z, Y)




6) Dato il seguente albero di ricerca, determinare in quale ordine vengono visitati i nodi applicando gli algoritmi Hill climbing, Best first e A*. Vicino a ogni nodo c'è il costo stimato per giungere al nodo finale M. I rami sono etichettati con il costo per andare da un nodo all'altro. Avvalorare le seguenti tabelle:


Hill climbing:  Current state


Best first e A*: Coda a priorità Nodo cancellato e visitato



A:30



8 7 2 9




6 9


I:7 J:6


5


M:0


Hill climbing: Current state

A

E

J


a questo punto l'algoritmo si blocca non potendo andare avanti


Best first:  Coda a priorità Nodo cancellato e visitato

A A

B C D E E

B C D I J J

B C D I I

B C D M M


A*: Coda a priorità Nodo cancellato e visitato

A A

B C D E D

B C E E

B C I J I

B C J M M



7) Dato il seguente grafo, determinare in quale ordine vengono visitati i nodi applicando gli algoritmi BFS e DFS (stato iniziale A, stato finale D). Assumiamo che i nodi vengono inseriti nella coda o nello stack in senso orario a partire dal basso. Avvalorare le seguenti tabelle:

coda   nodo cancellato nodo visitato lista visited


stack  nodo cancellato nodo visitato lista visited


A B





C D




E   F

BFS:

coda   nodo cancellato nodo visitato lista visited

A A A A

C B   C C A C

B E A B D F B B A C B

E A B D F D C A    E E A C B E

A B D F D C A C F A A C B E

B D F D C A C F    B A C B E

D F D C A C F    D D A C B E D



DFS:

stack  nodo cancellato nodo visitato lista visited

A A A A

C B   B B A B

C D C A A A B

C D C   C C A B C

C D E A B D F    F F A B C F

C D E A B D E C D D D A B C F D



8) Dato il seguente grafo, determinare in quale ordine vengono visitati i nodi applicando gli algoritmi BFS e DFS (stato iniziale A, stato finale E). Assumiamo che i nodi vengono inseriti nella coda o nello stack in senso orario a partire dall'alto. Avvalorare le seguenti tabelle:


coda   nodo cancellato nodo visitato lista visited


stack  nodo cancellato nodo visitato lista visited


A F






B C




D E

BFS:

coda   nodo cancellato nodo visitato lista visited

A  A A A

F C B F F A F

C B C A  C C A F C

B C A F A   B B A F C B

C A F A A E D    C A F C B

A F A A E D   A A F C B

F A A E D   F A F C B

A A E D A A F C B

A E D    A A F C B

E D   E E A F C B E




DFS:

stack  nodo cancellato nodo visitato lista visited

A A A A

F C B B B A B

F C A E D   D D A B D

F C A E B E E E A B D E




9) Data la seguente grammatica:


sentence --> noun-phrase (N), verb-phrase (N).

noun-phrase (N) --> det (N), adjectives, noun (N).

verb-phrase (N) --> verb (N), noun-phrase (_).

adjectives --> adjective adjectives / [ ].

adjective --> [piccolo] / [grande] / [bianco].

noun (s) --> [gatto] / [topo].

noun (p) --> [gatti] / [topi].

det (s) --> [il] .

det (p) --> [i] .

verb (s) --> [mangia].

verb (p) --> [mangiano].


individuare quali delle seguenti frasi possono essere riconosciute dalla grammatica e per esse disegnare il parse tree:


a) i piccolo topi mangiano il gatto


b) il topo mangiano il gatti


c) il grande bianco gatto mangia i topi


Per le frasi non generabili spiegare perché ciò non è possibile.


Il simbolo "/" serve a scrivere la grammatica in forma più compatta evitando di riscrivere più volte la categoria sintattica a sinistra.

Ad esempio, noun (s) --> [gatto] / [topo]. è un modo abbreviato per denotare le due regole:

noun (s) --> [gatto] .

noun (s) --> [topo] .



a) i piccolo topi mangiano il gatto


sentence




np  vp




det adjs noun verb np


adj adjs

det adjs noun





i piccolo - topi mangiano il - gatto






b) il topo mangiano il gatti


La frase non è generabile per due motivi. La prima regola della grammatica ci dice che il numero di noun-phrase deve accordarsi col numero di verb-phrase mentre "il topo" ha numero singolare e "mangiano" numero plurale. Inoltre nella noun-phrase il numero dell'articolo deve accordarsi col numero del sostantivo e ciò non accade in "il gatti".

c) il grande bianco gatto mangia i topi



sentence




np  vp




det adjs noun verb np


adj adjs


adj adjs det adjs noun




il grande bianco - gatto mangia i - topi








10) Rappresentare le seguenti frasi nella logica dei predicati:


a) Non esiste alcuno che non gradisce il gelato

X likes (X, gelato)


b) Essere madre di Y equivale ad essere il suo genitore femminile

" X, Y madre (X, Y) femmina (X) genitore (X, Y)


c) Maschio e femmina sono categorie disgiunte

" X maschio (X) femmina (X)


d) Per ciascuno stato c'è una sola capitale.

" X stato (X) Y capitale (Y, X) " Z capitale (Z, X) Y = Z)




11) Dato il seguente albero di ricerca, determinare in quale ordine vengono visitati i nodi applicando gli algoritmi Hill climbing, Best first e A*. Vicino a ogni nodo c'è il costo stimato per giungere al nodo finale M. I rami sono etichettati con il costo per andare da un nodo all'altro. Avvalorare le seguenti tabelle:


Hill climbing: Current state


Best first e A*: Coda a priorità Nodo cancellato e visitato

A:40



12 13 10



B:30 C:25 D:27


5


E:15


3 5



F:9 G:10

5 4


I:7 L:6




M:0

Hill climbing: Current state

A

C

E

F

L

a questo punto l'algoritmo si blocca non potendo andare avanti


Best first: Coda a priorità Nodo cancellato e visitato

A A

B C D C

B D E E

B D F G F

B D G I L   L

B D G I I

B D G M M


A*: Coda a priorità Nodo cancellato e visitato

A A

B C D D

B C C

B E E

B F G F

B G I L L

B G I I

B G M M


Al settimo passo si potrebbe cancellare G invece di I in quanto hanno lo stesso costo, poi I e M.




12) Rappresentare le seguenti frasi nella logica dei predicati:


Non tutti i gatti sono neri

X (gatto (X) nero (X))


Nessun uomo è più alto di Paolo

X (uomo (X) piualto (X, Paolo)


Ogni persona ha un'unica coppia di genitori

" X persona (X) Y genitori (Y, X) " Z genitori (Z, X)

Y = Z)





13) Supponiamo di avere i seguenti valori di probabilità:


P(artrite) = P(A) = 1/50


P(dolori articolazioni/artrite) = P(D/A) = 2/3


P(D/ A) = 1/10


Utilizzare il teorema di Bayes per ricavare il valore di P(A/D). Non si vuole il valore numerico finale ma solo l'espressione aritmetica corrispondente.


Per il teorema di Bayes abbiamo:

P(A/D) = P(D/A) P(A)

P(D)


Noi non conosciamo il valore di P(D) però sappiamo che la probabilità di un evento X è data dalla formula:


P(X) = P(X/H1) P(H1) + P(X/H2) P(H2) + ... + P(X/Hn) P(Hn)


dove compare l'insieme necessario di eventi incompatibili H1, H2, ..., Hn


Nel nostro caso abbiamo:


H1 = [avere l'artrite] = A


H2 = [non avere l'artrite] = A


che sono eventi esaustivi e mutuamente esclusivi le cui probabilità sono:


P(H1) = P(A) = 1/50


P(H2) = P( A) = 1 - P(A) = 1 - 1/50 = 49/50

(in quanto per ogni evento X si ha: P(X) + P X) = 1)


Pertanto abbiamo:


P(D) = P(D/A) P(A) + P(D/ A) P( A) = 2/3 x 1/50 + 1/10 x 49/50 =




Sostituendo nella formula di Bayes abbiamo:

P(A/D) = P(D/A) P(A) = 2/3 x 1/50___ = 1/75____

P(D) 1/75 + 49/500 1/75 + 49/500

14) Data la seguente matrice di gioco:



1 -3 -2


0 -4 -2


-5 2 3



controllare se esiste un punto di sella e risolvere quindi il gioco. Infine verificare che il valore del gioco coincide con il valore atteso.


Mettiamo le parentesi tonde e quadre e otteniamo:



[1] (-3) -2


0 (-4) -2


(-5) [2] [3]



non c'è punto di sella.


Vediamo che la colonna 2 domina la colonna 3, che può essere eliminata:




1 -3


0 -4


-5 2


Ora vediamo che la riga 1 domina la riga 2, che può essere eliminata:



1 -3


-5 2


Dobbiamo ora calcolare v, p1 , p2 , q1 , q2


v = Det(X) = ad - bc = -13

D a+d-b-c 11


p1 = d - c = 7 p2 = 1 - p1 = 4

D 11 11


q1 = d - b = 5 q2 = 1 - q1 = 6

D 11 11


E(X) = 1 7 5 - 3 7 6 - 5 4 5 + 2 4 6 = 35 - 126 - 100 + 48 =

11 11 11 11 11 11 11 11 121 121 121 121


= 83 - 226 = -143 = -13

121 121 11




15) R e C hanno ciascuno una moneta da 1 euro e una da 2 euro.

Mostrano contemporaneamente una moneta, se sono uguali R vince la moneta di C, se sono diverse C vince la moneta di R.

Rappresentare il gioco mediante una matrice, controllare se esiste un punto di sella, risolvere il gioco. Infine, verificare che il valore del gioco coincide con il valore atteso.


1 -1


-2 2


Mettendo le parentesi tonde e quadre otteniamo:



[1] (-1)


(-2) [2]


pertanto non c'è punto di sella.


Dobbiamo ora calcolare il valore del gioco v, p1 , p2 , q1 , q2


v = Det(X) = ad - bc = 0 = 0

D a+d-b-c 6


p1 = d - c = 4 = 2 p2 = 1 - p1 = 1

D 6 3 3


q1 = d - b = 3 = 1 q2 = 1 - q1 = 1

D 6 2 2


E(X) = 1 2 1 - 1 2 1 - 2 1 1 + 2 1 1 = 2 - 2 - 2 + 2 = 0

3 2 3 2 3 2 3 2 6 6 6 6



16) Consideriamo il gioco sasso, forbici, carta. Se R e C mostrano lo stesso oggetto pareggio, altrimenti sasso vince forbici, forbici vince carta, e carta vince sasso. La vincita è 1 euro a partita. Rappresentare il gioco mediante una matrice, controllare se esiste un punto di sella. Esporre il ragionamento che porta a individuare la strategia ottimale per R e C. Infine calcolare il valore atteso E(X).



S F C


S 0 1 -1


F -1 0 1


C 1 -1 0


Mettiamo le parentesi tonde e quadre e abbiamo:


S F C


S 0 [1] (-1)


F (-1) 0 [1]


C [1] (-1) 0



Non esiste punto di sella per cui non esistono strategie pure. La matrice è 3 x 3 e non possiamo ridurla in quanto non ci sono righe o colonne dominate. Per individuare le strategie ottimali occorrerebbe utilizzare il metodo del simplesso però è possibile fare un ragionamento simile a quello dell'Esempio 3. Se R scegliesse una delle tre possibilità più spesso delle altre due, C si accorgerebbe di ciò e ne trarrebbe vantaggio. Ad esempio, se R mostrasse Forbici con p=1/2, a C converrebbe mostrare Sasso. Pertanto l'unico modo per non avvantaggiare C e mostrare S, F, C con p=1/3. Ovviamente, anche per C la strategia ottimale è p=1/3.


E(X) = 0 1 1 + 1 1 1 - 1 1 1 - 1 1 1 + 0 1 1 + 1 1 1 + 1 1 1 +

3 3 3 3 3 3 3 3 3 3 3 3 3 3


- 1 1 1 + 0 1 1 = 0

3 3 3 3


17) Abbiamo visto che il gioco testa-croce dell'Esempio 3 può essere rappresentato (Esempio 16) dalla matrice:



testa croce


testa 1, -1 -1, 1


croce -1, 1 1, -1


e abbiamo verificato che non ci sono nè strategie dominanti, nè equilibri puri di Nash. Trovare gli equilibri misti.


Nel caso in cui R abbia scelto la riga 1, p1 = 1


e la vincita media di R dipenderà solo dalla strategia adottata da C.


Supponiamo che C adotti la strategia mista (q1, q2) = (q, 1-q), cioè C scelga la colonna 1 con probabilità q e la colonna 2 con probabilità (1-q), allora la vincita media di R sarà:


2

E(riga 1) = S x1 j p1 qj = 1 x 1 x q + (-1) x 1 x (1-q) = q - 1+ q = 2q - 1

j=1


Analogamente, una volta che R ha scelto la riga 2, p2 = 1 e la vincita media di R sarà:


2

E(riga 2) = S x2 j p2 qj = -1 x 1 x q + 1 x 1 x (1-q) = -q + 1 - q = -2q - 1

j=1


Ora, quello che vuole C è che per R sia indifferente scegliere riga 1 o riga 2, cioè scegliere una riga invece che l'altra non deve dare a R alcun vantaggio. In altri termini, la vincita media di R scegliendo la riga 1 deve essere uguale a quella ottenuta scegliendo la riga 2, cioè deve essere:


2q - 1 = -2q + 1


4q = 2


q = 1/2


(1 - q) = 1/2


In conclusione, la strategia di C che rende a R indifferente ai fini della vincita media la scelta della riga 1 o della riga 2 è individuata dal vettore (q1, q2) = (1/2, 1/2). Tale strategia ottimale era già stata individuata ragionando sul gioco.


Simmetricamente, anche R vuole che C non abbia motivo per preferire la colonna 1 alla colonna 2 o viceversa.


Ora, nel momento in cui C sceglie la colonna 1, q1 = 1 e il valore atteso della sua vincita dipende solo dalla strategia di R, descritta dal vettore (p1, p2) = (p, 1-p). La vincita media di C relativa alla scelta della colonna 1 è:


2

E(colonna 1) = S xi 1 pi q1 = -1 x p x 1 + 1 x (1-p) x 1 = -2p + 1

i=1


Analogamente, una volta che C ha scelto la colonna 2, q2 = 1 e la vincita media di C sarà:


2

E(colonna 2) = S xi 2 pi q2 = 1 x p x 1 -1 x (1-p) x 1 = 2p - 1

i=1


L'obiettivo di R è che per C sia indifferente scegliere colonna 1 o colonna 2, cioè scegliere una colonna invece che l'altra non deve avvantaggiare R.


In altri termini, la vincita di C scegliendo la colonna 1 deve essere uguale a quella ottenuta scegliendo la colonna 2, cioè deve essere:


-2p + 1 = 2p - 1


p = 1/2


In conclusione, la strategia di R che rende a C indifferente, ai fini della vincita media, la scelta della colonna 1 o della colonna 2 è individuata dal vettore (p1, p2) = (1/2, 1/2). La strategia è identica a quella che adotta C essendo il gioco simmetrico.


18) Due aziende, R e C, competono per la stessa nicchia di mercato. Se una sola azienda occupa la nicchia vince 100, se entrambe la occupano, ciascuna perde 50, se un'azienda non la occupa vince 0.

Rappresentare con una matrice questo gioco. Controllare se ci sono strategie dominanti. Individuare gli equilibri puri e misti.



occupa non occupa


occupa -50, -50 100, 0


non occupa 0, 100 0, 0


Non ci sono strategie dominanti.

Vediamo se ci sono equilibri puri:


occupa non occupa

occupa -50, -50 [100], (0)

non occupa (0), [100] 0, 0


Ci sono due equilibri puri (occupa, non occupa) e (non occupa, occupa).

Non essendoci strategie dominanti, possiamo cercare un equilibrio misto.


Nel caso in cui R abbia scelto la riga 1, p1 = 1 e la vincita media di R dipenderà solo dalla strategia adottata da C.


Supponiamo che C adotti la strategia mista (q1, q2) = (q, 1-q), cioè C scelga la colonna 1 con probabilità q e la colonna 2 con probabilità (1-q), allora la vincita media di R sarà:


2

E(riga 1) = S x1 j p1 qj = -50 x 1 x q + 100 x 1 x (1-q) =

j=1


= -50q + 100 -100q = 100 - 150q

Analogamente, una volta che R ha scelto la riga 2, p2 = 1 e la vincita media di R sarà


2

E(riga 2) = S x2 j p2 qj = 0 x 1 x q + 0 x 1 x (1-q) = 0

j=1


Ora, quello che vuole C è che per R sia indifferente scegliere riga 1 o riga 2, cioè scegliere una riga invece che l'altra non deve dare a R alcun vantaggio. In altri termini, la vincita media di R scegliendo la riga 1 deve essere uguale a quella ottenuta scegliendo la riga 2, cioè deve essere:


100 - 150q = 0


q = 100/150 = 2/3


(1 - q) = 1/3


In conclusione, la strategia di C che rende a R indifferente ai fini della vincita media la scelta della riga 1 o della riga 2 è individuata dal vettore (q1, q2) = (2/3, 1/3).


Simmetricamente, anche R vuole che C non abbia motivo per preferire la colonna 1 alla colonna 2 o viceversa. Ora, nel momento in cui C sceglie la colonna 1, q1 = 1 e il valore atteso della sua vincita dipende solo dalla strategia di R, descritta dal vettore (p1, p2) = (p, 1-p). La vincita media di C relativa alla scelta della colonna 1 è:

2



E(colonna 1) = S xi 1 pi q1 = -50 x p x 1 + 100 x (1-p) x 1 = 100 - 150p

i=1


Analogamente, una volta che C ha scelto la colonna 2, q2 = 1 e la vincita media di C sarà:

2

E(colonna 2) = S xi 2 pi q2 = 0 x p x 1 + 0 x (1-p) x 1 = 0

i=1


L'obiettivo di R è che per C sia indifferente scegliere colonna 1 o colonna 2, cioè scegliere una colonna invece che l'altra non deve avvantaggiare R.


In altri termini, la vincita di C scegliendo la colonna 1 deve essere uguale a quella ottenuta scegliendo la colonna 2, cioè deve essere:


100 - 150p = 0

p = 2/3


In conclusione, la strategia di R che rende a C indifferente, ai fini della vincita media, la scelta della colonna 1 o della colonna 2 è individuata dal vettore (p1, p2) = (2/3, 1/3). La strategia è identica a quella che adotta C essendo il gioco simmetrico.

19) Data la seguente matrice di gioco:


5, 9 19,11 8,8


15,16 14,7 9,18


20,11 12,13 14,3



E' la scelta riga 2 - colonna 1 un equilibrio di Nash ?

Controllare poi l'esistenza di strategie dominanti. Controllare l'esistenza di equilibri puri e ragionare sulla loro validità.


La scelta riga 2 - colonna 1 non è un equilibrio di Nash in quanto se C sceglie la colonna 1 a R conviene la riga 3 (vincita 20). Analogamente, se R sceglie la riga 2 a C conviene la colonna 3 (vincita 18).


Non vi sono strategie dominanti.


Usando le parentesi abbiamo:


5, 9 (19),[11] 8,8


15,16 14,7 9,[18]


(20),12 12,[13] (14),3



Esiste l'unico equilibrio puro riga1- colonna 2. Non si tratta del miglior risultato ottenibile con strategie pure. Infatti riga 3 - colonna 1 consente di vincere di più ad entrambi.

20) Supponiamo di avere la seguente tabella che indica se cinque pazienti sono stati dimessi dall'ospedale il giorno dopo l'operazione:


operazione famiglia anziano febbre DIMESSO

impegnativa

1) SI NO NO SI NO


2) SI NO SI SI NO


3) NO NO NO NO SI


4) NO NO SI SI NO


5) NO SI SI NO SI


Abbiamo la seguente popolazione iniziale di soluzioni:


S =


Calcolare la percentuale di esempi correttamente classificati da ciascuna stringa. Applicare l'operatore "incrocio" e calcolare la percentuale di esempi correttamente classificati dalle stringhe ottenute.


F F # T : 1, 2 --> 2/5


# T F #: 1, 2, 4 --> 3/5


# # F T: 2, 4 --> 2/5


F T T F: 1, 2, 4, 5 --> 4/5


Applichiamo l'operatore alle due stringhe con il miglior punteggio e abbiamo:


# T F # incrociata con F T T F genera


# T T F: 1, 2, 4, 5 --> 4/5 e


F T F #: 1, 2, 4 --> 3/5

21) Supponiamo di avere la seguente tabella che indica se quattro persone hanno ottenuto una polizza assicurativa:


giovane sano reddito famiglia POLIZZA


1) SI NO NO SI SI


2) NO SI SI NO SI


3) NO NO SI SI NO


4) SI NO SI NO NO


Abbiamo la seguente popolazione iniziale di soluzioni:


S =


Calcolare la percentuale di esempi correttamente classificati da ciascuna stringa. Applicare l'operatore "incrocio" e calcolare la percentuale di esempi correttamente classificati dalle stringhe ottenute.


T # # F: 1, 3 --> 2/4


T T # #: 1, 3, 4 - > 3/4


F T # F: 2, 4 --> 2/4


T # F F: 1, 3, 4 --> 3/4


Applichiamo l'operatore alle due stringhe con il miglior punteggio e abbiamo:


T T # # incrociata con T # F F genera


T T F F: 1, 3, 4 --> 3/4 e


T # # #: 1, 3 --> 2/4


22) Supponiamo di avere la seguente tabella che indica se quattro persone hanno ottenuto una polizza assicurativa:


giovane sano reddito famiglia POLIZZA


1) SI NO NO SI SI


2) NO SI SI NO SI


3) NO NO SI SI NO


4) SI NO SI NO NO


Applicare l'algoritmo di apprendimento del perceptron e ricavare il primo ciclo di apprendimento, supponendo che:

i pesi inizialmente valgono 0.2

il valore di soglia è t=0.5

il valore di modifica è d=0.05


1) 0.2 1 + 0.2 1 + 0.2 0 + 0.2 0 = 4


0.25 1 + 0.25 1 + 0.2 0 + 0.2 0 = 0.5


0.30 1 + 0.3 1 + 0.2 0 + 0.2 0 = 0.6 > t OK


2) 0.3 0 + 0.3 1 + 0.2 1 + 0.2 0 = 0.5


0.3 0 + 0.35 1 + 0.25 1 + 0.2 0 = 0.6 > t OK


3) 0.3 0 + 0.35 0 + 0.25 1 + 0.2 1 = 0.45 < t OK


0.3 1 + 0.35 0 + 0.25 1 + 0.2 0 = 0.55


0.25 1 + 0.35 0 + 0.2 1 + 0.2 0 = 0.45 < t OK

23) Supponiamo di avere la seguente tabella che indica se cinque pazienti sono stati dimessi dall'ospedale il giorno dopo l'operazione:


operazione famiglia anziano febbre DIMESSO

impegnativa

1) SI NO NO SI NO


2) SI NO SI SI NO


3) NO NO NO NO NO


4) NO NO SI SI NO


5) NO SI SI NO SI


Applicare l'algoritmo di apprendimento del perceptron e ricavare il primo ciclo di apprendimento, supponendo che:

i pesi inizialmente valgono 0.2

il valore di soglia è t=0.5

il valore di modifica è d=0.05


1) 0.2 1 + 0.2 0 + 0.2 0 + 0.2 1 = 0.4 < t OK


2) 0.2 1 + 0.2 0 + 0.2 1 + 0.2 1 = 0.6


0.15 1 + 0.2 0 + 0.15 1 + 0.15 1 = 0.45 < t OK


3) 0.15 0 + 0.2 0 + 0.15 0 + 0.15 0 = 0 < t OK


4) 0.15 0 + 0.2 0 + 0.15 1 + 0.15 1 = 0.3 OK


5) 0.15 0 + 0.2 1 + 0.15 1 + 0.15 0 = 0.35


0.15 0 + 0.25 1 + 0.2 1 + 0.15 0 = 0.45


0.15 0 + 0.3 1 + 0.25 1 + 0.15 0 = 0.55 > t OK


0.25 1 + 0.35 0 + 0.2 1 + 0.2 0 = 0.45 < t OK


24) Supponiamo di avere il seguente albero di gioco:



A MAX





B C   MIN





D E F

0 -10 10


Applicare la procedura Minimax avvalorando la seguente tabella:


Livello ric. Nodo Call Return Max Min


1 A max

2 B min

3 D 0

2 B

3 E -10

2 B -10

2 B -10

1 A

2 C min

3 F 10

2 C 10

2 C 10

1 A 10

1 A 10

25) Supponiamo di avere il seguente albero di gioco:



A MIN




B C D MAX

0 0




E F

10 -10


Applicare la procedura Minimax avvalorando la seguente tabella:


Livello ric. Nodo Call Return Max Min


1 A min

2 B 0

1 A

2 C max

3 E 10

2 C

3 F -10

2 C 10

2 C 10

1 A

2 D 0

1 A 0

1 A 0



26) R e C hanno ciascuno tre monete: una da 1 cent, una da 5 e una da 10.

Mostrano contemporaneamente una moneta, se la somma è pari R vince la moneta di C, se è dispari C vince la moneta di R.

Rappresentare il gioco mediante una matrice, controllare se esiste un punto di sella, risolvere il gioco. Infine, verificare che il valore atteso E(X) usando le strategie ottimali coincide con il valore del gioco.


Mettiamo le parentesi tonde e quadre e abbiamo:


1 5 10


1 [1] [5] (-1)


5 [1] [5] (-5)


10 (-10) (-10) [10]




Non esiste punto di sella.


Notiamo che la riga 1 domina la riga 2 per cui eliminiamo la riga 2:


1 5 -1


-10 -10 10


Vediamo ora che la colonna 1 domina la colonna 2, che viene eliminata:


1 -1


-10 10




Eliminando righe e colonne dominate si ottengono matrici equivalenti a quelle di partenza dal punto di vista del valore del gioco e delle strategie ottimali. Infatti anche la matrice ridotta è priva di punto di sella:



[1] (-1)


(-10) [10]


Dobbiamo ora calcolare il valore del gioco v e le strategie ottimali (p1 , p2) e (q1 , q2)


v = Det(X) = ad - bc = 10 - 10 = 0

D a+d-b-c 22


p1 = d - c = 20 = 10 p2 = 1 - p1 = 1

D 22 11 11


q1 = d - b = 11 = 1 q2 = 1 - q1 = 1

D 22 2 2


Calcoliamo infine il valore atteso E(X) nel momento in cui si utilizzano le strategie ottimali:


E(X) = 1 10 1 - 1 10 1 - 10 1 1 + 10 1 1 = 10 - 10 - 10 + 10 = 0

11 2 11 2 11 2 11 2 22 22 22 22


Le strategie ottimali per la matrice originale si ottengono assegnando probabilità zero alla seconda riga e alla seconda colonna.



27) Supponiamo di avere la seguente tabella che indica se quattro vini hanno avuto il permesso per l'esportazione:


colore odore sapore invecch. PERMESSO


1) NO SI SI SI SI


2) SI NO SI SI NO


3) SI SI NO NO SI


4) NO SI SI NO NO



Applicare l'algoritmo di apprendimento del perceptron e ricavare il primo ciclo di apprendimento, supponendo che:

i pesi inizialmente valgano 0.2

il valore di soglia sia t=0.5

il valore di modifica sia d=0.05


1) 0.2 0 + 0.2 1 + 0.2 1 + 0.2 1 = 0.6 OK




2) 0.2 1 + 0.2 0 + 0.2 1 + 0.2 1 = 0.6 KO


0.15 1 + 0.2 0 + 0.15 1 + 0.15 1 = 0.45 OK


3) 0.15 1 + 0.2 1 + 0.15 0 + 0.15 0 = 0.35 KO


0.2 1 + 0.25 1 + 0.15 0 + 0.15 0 = 0.45 KO


0.25 1 + 0.3 1 + 0.15 0 + 0.15 0 = 0.55 OK


4) 0.25 0 + 0.3 1 + 0.15 1 + 0.15 0 = 0.45 OK



28) Dato il seguente grafo, determinare in quale ordine vengono visitati i nodi applicando gli algoritmi BFS e DFS (stato iniziale D, stato finale E). Assumiamo che i nodi vengono inseriti nella coda o nello stack in senso antiorario a partire dal basso. Avvalorare le seguenti tabelle:

coda   nodo cancellato nodo visitato lista visited


stack  nodo cancellato nodo visitato lista visited




A





B C D




E F G



BFS:

coda   nodo cancellato nodo visitato lista visited

D D D D

A A A D A

C D B   C C D A C

D B G A B  D D A C

B G A B B B D A C B

G A B F G C A E    G G D A C B G

A B F G C A E C B A D A C B G

B F G C A E C B    B D A C B G

F G C A E C B    F F D A C B G F

G C A E C B B   G D A C B G F

C A E C B B   C D A C B G F

A E C B B   A D A C B G F

E C B B E D A C B G F E


DFS:

stack  nodo cancellato nodo visitato lista visited

D D D D

A A A D A

C D B B B D A B

C D F G C A E  E E D A B E

29) Consideriamo la seguente matrice di gioco:


60, 20 0, 0

0, 0 20, 60

Individuare, se esistono:

- strategie dominanti

- equilibri puri di Nash (sia basandosi sulla definizione, sia utilizzando l'algoritmo parentesi tonde-quadre)

- equilibri misti

Valutare la bontà degli equilibri individuati, calcolando i valori attesi delle vincite.

Non ci sono strategie dominanti. Vediamo se ci sono equilibri puri:


(60), [20] 0, 0

0, 0 (20), [60]

Vi sono due equilibri in strategie pure: (riga 1, colonna 1) e (riga 2, colonna 2).

In accordo con la definizione di equilibrio, la strategia (riga 1, colonna 1) è un equilibrio di Nash in quanto, se C sceglie la colonna 1, a R conviene la riga 1. Analogamente, se R sceglie la riga 1, a C conviene la colonna 1.

Lo stesso discorso vale per l'altra strategia (riga 2, colonna 2), per cui anche questa è un equilibrio puro.

Mancando le strategie dominanti possiamo cercare un equilibrio in strategie miste.

Supponiamo che R scelga la riga 1 per cui p1 = 1 e C adotti la strategia mista (q1, q2) = (q, 1-q), allora la vincita media di R sarà:


2

E(riga 1) = S x1 j p1 qj = 60 x 1 x q + 0 x 1 x (1-q) = 60q

j=1


Analogamente, una volta che R ha scelto la riga 2, p2 = 1 e la vincita media di R sarà:

2

E(riga 2) = S x2 j p2 qj = 0 x 1 x q + 20 x 1 x (1-q) = 20(1-q)

j=1


Ora, quello che vuole C è che per R sia indifferente scegliere riga 1 o riga 2, cioè scegliere una riga invece che l'altra non deve dare a R alcun vantaggio. In altri termini, la vincita media di R scegliendo la riga 1 deve essere uguale a quella ottenuta scegliendo la riga 2, cioè deve essere:


60q = 20(1 - q)


80q = 20


q = 20/80 = 1/4


1-q = 1 - 1/4 = 3/4


In conclusione, la strategia di C che rende a R indifferente ai fini della vincita media la scelta della riga 1 o della riga 2 è individuata dal vettore (q1, q2) = (1/4, 3/4).


Simmetricamente, anche R vuole che C non abbia motivo per preferire la colonna 1 alla colonna 2 o viceversa.

Ora, nel momento in cui C sceglie la colonna 1, q1 = 1 e il valore atteso della sua vincita dipende solo dalla strategia di R, descritta dal vettore (p1, p2) = (p, 1-p). La vincita media di C relativa alla scelta della colonna 1 è:


2

E(colonna 1) = S xi 1 pi q1 = 20 x p x 1 + 0 x (1-p) x 1 = 20p

i=1


Analogamente, una volta che C ha scelto la colonna 2, q2 = 1 e la vincita media di C sarà:


2

E(colonna 2) = S xi 2 pi q2 = 0 x p x 1 + 60 x (1-p) x 1 = 60(1 - p)

i=1


L'obiettivo di R è che per C sia indifferente scegliere colonna 1 o colonna 2, cioè scegliere una colonna invece che l'altra non deve avvantaggiare R. In altri termini, la vincita di C scegliendo la colonna 1 deve essere uguale a quella ottenuta scegliendo la colonna 2, cioè deve essere:


20p = 60(1 - p)


80p = 60


p = 60/80 = 3/4


1-p = 1 - 3/4 = 1/4


In conclusione, la strategia di R che rende a C indifferente, ai fini della vincita media, la scelta della colonna 1 o della colonna 2 è individuata dal vettore (p1, p2) = (3/4, 1/4).


Abbiamo perciò individuato un terzo equilibrio di Nash descritto dalla coppia di strategie miste:


(p1, p2) = (1/4, 3/4)


(q1, q2) = (3/4, 1/4)


Abbiamo individuato due equilibri puri e uno misto per il gioco. Quali sono le vincite medie per i tre equilibri ?


1) (riga 1, colonna 1): costantemente, R vince 60 e C vince 20


2) (riga 2, colonna 2): ogni volta, R vince 20 e C vince 60


3) con la strategia mista le vincite medie sono le seguenti:


E(R) = 60 3/4 1/4 + 20 1/4 3/4 = 180/16 + 60/16 = 240/16 = 15


E(C) = 20 3/4 1/4 + 60 1/4 3/4 = 160/16 + 180/16 = 240/16 = 15



Nessuno dei due equilibri puri è efficiente. Infatti, i due equilibri sono asimmetrici: il primo avvantaggia R, il secondo C. Notiamo però che il terzo equilibrio ha sì il vantaggio di essere simmetrico (entrambi i giocatori hanno la stessa vincita) però in media fa vincere 15, meno di quanto assicurato dagli equilibri puri. La cosa non è strana: infatti ogniqualvolta R sceglie la riga 1 e C la colonna 2 (ovvero riga 2 e colonna 1) entrambi vincono zero. Il buon senso suggerisce di mettersi d'accordo, adottare una delle strategie pure e dividere a metà la vincita (in tal modo sia R che C vincono 40).

30) Supponiamo di avere il seguente albero di gioco:



A MAX





B C MIN

10



D E F

0 -10 10




Applicare la procedura Minimax avvalorando la seguente tabella e disegnare l'albero indotto dalla procedura.


Livello ric. Nodo Call Return Max Min


1 A max

2 B min

3 D 0

2 B

3 E -10

2 B

3 F 10

2 B -10

2 B -10

1 A

2 C 10

1 A 10

1 A 10








A 10 MAX





B C MIN

10



D E F

0 -10 10




31) Data la matrice di gioco:



4 1


3 x



risolvere il gioco nei seguenti tre casi:


x=0, x=2, x=5.


Nei primi due casi NON utilizzare l'algoritmo parentesi tonde-quadre per individuare le strategie da applicare. Servirsi, invece, del concetto di righe e colonne dominanti.

Nel terzo caso, verificare che il valore atteso coincide con il valore del gioco.


Primo caso: x=0


4 1


3 0



La prima riga domina la seconda riga per cui quest'ultima si può cancellare:




4 1




Pertanto R sceglie sempre la prima riga e C la seconda colonna:


p = (1, 0) q = (0, 1)


Il valore del gioco è 1.


Secondo caso: x=2


4 1


3 2



La seconda colonna domina la prima per cui quest'ultima si può cancellare:




1


2



Pertanto R sceglie sempre la seconda riga e C la seconda colonna.


p = (0, 1) q = ( 0, 1)


Il valore del gioco è 2.


Terzo caso: x=5


4 1


3 5


Non ci sono righe o colonne dominanti. Non esiste punto di sella:



[4] (1)


(3) [5]



Dobbiamo individuare le strategie miste applicando il teorema minimax.

Calcoliamo il valore del gioco v e le strategie ottimali (p1 , p2) e (q1 , q2)


v = Det(X) = ad - bc = 20 - 3 = 17

D a+d-b-c 5 5


p1 = d - c = 2 p2 = 1 - p1 = 3

D 5 5


q1 = d - b = 4 q2 = 1 - q1 = 1

D   5 5


Calcoliamo infine il valore atteso E(X) nel momento in cui si utilizzano le strategie ottimali:


E(X) = 4 2 4 + 1 2 1 + 3 3 4 + 5 3 1 = 32 + 2 + 36 + 15 = 85 = 17 = v

5 5 5 5 5 5 5 5 25 25 25 25 25 5



32) Consideriamo la seguente matrice di gioco:


20, 0 0, 10

0, 90 20, 0

Individuare, se esistono:

- strategie dominanti

- equilibri puri di Nash (sia basandosi sulla definizione, sia utilizzando l'algoritmo parentesi tonde-quadre)

- equilibri misti

Verificare se il gioco è equo, cioè se, in condizioni di equilibrio, coincidono i valori attesi delle vincite per R e per C.

Non ci sono strategie dominanti. Vediamo se ci sono equilibri puri:


(20), 0 0, [10]

0, [90] (20), 0

Non vi sono equilibri puri.

In accordo con la definizione di equilibrio, la strategia (riga 1, colonna 1) non è un equilibrio di Nash in quanto, se R sceglie la riga 1, a C conviene la colonna 2. Lo stesso accade per le altre tre strategie.

Possiamo cercare un equilibrio in strategie miste.

Supponiamo che R scelga la riga 1 per cui p1 = 1 e C adotti la strategia mista (q1, q2) = (q, 1-q), allora la vincita media di R sarà:


2

E(riga 1) = S x1 j p1 qj = 20 x 1 x q + 0 x 1 x (1-q) = 20q

j=1


Analogamente, una volta che R ha scelto la riga 2, p2 = 1 e la vincita media di R sarà:

2

E(riga 2) = S x2 j p2 qj = 0 x 1 x q + 20 x 1 x (1-q) = 20(1-q)

j=1


Ora, quello che vuole C è che per R sia indifferente scegliere riga 1 o riga 2, cioè scegliere una riga invece che l'altra non deve dare a R alcun vantaggio. In altri termini, la vincita media di R scegliendo la riga 1 deve essere uguale a quella ottenuta scegliendo la riga 2, cioè deve essere:


20q = 20(1 - q)


40q = 20


q = 20/40 = 1/2


1-q = 1 - 1/2 = 1/2


In conclusione, la strategia di C che rende a R indifferente ai fini della vincita media la scelta della riga 1 o della riga 2 è individuata dal vettore (q1, q2) = (1/2, 1/2).


Simmetricamente, anche R vuole che C non abbia motivo per preferire la colonna 1 alla colonna 2 o viceversa.

Ora, nel momento in cui C sceglie la colonna 1, q1 = 1 e il valore atteso della sua vincita dipende solo dalla strategia di R, descritta dal vettore (p1, p2) = (p, 1-p). La vincita media di C relativa alla scelta della colonna 1 è:


2

E(colonna 1) = S xi 1 pi q1 = 0 x p x 1 + 90 x (1-p) x 1 = 90(1 - p)

i=1


Analogamente, una volta che C ha scelto la colonna 2, q2 = 1 e la vincita media di C sarà:

2

E(colonna 2) = S xi 2 pi q2 = 10 x p x 1 + 0 x (1-p) x 1 = 10p

i=1


L'obiettivo di R è che per C sia indifferente scegliere colonna 1 o colonna 2, cioè scegliere una colonna invece che l'altra non deve avvantaggiare R. In altri termini, la vincita di C scegliendo la colonna 1 deve essere uguale a quella ottenuta scegliendo la colonna 2, cioè deve essere:


90(1 - p) = 10p


90 = 100p


p = 90/100 = 9/10


1-p = 1 - 9/10 = 1/10


In conclusione, la strategia di R che rende a C indifferente, ai fini della vincita media, la scelta della colonna 1 o della colonna 2 è individuata dal vettore (p1, p2) = (9/10, 1/10).


Abbiamo perciò individuato un equilibrio misto descritto dalla coppia di strategie:


(p1, p2) = (9/10, 1/10)


(q1, q2) = (1/2, 1/2)


Vediamo quali sono, con la strategia mista, le vincite medie per R e C:


E(R) = 20 9/10 1/2 + 20 1/10 1/2 = 180/20 + 20/20 = 200/20 = 10


E(C) = 90 1/10 1/2 + 10 9/10 1/2 = 90/20 + 90/20 = 180/20 = 9

Come si vede, il gioco non è equo in quanto la vincita attesa di R è maggiore di quella di C.






Privacy




Articolo informazione


Hits: 2111
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2024