Equazione di ricorrenza
Ciao a tutti 
Ho provato a proporre questo esercizio nella sezione "analisi matematica" ma con scarso risultato...nessuno mi ha risposto!!
Provo qui, confidando in una mano da parte di chi frequenta la mia stessa facoltà
Non è che mi potreste dare delle dritte su questo esercizio? Come si imposta?
"Scrivere un'equazione di ricorrenza per il numero di stringhe binarie di lunghezza n che contengono almeno due zeri consecutivi".
Io sono in grado di risolvere un'equazione di ricorrenza...ma non so ricavarla (ne in questo caso, ne in generale)
Me lo potreste gentilmente spiegare? Mi fareste un grosso favore.
Grazie
Ho provato a proporre questo esercizio nella sezione "analisi matematica" ma con scarso risultato...nessuno mi ha risposto!!
Provo qui, confidando in una mano da parte di chi frequenta la mia stessa facoltà
Non è che mi potreste dare delle dritte su questo esercizio? Come si imposta?
"Scrivere un'equazione di ricorrenza per il numero di stringhe binarie di lunghezza n che contengono almeno due zeri consecutivi".
Io sono in grado di risolvere un'equazione di ricorrenza...ma non so ricavarla (ne in questo caso, ne in generale)
Me lo potreste gentilmente spiegare? Mi fareste un grosso favore.
Grazie
Risposte
Credo sia più facile calcolare il numero di stringhe binarie che non contengono zeri consecutivi. E da questo numero si può poi calcolare il numero di stringhe in cui ci siano almeno due zeri consecutivi abbastanza facilmente. Ignorando il fatto di dover poi scrivere una equazione di ricorrenza, se dovessi calcolare ad esempio il numero di stringhe binarie di lunghezza n (per esempio 7) con quella proprietà, che cosa faresti?
Ciao Apatriarca,
inizio subito a dirti che non sono proprio in grado di fare quello che tu mi chiedi gli appunti pressi a lezione non aiutano, e io devo cercare di capire come funzionano questi esercizi prima del prossimo esame 
Andiamo per punti:
Io non saprei fare neanche questa parte, il che ti fa capire che sono un attimo perso
Ci sono proprietà o metodi per ricavare ciò?
Forse è meglio prima sistemare questo punto...
Ti ringrazio per il tuo eventuale aiuto
inizio subito a dirti che non sono proprio in grado di fare quello che tu mi chiedi
gli appunti pressi a lezione non aiutano, e io devo cercare di capire come funzionano questi esercizi prima del prossimo esame Andiamo per punti:
"apatriarca":
se dovessi calcolare ad esempio il numero di stringhe binarie di lunghezza n (per esempio 7) con quella proprietà, che cosa faresti?
Io non saprei fare neanche questa parte, il che ti fa capire che sono un attimo perso
Ci sono proprietà o metodi per ricavare ciò?
Forse è meglio prima sistemare questo punto...
Ti ringrazio per il tuo eventuale aiuto
Prima di tutto, come ti ho scritto in precedenza, è più facile in questo caso calcolare il complemento di questo insieme. Per trovare infatti il numero di elementi di \(A \subseteq X\) puoi calcolare il numero di elementi di \(B = X - A\) e poi sottrarre tale numero al numero di elementi dell'insieme \(X\). In questo caso abbiamo che il numero di stringhe binarie di lunghezza \(n\) è \(2^n\) e quindi, se calcoliamo il valore \(T(n)\) delle stringhe binarie di lunghezza \(n\) che non contengono \(0\) consecutivi, possiamo calcolare il numero \(S(n)\) di stringhe binarie di lunghezza \(n\) con almeno due \(0\) consecutivi con la formula \( S(n) = 2^n - T(n). \) L'idea è quindi quella di costruire una equazione di ricorrenza per \(T(n)\) e usarla per \(S(n)\).
Vediamo ora di studiare come sono fatte le stringhe che non hanno zeri consecutivi. Possiamo ad esempio osservare che queste stringhe possono iniziare con un zero o con un uno, ma quando iniziano con uno zero il secondo bit deve essere un uno. Vediamo che il resto della stringa ha la proprietà di non avere zeri consecutivi per cui possiamo fare la ricorsione. La formula è quindi
\[ T(0) = 0,\quad T(1) = 2, \quad T(n) = T(n-1) + T(n-2). \]
Nota che \(T(n-1)\) rappresenta il caso in cui la stringa inizia con \(1\), mentre T(n-2) rappresenta il caso in cui la stringa inizia con \(01\). A questo punto puoi calcolarti \(S(n)\) a partire da questa ricorrenza
\[
\begin{align*}
S(n) &= 2^n - T(n) = 2^n - T(n-1) - T(n-2) = 2^n - ( 2^{n-1} - S(n-1) ) - (2^{n-2} - S(n-2)) \\
&= S(n-1) + S(n-2) + 2^n - 2^{n-1} - 2^{n-2}
\end{align*}
. \]
Esiste forse un modo per calcolarsela direttamente ma credo che questo metodo sia il più comodo. Ovviamente hai che \(S(0) = 0\) e \(S(1) = 0\).
Vediamo ora di studiare come sono fatte le stringhe che non hanno zeri consecutivi. Possiamo ad esempio osservare che queste stringhe possono iniziare con un zero o con un uno, ma quando iniziano con uno zero il secondo bit deve essere un uno. Vediamo che il resto della stringa ha la proprietà di non avere zeri consecutivi per cui possiamo fare la ricorsione. La formula è quindi
\[ T(0) = 0,\quad T(1) = 2, \quad T(n) = T(n-1) + T(n-2). \]
Nota che \(T(n-1)\) rappresenta il caso in cui la stringa inizia con \(1\), mentre T(n-2) rappresenta il caso in cui la stringa inizia con \(01\). A questo punto puoi calcolarti \(S(n)\) a partire da questa ricorrenza
\[
\begin{align*}
S(n) &= 2^n - T(n) = 2^n - T(n-1) - T(n-2) = 2^n - ( 2^{n-1} - S(n-1) ) - (2^{n-2} - S(n-2)) \\
&= S(n-1) + S(n-2) + 2^n - 2^{n-1} - 2^{n-2}
\end{align*}
. \]
Esiste forse un modo per calcolarsela direttamente ma credo che questo metodo sia il più comodo. Ovviamente hai che \(S(0) = 0\) e \(S(1) = 0\).
Grazie mille per la soluzione, almeno ho un "modello" da seguire per gli esercizi
Non posso fare a meno di chiederti alcune cose cosi da avere tutto più chiaro...
In base a cosa scegli $T(0) = 0$ e $T(1) = 2$?
E poi ti chiedo la stessa cosa per quanto riguarda $S(0) = 0$ e $S(1) = 0$ non capisco perché abbiano esattamente questi valori.
Detto ciò, volevo fare il punto sulle formule da te citate...sono le uniche utili o c'è altro che è bene conoscere per svolgere esercizi di questo tipo?
Non posso fare a meno di chiederti alcune cose cosi da avere tutto più chiaro...
In base a cosa scegli $T(0) = 0$ e $T(1) = 2$?
"apatriarca":
\[ T(0) = 0,\quad T(1) = 2, \quad T(n) = T(n-1) + T(n-2). \]
E poi ti chiedo la stessa cosa per quanto riguarda $S(0) = 0$ e $S(1) = 0$ non capisco perché abbiano esattamente questi valori.
Detto ciò, volevo fare il punto sulle formule da te citate...sono le uniche utili o c'è altro che è bene conoscere per svolgere esercizi di questo tipo?
I casi base vanno considerati a parte, ma normalmente è sufficiente fare una enumerazione completa dei casi. Se la stringa ha lunghezza \(1,\) allora non ci possono essere due zeri ripetuti e quindi le due stringhe possibili vanno contate in T. Nel caso di lunghezza \(0\) ho invece sbagliato a scrivere. C'è infatti una sola stringa (quella vuota) e questa non ha ovviamente zeri ripetuti. Per cui si deve avere \(T(0) = 1.\) In effetti \(T(2) = 3\) (\(01, 10, 11\)) e non \(2\) come verrebbe nel caso fosse \(T(0) = 0\). Discorso simile vale per \(S\). Perché ci siano due zeri consecutivi ci vanno almeno due bit, per qui \(S(0) = S(1) = 0\). Alternativamente puoi calcolarlo a partire da \(T\).
EDIT: Ovviamente puoi anche scrivere la formula per \(S\) come
\[ S(n) = S(n-1) + S(n-2) - (4 - 2 - 1)\,2^{n-2} = S(n-1) + S(n-2) - 2^{n-2}. \]
EDIT: Ovviamente puoi anche scrivere la formula per \(S\) come
\[ S(n) = S(n-1) + S(n-2) - (4 - 2 - 1)\,2^{n-2} = S(n-1) + S(n-2) - 2^{n-2}. \]
Grazie, ora provo a svolgere qualche esercizio e vedo cosa ne salta fuori. Purtroppo questi esercizi mi sembrano molto complessi, mi sa che mi ci vorrà un po' di tempo per apprendere il "metodo" e arrivare correttamente al risultato XD
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo