Corsi di Laurea

[|system88|]

Vi voglio proporre la soluzione che ho adottato per risolvere il problema assegnato dal professore ed anche la relativa analogia che, secondo me, può essere fatta con la teoria dell'informazione! 

Sono ben graditi pareri di ogni sorta, purchè costruttivi e/o soluzioni alternative!

 

 

Abbiamo 4 monete: A B C D, una è sicuramente falsa e pesa o più o meno rispetto alle altre 3. Abbiamo una moneta di test E che sappiamo essere sicuramente vera.

Trovare la moneta falsa nel minor numero di passaggi possibile e dire se è più leggera o pesante rispetto alle monete originali.

Abbiamo, inoltre, a disposizione una bilancia che può dare i seguenti valori:
 

- piatti equilibrati

-piatto dx più pesante

-piatto sx più pesante

 

La soluzione la spoilero così se qualcuno non vuole vederla può farne a meno!

Spoiler

I Passo: peso le monete A e B

I evento: La bilancia resta equilibrata
II evento: La moneta A pesa più della B o viceversa

II Passo: Se al passo I si è verificato il I evento so con certezza che una tra le monete C e D è falsa, Ne scelgo una e la confronto con la moneta campione:

I evento: La bilancia è equilibrata, vuol dire che è determinata la moneta falsa e bisogna procedere al III passo per capire se è più leggera o pesante

II evento: La bilancia non resterà equilibrata e, sapendo che la moneta di test è certamente vera ho determinato la moneta falsa ed il suo peso.

Se al I passo si è verificato il II evento si sceglie una moneta e si confronta con la moneta test:

I evento: la bilancia resta in equilibrio, è determinata la moneta falsa e bisogna procedere al passo III per determinarne il peso.

II evento: la bilancia non è equilibrata, è determinata la moneta falsa ed anche il suo peso.

III passo: si pesa la moneta falsa con quella di test per determinarne il peso.

Formalizzando da un punto di vista matematico possiamo dire che:

La sorgente è una sorgente equiprobabile che emette 4 simboli con probabilità 1/4

L'entropia della sorgente è 2 e non possiamo, quindi, impiegare meno di due passaggi per la determinazione della soluzione.

Il numero di passaggi medio, inoltre, è compreso tra l'entropia e l'entropia+1

[Ryuji]

Forse la si può fare sempre con soli 2 passi, ma la domanda è: si possono pesare due monete per piatto o solo una?

 

Spoiler

Passo 1: peso le monete EA e CB su diversi piatti.

Evento 1-1: piatto equilibrato ---> la moneta falsa è D

Passo 2: confronto D con E per vedere se è più leggera o più pesante.

 

Passo 1: peso le monete EA e CB su diversi piatti.

Evento 1-2: piatto non equilibrato --> la moneta falsa è una tra A, C e B.

Passo 2: peso C e B.

Evento 2-1: C e B sono in equilibrio ---> ciò implica che la moneta falsa è la A e posso anche dire anche se è più leggera o pesante a seconda della posizione dei piatti.

Caso EA più basso di CB --> A è più pesante.

Caso CB più basso di EA --> A è più leggera.

Evento 2-2: C e B non sono in equilibrio -->  una delle due è falsa

Caso C più bassa di B && EA più basso di CB --> B è falsa poiché più leggera

Caso C più bassa di B && EA più alto di CB --> C è falsa poiché la più pesante

Caso C più alta di B && EA più basso di CB --> C è falsa poiché più leggera

Caso C più alta di B && EA più alto di CB --> B è falsa poiché la più pesante

[|system88|]

Ci avevo pensato anche io, però non so se è concesso pesare due monete per volta... ci troviamo, comunque, sul numero minimo!

[D]

Gli algoritmi che sono riuscito a tirare fuori sono due, ed in ogni caso il primo non funziona completamente.

Il primo 

 
if(A==B)
{

if(A==C)
{
return D;
}
else
{
return C;
}

}else{

if (A==C)
{
return B;
}
else
{
return A;
}

}

Con questa versione dell'algoritmo eseguo solamente due pesate nel caso peggiore, ma nel caso in cui la moneta falsata è la D non riesco a dire se essa sia più pesante o meno. In tale versione inoltre non uso la moneta equilibrata che porta un tasso di informazione nullo (è deterministica)

 

Nell'altro caso invece 

 
if((a+b)==(d+e))
return c;
else if((a+c)==(d+e)
return b;
else if((a==e)
return d; 
else
return a

In questo caso qui l'idea è:

1) Creo due coppie di elementi ed in una c'è necessariamente la moneta equilibrata. Se si verifica l'evento bilancia equilibrata, ho beccato la moneta, altrimenti no. Rieseguo la pesata accoppiando due delle tre monete rimanenti con le due che so essere equilibrate. Se ripesando ho nuovamente l'equilibrio allora è sicuramente la moneta che non ho considerato ad essere falsata. Altrimenti al risultato della pesata posso ottenere due risultati: se il lato a sx si abbassa o è perchè in quel lato c'è la moneta falsata ed è più pesante oppure è nel lato a dx che abbiamo una moneta più leggera. Ovviamente il risultato si può leggere al contrario. A questo punto, tenendo conto del risultato confronto una delle due con l'equilibrata: se sono uguali so dire che la falsa è l'altra e so anche dire se lo è di più o di meno. Altrimenti so farlo ugualmente.

Non riesco però a concretizzare perchè in questo caso non sappiamo quale siano le probabilità legate alle varie monete ne possiamo supporlo perchè facendolo in qualche modo caratterizziamo completamente lo spazio.

[|system88|]

credo sia legittimo, però, ipotizzare una sorgente equiprobabile, e diciamo che questa supposizione è avvalorata dal fatto che nessuno di noi riesce a scendere al di sotto di 2 passaggi che rappresenterebbe proprio l'entropia della sorgente con 4 simboli equiprobabili! 

Prova a rifare il ragionamento tenendo in conto questa supposizione e vedi che ti esce

[D]

Io credo che come ho detto dipende fondamentalmente da quale sia la cardinalità del nostro alfabeto. Se usiamo la moneta equilibrata gli elementi sono 5 e dunque servono 3 pesate per ottenere la risposta. Nel caso in cui invece non la usiamo, come si evince dal primo algoritmo, allora ne bastano due, con l'unica particolarità che nel caso peggiore di tutte non riesco a determinare la natura dell'ultima (sia essa più pesante o più leggera). Secondo me il ragionamento che bisogna fare è diverso: imporre che la moneta E ha probabilità 1 (e quindi entropia 0) e considerare il nostro spazio composto da 4 elementi di cui 3 con probabilità p/4 e uno con probabilità (1-3/4*p) e partire da questo per formalizzare matematicamente la cosa.

[|system88|]

che si debba considerare una cardinalità pari a 4 perchè la moneta E è deterministica, credo, sia fuori discussione! Resta, quindi, il dubbio sul fatto che si possa o meno asserire che la sorgente sia equiprobabile ed anche sul modo di pesare le monete! Una per piatto o a gruppi... Vediamo se esce fuori qualche altra soluzione e/o considerazione in merito altrimenti aspettiamo giovedì!