Pagina 1 di 1
Treelogy
Inviato: 10 gen 2008, 11:15
da rand
Dimostrare che per ogni n questi due insiemi hanno la stessa cardinalità: gli alberi binari cardinali con n nodi, le stringhe di parentesi bilanciate di lunghezza 2n.
P.S. In un albero binario cardinale i nodi possono avere un solo figlio sinistro, un solo figlio destro, entrambi o nessuno dei due.
Inviato: 10 gen 2008, 20:39
da rand
E dai...
Hint:
Qual è una grammatica non ambigua per il linguaggio delle stringhe di parentesi bilanciate?
Inviato: 10 gen 2008, 21:00
da edriv
La maggior parte della gente si lamenta se qualcuno gli brucia il problema nelle prime 10 ore, tu vai controcorrente!
P.S. Propongo un'alleanza con
il mio topic
Inviato: 11 gen 2008, 01:31
da mitchan88
Le parentesi bilanciate sarebbero?
Inviato: 11 gen 2008, 13:47
da rand
Se prendi un espressione, e togli tutto tranne le parentesi ottieni una stringa di parentesi bilanciate. Comunque, detto più semanticamente, le stringhe di parentesi bilanciate sono stringhe di ( e ) tali che la differenza tra il numero di ( e di ) fino ad un qualsiasi punto della stringa è non negativa ed è 0 alla fine della stringa. Tipo (), ((())), ()(())...
Inviato: 12 gen 2008, 04:23
da Tibor Gallai
Molto carino questo fatterello, e confesso di non averlo mai notato!
Prima che scrivessi l'hint avevo trovato un algoritmo per passare da alberi a stringhe di parentesi in modo bigettivo, ma una volta letto l'hint ne è venuta una soluzione molto più pulita. Buon lavoro a tutti e grazie a rand per il bel problema!
Btw, come ne sei venuto a conoscenza? Ha qualche applicazione non fine a sé stessa?
Inviato: 12 gen 2008, 14:24
da rand
Se posti la soluzione te lo dico
Inviato: 12 gen 2008, 22:05
da Tibor Gallai
lol
Un algoritmo per trasformare alberi in stringhe è:
Codice: Seleziona tutto
void albero2stringa(albero)
scrivi("(");
if (albero.sinistro != NULL)
albero2stringa(albero.sinistro);
scrivi(")");
if (albero.destro != NULL)
albero2stringa(albero.destro);
Siccome la seguente è una grammatica non ambigua per le stringhe di parentesi bilanciate:
$ S \rightarrow \epsilon $
$ S \rightarrow (S)S $
allora la seguente funzione è ben definita (puntatori a parte
) e trasforma stringhe in alberi:
Codice: Seleziona tutto
albero stringa2albero(stringa)
if (stringa = "") return NULL;
r := crea_nodo;
match stringa with "("s1")"s2, con s1 e s2 bilanciate;
r.sinistro := stringa2albero(s1);
r.destro := stringa2albero(s2);
return r;
E' piuttosto facile convincersi che le due funzioni sono una l'inversa dell'altra, e definiscono quindi la bigezione voluta.
Inoltre, gli alberi binari così generati sono precisamente gli alberi di derivazione delle stringhe di parentesi definiti dalla grammatica (ovviamente, togliendo tutta la roba di troppo, tipo foglie con i simboli terminali attaccati, etc... insomma, ci siamo capiti).
Inviato: 13 gen 2008, 11:42
da rand
E' noto fin da tempi antichi (sicuramente più antichi di Google) che alberi binari cardinali e alberi sono in corrispondenza biunivoca, come pure alberi e parentesi bilanciate, da cui segue l'asserto. Io mi sono semplicemente accorto che si può arrivare direttamente alla stessa conclusione sfruttando la non-ambiguità di quella grammatica. Credo che ci siano tante applicazioni, ad esempio immagina di voler rappresentare un albero usando solo due bit per nodo, invece di log n richiesti da una rappresentazione a puntatori.
Inviato: 14 gen 2008, 22:11
da Tibor Gallai
Ah capito.
Puoi chiarire le corrispondenze tra alberi e alberi cardinali, e tra alberi e stringhe di parentesi bilanciate?
Grazie.
Inviato: 15 gen 2008, 15:45
da rand
La corrispondenza tra alberi a n+1 nodi e stringhe di parentesi bilanciate è ottenuta in maniera simile, visiti l'albero in profondità e per ogni nodo diverso dalla radice emetti "(" quando la sua visita inizia e ")" quando termina.
Inviato: 27 feb 2008, 21:21
da pa