Dsy Network>  www | forum | my | didattica | howto | wiki | el goog | stats | blog | dona | rappresentanti
Homepage
 Register   Calendar   Members  Faq   Search  Logout 
.dsy:it. : Powered by vBulletin version 2.3.1 .dsy:it. > Didattica > Corsi A - F > Algoritmi e strutture dati > Informazione
Pages (3): « 1 [2] 3 »   Last Thread   Next Thread
Author
Thread    Expand all | Contract all    Post New Thread    Post A Reply
Collapse
CaboM.BNA
.grande:maestro.

User info:
Registered: Jan 2006
Posts: 503 (0.07 al dì)
Location:
Corso:
Anno:
Time Online: 1 Day, 23:32:44 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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."
24-07-2007 17:58
Click Here to See the Profile for CaboM.BNA Click here to Send CaboM.BNA a Private Message Find more posts by CaboM.BNA Add CaboM.BNA to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
mark
.grande:maestro.

User info:
Registered: Oct 2003
Posts: 783 (0.10 al dì)
Location:
Corso: F49
Anno: finito!
Time Online: 8 Days, 18:34:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

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.....
24-07-2007 20:10
Click Here to See the Profile for mark Click here to Send mark a Private Message Find more posts by mark Add mark to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
CaboM.BNA
.grande:maestro.

User info:
Registered: Jan 2006
Posts: 503 (0.07 al dì)
Location:
Corso:
Anno:
Time Online: 1 Day, 23:32:44 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.
24-07-2007 22:08
Click Here to See the Profile for CaboM.BNA Click here to Send CaboM.BNA a Private Message Find more posts by CaboM.BNA Add CaboM.BNA to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
mark
.grande:maestro.

User info:
Registered: Oct 2003
Posts: 783 (0.10 al dì)
Location:
Corso: F49
Anno: finito!
Time Online: 8 Days, 18:34:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.....
25-07-2007 06:35
Click Here to See the Profile for mark Click here to Send mark a Private Message Find more posts by mark Add mark to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
CaboM.BNA
.grande:maestro.

User info:
Registered: Jan 2006
Posts: 503 (0.07 al dì)
Location:
Corso:
Anno:
Time Online: 1 Day, 23:32:44 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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 ?


cioè se fosse non prefisso (e qundi nel linguaggio esisterebbero dei prefissi), le parole corrispondenti ai prefissi SAREBBERO PROPRIO QUELLE ASSOCIATE AI NODI INTERNI...
adex mi riaggancio a quello scritto nel post precedente..

ecco il link ad un'immagine, cosi mi spiego con un esempio...
Del linguaggio fanno parte i simboli: a,b,c,d,e,f,p (il pallino in basso a dx nel disegno sarebbue una "e").
Questi simboli vengono codificati in bit con le seguenti sequenze di bit (e percio parole): a=0, p=1, c=100, b=101, d:111, f=1100, e=1101.
SE NON vi fossero simboli associati ai nodi interni, ma solo alle foglie, in percorso per arrivare ad ogni foglia è univoco e diverso da altri percorsi. Per arrivare a "f" seguo lo stesso percorso che userei per arrivare al nodo "e" (ossia '110'), ma arrivato al nodo interno "14" i due percorsi differiscono per l'ultimo bit.
Poiche vi è un simbolo ASSOCIATO AD UN NODO INTERNO, tutti i percorsi che passano da quel nodo (e quindi tutte le parole che in binario iniziano per '1') hanno "p" come prefisso. Se vogliamo arrivare "a","b","c","d","e","f" PASSIAMO PER FORZA da "p"; perciò "p" è un prefisso.
25-07-2007 09:37
Click Here to See the Profile for CaboM.BNA Click here to Send CaboM.BNA a Private Message Find more posts by CaboM.BNA Add CaboM.BNA to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
mark
.grande:maestro.

User info:
Registered: Oct 2003
Posts: 783 (0.10 al dì)
Location:
Corso: F49
Anno: finito!
Time Online: 8 Days, 18:34:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.....
25-07-2007 16:44
Click Here to See the Profile for mark Click here to Send mark a Private Message Find more posts by mark Add mark to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
mark
.grande:maestro.

User info:
Registered: Oct 2003
Posts: 783 (0.10 al dì)
Location:
Corso: F49
Anno: finito!
Time Online: 8 Days, 18:34:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.....
28-07-2007 18:38
Click Here to See the Profile for mark Click here to Send mark a Private Message Find more posts by mark Add mark to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
CaboM.BNA
.grande:maestro.

