Treelogy

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Treelogy

Messaggio 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.
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

E dai...

Hint:

Qual è una grammatica non ambigua per il linguaggio delle stringhe di parentesi bilanciate?
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

La maggior parte della gente si lamenta se qualcuno gli brucia il problema nelle prime 10 ore, tu vai controcorrente! :D

P.S. Propongo un'alleanza con il mio topic
Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da mitchan88 »

Le parentesi bilanciate sarebbero? :?:
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio 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 (), ((())), ()(())...
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio 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? :D
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Se posti la soluzione te lo dico
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

lol :D

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 :roll: ) 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).
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio 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.
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Ah capito.
Puoi chiarire le corrispondenze tra alberi e alberi cardinali, e tra alberi e stringhe di parentesi bilanciate?
Grazie.
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio 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.
Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

Messaggio da pa »

paolo
Rispondi