.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Algoritmi e strutture dati - Torelli] Dubbi (http://www.dsy.it/forum/showthread.php?threadid=9496)

[Algoritmi e strutture dati - Torelli] Dubbi

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.

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

__________________
my site:http://heavylord.splinder.com
my pub:http://www.inkubo.it
- Possiamo vedere nel futuro solo per un piccolo tratto,ma vediamo che in questo piccolo tratto c'è molto da fare
- Non bisogna dare solo anni alla vita,ma anche vita agli anni

Originally posted by HeavyLoaded
[B]solitamente (credo) il nome key è associato ad un indice e non al valore contenuto nella struttura di indice key.

è 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

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!

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]

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]

n si riferisce agli elementi effetivamente memorizzati nella tabella...e m gli slot a disposizione....
quindi sara sempre minore di 1....

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

ouhh

__________________
my site:http://heavylord.splinder.com
my pub:http://www.inkubo.it
- Possiamo vedere nel futuro solo per un piccolo tratto,ma vediamo che in questo piccolo tratto c'è molto da fare
- Non bisogna dare solo anni alla vita,ma anche vita agli anni

Originally posted by eugenio_2
Ah ok, pensavo n = numero degli elementi che vogliamo memorizzare.


Grazie.

__________________
Federazione
Imbroglioni
Giuoco
Calcio

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)]?

__________________
Federazione
Imbroglioni
Giuoco
Calcio

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

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.

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

__________________
Federazione
Imbroglioni
Giuoco
Calcio

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.

quando mi sono iscritto io sono stato messo in lista come numero 49.

__________________
Federazione
Imbroglioni
Giuoco
Calcio