Teoria Della Computazione(Metodo della Diagonalizzazione)
Salve ragazzi, sono un nuovo utente del forum, a breve ho l' esame di ETC(informatica terzo anno) e tra gli esercizi che la professoressa ci ha proposto in classe , c è ne uno che non riesco a risolvere.L' esercizio recita :
Mostrare che l’insieme di tutte le stringhe di lunghezza dispari in {a, b, c}∗ risulta numerabile.
L' esercizio dovrebbe essere svolto con il metodo della diagonalizzazione (diagonale di Cantor), il problema è che non riesco a trovare argomenti simili su internet. Se potete aiutarmi ve ne sono grato, grazie.
Mostrare che l’insieme di tutte le stringhe di lunghezza dispari in {a, b, c}∗ risulta numerabile.
L' esercizio dovrebbe essere svolto con il metodo della diagonalizzazione (diagonale di Cantor), il problema è che non riesco a trovare argomenti simili su internet. Se potete aiutarmi ve ne sono grato, grazie.
Risposte
Non ho capito una cosa, l'esercizio ti impone di risolverlo con il metodo diagonale di Cantor o sei tu che vuoi usarlo?
Ti faccio questa domanda perché è una cosa un po' strana, in genere il metodo diagonale di Cantor si usa per dimostrare che qualcosa NON è numerabile, e poi l'esercizio si può senz'altro fare con diversi metodi.
Ti faccio questa domanda perché è una cosa un po' strana, in genere il metodo diagonale di Cantor si usa per dimostrare che qualcosa NON è numerabile, e poi l'esercizio si può senz'altro fare con diversi metodi.
L' esercizio non mi impone nulla, ero io che pensavo si risolvesse con la diagonalizzazione di Cantor. Qual è il metodo ottimale per risolvere questo esercizio?
Fatti queste domande: quante sono le stringhe di lunghezza 1? quante sono le stringhe di lunghezza 3? quante sono le stringhe di lunghezza 5? quante sono le stringhe di lunghezza 7?................
L' insieme di queste stringhe è di lunghezza finita. Magari parto da questa osservazione e provo a mettere le stringhe di lunghezza dispari in relazione binaria con l' insieme dei numeri Naturali,dimostrando cosi che l' insieme risulta finito?
Ti è noto il fatto che unione numerabile di insiemi numerabili è numerabile?
Guarda sul libro quest argomento non è spiegato benissimo, anzi tutt' altro.In piu su internet ho trovato veramente poco sull' argomento. Comunque forse ho capito.Posso mettere in relazione biunivoca l' insieme dei numeri dispari con l' insieme dei numeri naturali , ed utilizzando la definizione di cardinalità di Cantor dimostrare che l' insieme dei numeri dispari è numerabile, poiche è un sottoinsieme dei numeri naturali con la stessa cardinalità. Quello che non capisco è questo , io in questo momento vado a mettere in relazione l' intero sottoinsieme dei numeri dispari , con l' insieme dei numeri naturali; invece l' esercizio mi chiede di mostrare che l’insieme di tutte le stringhe di lunghezza dispari in {a, b, c}∗ risulta numerabile. Quindi mi manca qualche passaggio? O sto sbagliando qualcosa?
In realtà mettere in biezione l'insieme dei numeri dispari con tutti i naturali non ti serve a molto, piuttosto devi mettere in biezione l'insieme delle stringhe di lunghezza dispari con $NN$, puoi notare che la quantità di stringhe di lunghezza n è $3^n$, quindi la biezione la puoi fare così: con i primi $3^1=3$ numeri conti le stringhe di lunghezza 1 (nell'ordine che preferisci, diciamo quello alfabetico), poi con le successive $3^3=27$ conti quelle di lunghezza 3, e vai avanti così fino all'infinito.
Ho capito, grazie mille.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo