eugenio_2

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

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.

HeavyLord

.arcimaestro.

User info:

Registered: Jun 2003
Posts: 278 (0.04 al dì)
Location: hell is home
Corso: Informatica
Anno: 3^
Time Online: 4 Days, 18:30:28 [...]
Status: Offline

Post actions:

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

eugenio_2

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

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

Benjamin

.fedelissimo.

User info:

Registered: Oct 2002
Posts: 59 (0.01 al dì)
Location: lontano!
Corso: Info
Anno: caz..5°
Time Online: 2 Days, 8:56:50 [...]
Status: Offline

Post actions:

è 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

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

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

.fedelissimo.

User info:

Registered: Oct 2002
Posts: 59 (0.01 al dì)
Location: lontano!
Corso: Info
Anno: caz..5°
Time Online: 2 Days, 8:56:50 [...]
Status: Offline

Post actions:

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

eugenio_2

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

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

HeavyLord

.arcimaestro.

User info:

Registered: Jun 2003
Posts: 278 (0.04 al dì)
Location: hell is home
Corso: Informatica
Anno: 3^
Time Online: 4 Days, 18:30:28 [...]
Status: Offline

Post actions:

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

Moffone

.deluso.

User info:

Registered: Nov 2002
Posts: 1016 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: perso il conto
Time Online: 10 Days, 2:15:12 [...]
Status: Offline

Post actions:

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


Grazie.

__________________
Federazione
Imbroglioni
Giuoco
Calcio

Last edited by Moffone on 15-03-2004 at 14:58

Moffone

.deluso.

User info:

Registered: Nov 2002
Posts: 1016 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: perso il conto
Time Online: 10 Days, 2:15:12 [...]
Status: Offline

Post actions:

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

Gusher

Splinter fun club

User info:

Registered: Jan 2003
Posts: 475 (0.06 al dì)
Location: Ovunque
Corso: Informatica
Anno: Done
Time Online: 15 Days, 22:06:15 [...]
Status: Offline

Post actions:

<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

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

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

.deluso.

User info:

Registered: Nov 2002
Posts: 1016 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: perso il conto
Time Online: 10 Days, 2:15:12 [...]
Status: Offline

Post actions:

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

eugenio_2

User info:

Registered: Jun 2003
Posts: 77 (0.01 al dì)
Location:
Corso:
Anno:
Time Online: 17:03:30 [...]
Status: Offline

Post actions:

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

.deluso.

User info:

Registered: Nov 2002
Posts: 1016 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: perso il conto
Time Online: 10 Days, 2:15:12 [...]
Status: Offline

Post actions:

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

__________________
Federazione
Imbroglioni
Giuoco
Calcio