Newsgroup: it.scienza.informatica
Titolo: Algoritmo hashing

Salve,
che conseguenze si avrebbero se si riuscisse a scoprire un algortimo
di hashing (polinomiale deterministico) che, preso in input un qualsiasi
'oggetto' definito da n-uple di numeri naturali, restituica un hashcode
senza mai generare collisioni? 


Se lo spazio degli ingressi è più grande di quello delle uscite tale
algoritmo non può esistere.

 ha scritto nel messaggio 
news:87ddc081-cd6d-4b4d...@l28g2000prd.googlegroups.com...

Mi sono dimenticato di dire che non c'è limite di spazio ;)
In altre parole, che conseguenze ci sarebbero se si riuscisse a mappare
iniettivamente n-uple su N 

 wrote:

 iniettivamente n-uple su N
parli della goedelizzazione?
Mauro

 ha scritto nel messaggio
news:250cc836-022f-4eba...@p25g2000hsf.googlegroups.com...

Ho dimenticato di scrivere che l'algoritmo deve essere polinomiale
deterministico

 si chiama scomposizione in fattori primi...
Che sia polinomiale determistica ;-) 

 ha scritto nel messaggio 
news:250cc836-022f-4eba...@p25g2000hsf.googlegroups.com...



 deterministico
come vedi ne qui ne su i.s.matematica nessuno è riuscito a capire la
tua domanda, forse perchè hai sviato tutti con quella parola "hashing"
che non c'entra nulla...
se ti interessa prova a spiegarti meglio e a dirci da dove sorge
questa domanda
Mauro

 ha scritto nel messaggio news:c2fb6284->

Semplice:
1. Scegli una stringa di bit come separatore.
2. Considera gli elementi della tupla come stringhe di bit, ad ogni
occorrenza del separatore all'interno di queste stringhe duplicalo.
3. Concatena le stringhe ottenute al punto precedente intervallandole
al separatore. La stringa che ottieni è il tuo nomero di uscita
scritto in binario.

Guido ha scritto:

ti posso rispondere dicendoti di documentanti su FPT-Technique, ho 
appena sostenuto l'esame qui in norvegia e in particolare sulla tecnica 
color coding cerca direttamente da google e vedrai che la tua 
affermazione viene dimostrata che non può esistere.
per ulteriori informazioni contattami pure

 scritto in binario.
Tale algoritmo non è polinomiale deterministico però. 


Come no?

 Come no?
Il numero di bit è esponenziale in funzione della dimensione del
numero presente nell' n-upla. Fai un esempio del tuo algoritmo 

 Fai un esempio del tuo algoritmo
separatore: "100"
n-upla: (12, 7, 1024) = ("1100", "111", "10000000000")
Risultato: concat("1100100", "100", "111", "100", "10010000000000") "110010010011110010010000000000" = 844047360

 "110010010011110010010000000000" = 844047360
E la dimostrazione che questa funzione č iniettiva? 

 E la dimostrazione che questa funzione č iniettiva?
Chiaramente non č iniettiva, controesempio:
(0,1000)=01001001000
(0100,0)=01001001000
Questo controesempio č valido per qualsiasi separatore X si scelga;
quindi č sbagliato l'algoritmo.

 "Axel" <a...@axel.axe> ha scritto nel messaggio news:LSb2k.93341

Hai ragione.
Errore mio. :)

 "Axel" <a...@axel.axe> ha scritto nel messaggio news:LSb2k.93341

Ci riprovo:
Siano s1 ed s2 due stringhe non vuote tali che non siano l'una un
prefisso dell'altra.
1. Sostituisci negli elementi della n-upla s1 con s1s1 e s2 con s1s2.
2. Concatena le stringhe ottenute al passo precedente intervallandole
con s2.
In questo modo ogni s2 introdotto nel risultato come separatore č
sepre preceduto da una sequenza pari (eventualmente nulla) di s1,
mentre ciascun s2 che si trovava gią nella n-upla č sempre preceduto
da una sequenza dispari di s1 nel risultato, quindi č possibile
ricostruire gli elementi della n-upla a partire dal risultato.

 ricostruire gli elementi della n-upla a partire dal risultato.
Si ma così l'algoritmo non è definito, nel senso che non è definito
un unico separatore a priori. Anzi questo ragionamento dimostra che non è
possibile usare la tecnica delle doppie ripetizioni per mappare 
iniettivamente
n-uple di naturali su N con un unico separatore, più precisamente
servirebbero infiniti separatori S2 (diversi tra loro) per aggirare ogni 
controesempio possibile.