.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- Informazione (http://www.dsy.it/forum/showthread.php?threadid=31602)

cito Torelli: (from videolezioni)
"è guradando l'albero che possiamo dimostrarlo: una parola è di codice è associata alle foglie (e non ai nodi interni!) e le stringhe che corrispondono ai prefissi sono quelle che si fermano ai nodi interni... Noi arriviamo SEMPRE ad una foglia e non ci fermiamo mai prima di arrivare ad una foglia; dunque di prefissi non ce ne sono. Il fatto di associare le parole alle foglie ci garantisce che è un codice prefisso."

ho ascoltato quel pezzo 10 volte ma non ne ho ricavato nulla, sarà la stanchezza, nemmeno ora da quello che mi scrivi

quello che sono riuscito a trascrivere detto dal prof:

guardando l'albero si vede subito se un codice è prefisso perchè associamo sempre un codice ad una foglia e ciò garantisce che è prefisso

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Cerco di spegarlo con altre parole...
Le foglie differiscono tutte PER ALMENO 1 BIT... Sicché non possiamo mai avere 2 parole uguale... Quando "crei" una parola (p1), parti dalla radice e poi segui un percorso univoco nodo per nodo fino a quando non arrivi alla foglia. Se vi fosse un prefisso (p2), dovrebbero esservi parole termanano ad un nodo interno, in modo che il percorso che segui per arrivare a p2 concida, cioè SIA PARTE, del percorso che seguiresti per arrivare a p1.

vuoi dire che se un codice non fosse prefisso avremmo lettere posizionate all'interno dei nodi dell'albero in quanto alcune lettere, anzichè fermarsi solo come foglie diverrebbero anchesse nodi e verrebbero "sfondati"(passami il termine) da parole prefisse ?

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

la prima parte ok, ma non capisco questa frase...

Originally posted by mark
... alcune lettere, anzichè fermarsi solo come foglie diverrebbero anchesse nodi e verrebbero "sfondati"(passami il termine) da parole prefisse ?

lo avevo capito proprio così, coem lo hai spiegato ora, anche se dalle mie parole forse non si era molto capito molto

mi sono fatto anche un banale esempio con tali dati:

a=0; b=01; c=10

frequenze
a=30; b=10; c=5

e poi costruendo l'albero si vede proprio che sullo stesso cammino(nodo interno) della lettera 'a' ci passa la lettera 'b', quindi il codice da me proposto non è prefisso in quanto il codice di 'a' è prefisso per il codice di 'b' e non è univoco

grazie 1000

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

a me della videolezione 1 è rimasto un dubbio. Si parla di problemi di dimensione n e il prof dice che, se per ridurlo di una dimensione uso sempre il medesimo numero di passi, es: 10, allora i passi totali saranno n*n e cioè n^2.

Poi, enuncia un certo k e dice che se un problema è di dimensioni 1 e poi 2 e poi 3 e poi k, n^2 non è più valido per determinare il numero di passi necessari per risolvere il problema; e tira in ballo la "somma" di Gauss.... ??????

Help

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

confesso che non mi ricordo bene di tutto quello su cui ha parlato/divagato...
cmq non te preocupe... quella parte li "non serve"... io mi son segnato veramente poca roba...

l'unica cosa che ho trovato interessante (oltra all'idea su come si fa a calcolare la somma di Gauss) è stata: "SE HO UN PROBLEMA DI DIMENSIONE n E AD OGNI PASSO DIMEZZO IL MIO PROBLEMA, DOPO QUANTI PASSI RIDUCO IL MIO PROBLEMA ALLA DIMENSIONE 1? DOPO lg(n) PASSI."

il resto, a mio avviso lo puoi tranquillamente lasciare perdere... (la max dai un'occhiata sul libro a come calcolare i fattoriali, come dice Torelli)

Originally posted by CaboM.BNA
confesso che non mi ricordo bene di tutto quello su cui ha parlato/divagato...
cmq non te preocupe... quella parte li "non serve"... io mi son segnato veramente poca roba...

l'unica cosa che ho trovato interessante (oltra all'idea su come si fa a calcolare la somma di Gauss) è stata: "SE HO UN PROBLEMA DI DIMENSIONE n E AD OGNI PASSO DIMEZZO IL MIO PROBLEMA, DOPO QUANTI PASSI RIDUCO IL MIO PROBLEMA ALLA DIMENSIONE 1? DOPO lg(n) PASSI."

