| V I S U A L I Z Z A D I S C U S S I O N E |
| softmystery |
Inserito il - 28/12/2009 : 22:11:55
Salve, mi sto' preparando per l'esame e vorrei un chiarimento.
La traccia del 22/01/09 quesito n.5 dice di scrivere un algoritmo per la ricerca di UN valore false in un array di boolean, e di determinare la complessita nei casi ottima pessima e media.
La mia domanda e':sulle slide c'e' un esempio che determina la posizione del PRIMO valore false all'interno di array di boolean, quindi bastava scivere quell'esempio nell'esame? E poi per il calcolo della complessita' media, davvero bisognerebbe calcolare la media pesata dei costi di ogni singolo evento?
Grazie in anticipo per coloro che mi sapranno rispondere! |
| 4 U L T I M E R I S P O S T E (in alto le più recenti) |
| nicolamonaca |
Inserito il - 09/01/2010 : 12:19:52
Ops, è vero...avevo notato la piccola differenza linguistica ma nello scrivere la risposta mi era sfuggita, evidentemente...ma la risposta rimane comunque valida, vero? Perchè secondo me cercare UN valore implica cercare il PRIMO valore. A meno di una smentita.
PS: il fatto di dover rispondere ad una domanda così relativamente complessa in sede d' esame senza avere un esempio svolto mi preoccupava un poco, effettivamente; ma ora che ha chiarito sono più tranquillo, grazie.
|
| Malerba |
Inserito il - 08/01/2010 : 09:28:40
Citazione:
Messaggio inserito da nicolamonaca
Ciao, per quanto riguarda l' esercizio della ricerca del FALSE in un array, immagino che l' esercizio sia stato inserito nelle slides DOPO averlo proposto in sede d' esame, quindi non è che bastava inserire quell' esempio nell' esame; semmai è stato fatto il contario.
No, non è andata proprio così. L'esercizio era volutamente una variante linguistica di quello presentato a lezione e già riportato sulle slide.
Nonostante questo ... lasciamo perdere.
|
| nicolamonaca |
Inserito il - 04/01/2010 : 19:37:08
PS: per caso hai i file dell' ultima esercitazione sugli alberi? Purtroppo sono stato assente per l' unica volta a quell' esercitazione e vorrei darmi un' occhiata veloce all' argomento poichè non ho tempo per svilupparlo interamente!
|
| nicolamonaca |
Inserito il - 04/01/2010 : 19:33:55
Ciao, per quanto riguarda l' esercizio della ricerca del FALSE in un array, immagino che l' esercizio sia stato inserito nelle slides DOPO averlo proposto in sede d' esame, quindi non è che bastava inserire quell' esempio nell' esame; semmai è stato fatto il contario.
Per quanto riguarda la complessità: la difficoltà non è tanto il caso ottimo e pessimo, quanto il caso medio. In ogni caso, ciò che devi fare è:
1) Individuare la DISTRIBUZIONE DI PROBABILITA', cioè determinare che probabilità hanno tutte le possibili configurazioni di essere presenti;
2) Scrivere in qualche modo una tabella o uno schema riassuntivo di tutte le possibili configurazioni (non indispensabile ai fini dell' esercizio in sè, ma molto utile per svilupparlo);
3) Tenendo a mente lo scopo dell' esercizio (la ricerca del primo FALSE in una array), individuare la probabilità di ogni singola configurazione, cioè:
E1: A[1] = false ha probabilità P(E1) = 1/2 // false si trova in prima posizione
E2: A[1] = true ^ A[2] = false ha probabilità P(E2) = 1/4 // false si trova in seconda posizione
In generale:
Ek: A[1] = true ^ A[2] = true ^ ... ^ A[k-1] = true ^ A[k] = false, con k<=n, ha probabilità P(Ek) = 1/(2^k) // false si trova in k-esima posizione
Infine dobbiamo considerare l' evento in cui false non è presente nell' array:
En+1: A[1] = true ^ ... ^ A[n] = true ha probabilità P(En+1) = 1/(2^n)
A questo punto possiamo effettivamente calcolare fMED (n). Ma ci manca ancora una cosa: poichè fMED (n) = SOMMATORIA[i=0 to n+1] P(Ei) * costo(Ei), dobbiamo calcolarci i costi dei singoli Ei, ma niente di più facile: costo(E1) = 1 poichè faccio un solo confronto, costo(E2) = 3 per lo stesso motivo, in generale: costo(Ek) = 1 + 2(k-1), infine costo (En+1) = 1 + 2n.
Ora possiamo scrivere fMED (n) = ((1/2) * 1) + ((1/4) * 3) + ... + ((1/(2^k) * (1 + 2(k - 1)))) + ... + ((1/(2^n)) * (1 + 2n - 2)) + ((1/(2^n)) * (1+ 2n)). [Nota che il primo termine della i-esima moltiplicazione rappresenta la PROBABILITA' dell' evento i, mentre il secondo termine rappresenta il COSTO dell' evento i].
Da qui, attraverso una non breve sequenza di passaggi atti a semplificare successivamente l' espressione scrivendola in forma esplicita (esplicitando le sommatorie), si arriva a concludere che fMED (n) = 3 - (1/(2^(n-1))). Ora, poichè per ogni n si ha che 2 <= fMED (n) <= 3 e che lim[x->+inf] di fMED (n) = 3, si ha che fMED (n) è di ordine théta(c), con c = costante > 0.
|
|
|
