 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[Algoritmi e strutture dati - Torelli] Dubbi
Clicca QUI per vedere il messaggio nel forum |
| eugenio_2 |
Ciao a tutti,
ho alcuni dubbi, li posto nella speranza che qualcuno sappia aiutarmi :)
Il libro di testo (versione inglese) usa spesso il termine key, il problema e' che mi sembra lo usi con significati diversi; prendiamo ad esempio l'elemento a[4] = 6 di un array a; a volte mi sembra che key si rifersca all'indice 4, a volte al suo valore 6.
Riguardo al metodo dell'open addressing: in sostanza si mettono tutti gli elementi che abbiamo necessita' di memorizzare nella tabella di hash, e n/m non puo' superare 1; ma non si e' approdati alla tecnica di hashing proprio per evitare di dover avere a disposizione tanti slot quanti sono i diversi elementi che vogliamo memorizzare?
Sul sito del Prof. Torelli (http://homes.dsi.unimi.it/~torelli/argomenti03.html) leggo che:
"Alberi binari di ricerca: un albero in cui ogni figlio sinistro è minore del padre e ogni figlio destro è maggiore NON è necessariamente di ricerca! (testo § 13.1)."
Chi mi sa dare una spiegazione di questa affermazione?
Grazie.
Ciao. |
| HeavyLoaded |
solitamente (credo) il nome key è associato ad un indice e non al valore contenuto nella struttura di indice key.
per intenderci
A[4] = 6
key = 4
valore = 6.
sul libro di testo (italiano ^^) di algo viene sempre utilizzato come indice.
spero di averti dato una mano.
Ciauuz ^^
ps: posso anche sbagliare ovviamente. lol |
| eugenio_2 |
Originally posted by HeavyLoaded
[B]solitamente (credo) il nome key è associato ad un indice e non al valore contenuto nella struttura di indice key.
Ok, grazie per la risposta! |
| Benjamin |
è esattamente il contrario!
per kiave si inende sempre l'informazione è come se fosse una chiava di un Db....4 è semplicemente l'indice!
Per l'indirizzamento aperto:si mettono tutti gli elementi nella tabella di hash,che è cmq limitata,per questo c'è bisogno di scandire diverse posizioni alla ricerca di una posizione libera!questo non vuol dire che siamo nella situazione dell'indirizzamento diretto in cui tutte le chiavi erano memorizzate!
per quanto riguarda l'albero...bè deve essere binario!e poi mancano gli uguali nelle due relazioni!!
posso sbagliarmi...pero questo è quello che so!
ciao |
| eugenio_2 |
Originally posted by Benjamin
è esattamente il contrario!
per kiave si inende sempre l'informazione è come se fosse una chiava di un Db....4 è semplicemente l'indice!
Ah, ok :)
Originally posted by Benjamin
Per l'indirizzamento aperto:si mettono tutti gli elementi nella tabella di hash,che è cmq limitata,per questo c'è bisogno di scandire diverse posizioni alla ricerca di una posizione libera!questo non vuol dire che siamo nella situazione dell'indirizzamento diretto in cui tutte le chiavi erano memorizzate!
[/B]
Non ti seguo, se n/m non puo' superare 1 allora gli slot m non possono essere minori degli elementi n che vogliamo memorizzare, quindi perche' dici che e' limitata?
Originally posted by Benjamin
per quanto riguarda l'albero...bè deve essere binario!e poi mancano gli uguali nelle due relazioni!!
posso sbagliarmi...pero questo è quello che so!
ciao [/B]
Giusto, mi era sfuggito.
Grazie! |
| Benjamin |
n si riferisce agli elementi effetivamente memorizzati nella tabella...e m gli slot a disposizione....
quindi sara sempre minore di 1.... |
| eugenio_2 |
Originally posted by Benjamin
n si riferisce agli elementi effetivamente memorizzati nella tabella...e m gli slot a disposizione....
quindi sara sempre minore di 1....
Ah ok, pensavo n = numero degli elementi che vogliamo memorizzare.
Grazie. |
| Moffone |
Originally posted by eugenio_2
Ah ok, pensavo n = numero degli elementi che vogliamo memorizzare.
Grazie.
Dal Libro (ver italiana)
Data una tabella hash T con m posizioni che memorizza n elementi, si definisce il fattore di carico "alfa" per T come n/m, cioè il numero medio di elementi memorizzati in ogni lista concatenata.
Quindi n è il numero di elementi memorizzati in un certo istante nella tabella e non il numero totale di elementi dell'insieme. |
| Moffone |
Per quanto riguarda lo pseudocodice che spiega come risolvere le collisioni con liste concatenate in tabelle hash:
Chaine-Hash-Delete(T, k)
-cancella x dalla lista T[h(key[x])]
l'intestazione della funzione è sbagliata?
secondo me dovrebbe essere:
Chaine-Hash-Delete(T, x) oppure se passo k dovrebbe rimuovere l'elemento T[h(k)]? |
| Gusher |
<quote>
secondo me dovrebbe essere:
Chaine-Hash-Delete(T, x) oppure se passo k dovrebbe rimuovere l'elemento T[h(k)]?
</quote>
Ricordo di aver riscontrato il tuo stesso problema durante una lezione di Trubian, cmq. il Cormen intende che key[x] sia K
(il parametro). Sostanzialmente fa un passo indietro e ti fa vedere esplicitamente da cosa proviene quella k.. tutto qui! |
| eugenio_2 |
Approfitto del thread, senza aprirne uno nuovo, per chiedere chiarimenti riguardo al programma.
Ho il libro di testo in inglese (seconda edizione) e, premesso che ho gia' letto l'indice della prima versione in inglese presente nell'area filez, rimangono alcuni paragrafi / teoremi / pagine di cui non riesco a trovare la corrispondenza tra quanto citato dal professore, riferito alla prima edizione, e la seconda edizione.
Faccio riferimento a http://homes.dsi.unimi.it/~torelli/argomenti03.html:
- 17 ottobre: cenno agli algoritmi probabilstici (testo 33.8)
- 2 dicembre: teofrema 12.5 del testo (11.5 della seconda edizione?)
- 5 dicembre, pag. 238 e enunciato teorema 13.6
- 16 gennaio: teorema 17.10 - saltare da pag 467 a fine capitolo
- 22 gennaio: saltare da pagina 351 alla fine
- 23 gennaio: testo pagina 907
Facendo riferimento invece a:
http://homes.dsi.unimi.it/~torelli/mod_esame03.html
- pagine da 81 a 95
- teorema 13.6
- funzione di Ackermann (dov'e' spiegata nella seconda edizione).
Grazie mille. |
| Moffone |
Pag 216
12.3.3 FUNZIONE HASH UNIVERSALE
...Tale insieme è detto universale se per ogni coppia di chiavi distinte x,y Є U, il numero di funzioni hash h Є H per cui h(x) = h(y) è precisamente...
Qualcuno può aiutarmi a concludere questa frase? fino al punto.
Ho il libro fotocopiato e nel mettere la spirale si è cancellato l'ultimo simbolo e non riesco a capire la formula...
Grazie |
| eugenio_2 |
Per quanto riguarda i tempi di progetto ed esame orale: solitamente ci sono due settimane per consegnare il progetto, poi come e dopo quanto si sa se il progetto e' giudicato sufficiente per accedere all'orale? E dopo quanto iniziano gli orali?
Saremo in tanti secondo voi per il progetto del 6 Aprile?
Parlo sempre di Torelli-Fiorentini.
Grazie. |
| Moffone |
| quando mi sono iscritto io sono stato messo in lista come numero 49. |
| eugenio_2 |
Originally posted by Moffone
quando mi sono iscritto io sono stato messo in lista come numero 49.
Con Torelli?
Io mi sono appena iscritto e mi da' 41.
Sai nulla riguardo ai tempi tra progetto e orale e per quanto vanno avanti gli orali? |
| Moffone |
Avevo letto il calendario per andare a vedere un appello. Poi non ci son andato!
Mi sembra che durassero più di una settimana, però non ne faceva più di 5 al giorno e non tutti i giorni.
Cmq se cerchi un po' sul sito, magari li trovi ancora |
| Asciapazza |
In genere sceglie uno o due giorni alla settimana e va avanti mettendo un massimo di dieci persone al giorno.
Gli orali iniziano circa dalla settimana successiva alla data di consegna ultima del progetto.
Saluti... |
| eugenio_2 |
Originally posted by Asciapazza
In genere sceglie uno o due giorni alla settimana e va avanti mettendo un massimo di dieci persone al giorno.
Gli orali iniziano circa dalla settimana successiva alla data di consegna ultima del progetto.
Saluti...
Grazie per la risposta.
Come funziona se uno passa il progetto ma non l'orale? Puo' ripresentarsi al successivo appello saltando il progetto o deve rifare tutto? |
| loreste |
Per quanto mi è stato detto, se passi il progetto e l'orale dell'assistente sei a posto..... poi quando vai da Torrelli dovrebbere essere una quartione di voto, però è solo una voce.
Speriamo in bene |
| eugenio_2 |
Originally posted by loreste
Per quanto mi è stato detto, se passi il progetto e l'orale dell'assistente sei a posto..... poi quando vai da Torrelli dovrebbere essere una quartione di voto, però è solo una voce.
Speriamo in bene
Cioe' sarebbe a dire che Torelli non boccia? Non credo, in un altro post qualcuno parlava proprio di uno studente bocciato prima di lui.
Qualcuno sa qualcosa di piu'? |
| Viry |
Originally posted by eugenio_2
Cioe' sarebbe a dire che Torelli non boccia? Non credo, in un altro post qualcuno parlava proprio di uno studente bocciato prima di lui.
Qualcuno sa qualcosa di piu'?
Normalmente Torelli e' abbastanza "buono", quindi e' difficile che bocci. Difficile pero' non vuol dire impossibile, se uno non sa nulla e ha fatto un progetto del cavolo... |
| eugenio_2 |
Originally posted by Viry
Normalmente Torelli e' abbastanza "buono", quindi e' difficile che bocci. Difficile pero' non vuol dire impossibile, se uno non sa nulla e ha fatto un progetto del cavolo...
E Fiorentini com'e'? |
| loreste |
| Un mio amico ha detto che chiede parecchie cose, inizialmente perchè vuole capire se il progetto l'hai fatto tu o qualcuno altro, poi vuole sapere perchè hai usato qulla struttura e quell'algoritmo |
| Asciapazza |
Io sono stato segato da Torelli all'orale.
Il progetto era buono, ma la teoria era tabula rasa e mi ha detto di tornare l'appello successivo tenendomi comunque valido il progetto (andavo a ripetere solo l'orale).
Cmq in linea generale se riesci a dire qualcosa non ti boccia, sono stato un caso eccezionale siccome non ho proprio detto nulla.
Fiorentini ti chiede due cose sul tuo progetto, cose che in teoria dovresti aver già scritto sulla relazione.
Saluti... |
| eugenio_2 |
Originally posted by Asciapazza
Io sono stato segato da Torelli all'orale.
Il progetto era buono, ma la teoria era tabula rasa e mi ha detto di tornare l'appello successivo tenendomi comunque valido il progetto (andavo a ripetere solo l'orale).
[....]
Erano complesse le domande o proprio ti sei presentato a digiuno? :) |
| Asciapazza |
Le voci mi dicevano che bastasse fare bene il progetto e poi anche se non sapevi nulla da Torelli uscivi lo stesso.
Mi sono fidato ciecamente e me la sono presa nel culo...
L'appello dopo mi ha fatto passare per primo e il calcio nel culo me l'ha dato.
Saluti... |
| eugenio_2 |
Originally posted by loreste
Un mio amico ha detto che chiede parecchie cose, inizialmente perchè vuole capire se il progetto l'hai fatto tu o qualcuno altro, poi vuole sapere perchè hai usato qulla struttura e quell'algoritmo
Ma se hai passato il progetto lo sai il giorno dell'orale? |
|
|
|
|