User info:
Registered: Jan 2006
Posts: 503 (0.07 al dì)
Location:
Corso:
Anno:
Time Online: 1 Day, 23:32:44 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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)
28-07-2007 19:19
Click Here to See the Profile for CaboM.BNA Click here to Send CaboM.BNA a Private Message Find more posts by CaboM.BNA Add CaboM.BNA to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
mark
.grande:maestro.

User info:
Registered: Oct 2003
Posts: 783 (0.10 al dì)
Location:
Corso: F49
Anno: finito!
Time Online: 8 Days, 18:34:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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)



da come esponeva le cose sembra che gli desse molta importanza. Se hai notato, serviva per introdurre quel famoso theta(n^2). Non conoscendo il docente non è facile comprendere cosa serve, ah...

Hai visto il riassunto delle videolezioni qui sul dsy ?

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....
28-07-2007 19:23
Click Here to See the Profile for mark Click here to Send mark a Private Message Find more posts by mark Add mark to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
CaboM.BNA
.grande:maestro.

User info:
Registered: Jan 2006
Posts: 503 (0.07 al dì)
Location:
Corso:
Anno:
Time Online: 1 Day, 23:32:44 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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:shock:
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)
28-07-2007 19:26
Click Here to See the Profile for CaboM.BNA Click here to Send CaboM.BNA a Private Message Find more posts by CaboM.BNA Add CaboM.BNA to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
CaboM.BNA
.grande:maestro.

User info:
Registered: Jan 2006
Posts: 503 (0.07 al dì)
Location:
Corso:
Anno:
Time Online: 1 Day, 23:32:44 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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

Last edited by CaboM.BNA on 28-07-2007 at 20:29
28-07-2007 19:28
Click Here to See the Profile for CaboM.BNA Click here to Send CaboM.BNA a Private Message Find more posts by CaboM.BNA Add CaboM.BNA to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
mark
.grande:maestro.

User info:
Registered: Oct 2003
Posts: 783 (0.10 al dì)
Location:
Corso: F49
Anno: finito!
Time Online: 8 Days, 18:34:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.....

Last edited by mark on 29-07-2007 at 09:09
29-07-2007 07:58
Click Here to See the Profile for mark Click here to Send mark a Private Message Find more posts by mark Add mark to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
CaboM.BNA
.grande:maestro.

User info:
Registered: Jan 2006
Posts: 503 (0.07 al dì)
Location:
Corso:
Anno:
Time Online: 1 Day, 23:32:44 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.
29-07-2007 10:56
Click Here to See the Profile for CaboM.BNA Click here to Send CaboM.BNA a Private Message Find more posts by CaboM.BNA Add CaboM.BNA to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
mark
.grande:maestro.

User info:
Registered: Oct 2003
Posts: 783 (0.10 al dì)
Location:
Corso: F49
Anno: finito!
Time Online: 8 Days, 18:34:33 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.



grazie

p.s.
in ultima analisi, a me sembra che abbia mostrato un certo numero di metodi per determinalre il numero di passi per risolvere un problema o sbaglio ?

nell'ordine:

- log2(n)
- n^2
- Gauss

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

Last edited by mark on 29-07-2007 at 11:48
29-07-2007 11:04
Click Here to See the Profile for mark Click here to Send mark a Private Message Find more posts by mark Add mark to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
Collapse
CaboM.BNA
.grande:maestro.

User info:
Registered: Jan 2006
Posts: 503 (0.07 al dì)
Location:
Corso:
Anno:
Time Online: 1 Day, 23:32:44 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

si... il numero di passi o tempo necessario...
29-07-2007 12:18
Click Here to See the Profile for CaboM.BNA Click here to Send CaboM.BNA a Private Message Find more posts by CaboM.BNA Add CaboM.BNA to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
All times are GMT. The time now is 12:52.    Post New Thread    Post A Reply
Pages (3): « 1 [2] 3 »   Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread | Add to Bookmarks

Forum Jump:
Rate This Thread:

Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts 		HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON
 

Powered by: vBulletin v2.3.1 - Copyright ©2000 - 2002, Jelsoft Enterprises Limited
Mantained by dsy crew (email) | Collabora con noi | Segnalaci un bug | Archive | Regolamento | Licenze | Thanks | Syndacate
Pagina generata in 0.047 seconds (76.89% PHP - 23.11% MySQL) con 26 query.