il resto, a mio avviso lo puoi tranquillamente lasciare perdere... (la max dai un'occhiata sul libro a come calcolare i fattoriali, come dice Torelli)

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

io comincio a postare il mio dubbio... tu ci metterai un po ad arrivarci, vito che è la (video)lezione del 14-10-2003, ma magari oltre a noi altri PAZZI studiamo algoritmi ad agosto...

heap
trattasi dell'ultimo pezzetto del paragrafo 3.2, delgli appunti di Torelli sugli HEAP. Il mio problema è la frase sottolineata. Piu che italiano mi pare sumero antico. Non ho capito ASSOLUTAMENTE NULLA (mentre tutto quello che è stato detto precendetemente mi è sembrato chiaro)

trovati i riassunti... dopo che me l'hai detto li ho visto nell'area filez... ben fatti, saranno sicuramente utili...

ho visto il pezzo a cui ti riferivi...
la questione è piuttosto semplice.
HO UN PROBLEMA DI DIMENSIONE n. SUPPONIAMO CHE PER RIDURRE DI 1 LA DIMENSIONE DEL MIO PROBLEMA (E PERCIO FARLO DIVENTARE DI DIMENSIONE n-1) IO CI IMPIEGO n TEMPO. ADESSO DOBBIAMO RISOLVERE UN PROBLEMA DI DIMENSIONE n-1. POI AVRO UN PROBLEMA DI DIMENSIONE n-2... ETC.
DOPO n OPERAZIONI ARRIVERO AD AVERE UN PROBLEMA DI DIMENSIONE 1. SICCOME OGNI OPERAZIONE MI E' COSTATA n TEMPO, IN TUTTO CI AVRO IMPIEGATO n*n TEMPO.
k viene citato solo per spiegarti PERCHE si vogliono n passi. fare n-1, poi (n-1)-1, poi ((n-1)-1)-1 richiede lo stesso numero di passi anche se andassimo "alla rovescia" (e percio da 1 ad n): 1, poi 1+1, poi (1+1)+1... devo in ogni caso fare n operazioni. [sia che decrementi di 1 alla volta partendo da n, sia che sommi +1 ogni volta partendo da 1]
......

continuo domani... adex devo uscire perche sono in ritadro... byez

cito il prof, o quasi



ho un problema di dimensione n e impiego tempo n per ridurre di 1 la dimensione del problema e facendo n operazioni ora ho ridotto il problema a dimensione n-1

quante operazioni per arrivare a problema di didmensione 1 ?

se il numero di passi fosse sempre n e lo faccio per n volte il numero di passi sarebbe n^2.

Ma se ho dimensione del problema variabile ? dimens 1, poi dimens 2, poi dimens 3, poi dimens 4, poi dimens 5, poi dimens 6, come faccio ?

numero di passi sarà ancora n^2 ?
sarà dell'ordine di n^2 ma quanto precisamente ?


entra in ballo Gauss!

somma di
0+100
1+99
2+98
etc...sempre 100
e
1+2+3+4+5+6+7.....100

li metto insieme nel modo indicato negli appunti del prof e divido per due, ottenendo 5050, e quindi ?

quanto sopra è dell'ordine di n^2


chiari i vari passaggi rispetto agli appunti del prof, ma no capisco l'aggancio col problema di dimensione variabile, boh!

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

in sostanza: io ho un problema che ha complessità 1, poi 2, poi 3... e cosi fino a n. Per calcolare il tempo che ci metto a risolverlo uso la somma di Gauss. Il risultato ottenuto è dell'ordine di grandezza di n^2.

Originally posted by CaboM.BNA
in sostanza: io ho un problema che ha complessità 1, poi 2, poi 3... e cosi fino a n. Per calcolare il tempo che ci metto a risolverlo uso la somma di Gauss. Il risultato ottenuto è dell'ordine di grandezza di n^2.

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

si... il numero di passi o tempo necessario...