Esercizio 7

Esercizio 7   Si consideri il seguente algoritmo Goloson.

Input: un sacchetto di cioccolatini.

1. se il sacchetto contiene al più un cioccolatino, allora mangiatelo e termina.
2. prendi un cioccolatino dal sacchetto ricevuto in input, leccalo, e mettilo in un sacchetto di cioccolatini leccati.
3. se il sacchetto ricevuto in input non è ancora vuoto, e finchè non ti assale lo scrupolo per il fatto di essere in dieta, puoi ripetere il passo 2.
4. preso dallo scrupolo (o dai rimpianti), conta i cioccolatini leccati, siano essi $x$.
5. nel tentativo di nascondere la tua debolezza, sposta $\lfloor \frac{x}{2} \rfloor$ cioccolatini dal sacchetto dei leccati al sacchetto ricevuto in input.
6. agisci da Goloson sul sacchetto dei cioccolatini leccati.
7. agisci da Goloson sul sacchetto dei cioccolatini ricevuto in input.

Sia $G(n)$ il numero massimo di degustazioni di cioccolatino (leccatine + magnate) in cui si può incorrere partendo da un sacchetto di $n$ cioccolatini. Descrivere $G(n)$ tramite una ricorrenza. Condurre analisi asintotica per $G(n)$. Riesci ad estrapolare od intuire la politica da tenere (quando conviene farsi prendere da scrupolo) qualora si voglia massimizzare il numero di degustazioni? Quale potrà essere invece il minor numero di degustazioni possibili partendo da un sacchetto di $n$ cioccolatini? Riesci ad estrapolare anche formalmente quale politica porti a questo minimo.

Chiaramente, $G(0)=0$ e $G(1)=1$ sono le nostre condizioni al contorno. Indicato con $l$ il numero di cioccolatini leccati ad una generica chiamata della procedura, otteniamo facilmente la seguente ricorrenza.

$$G(n) = G(\lceil \frac{l}{2}\rceil) +G(n-\lceil \frac{l}{2}\rceil) +l$$   $$\mbox{\hspace{1cm} con $l\geq 1$, $l\leq n$}$$$$$$

Nel caso si abbia sempre $l=1$, allora otteniamo la ricorrenza

$$G(n) = G(1) +G(n-1) +1 = G(n-1) +2$$

Che ha soluzione $G(n)= 2n-1$, vista la condizione al contorno $G(1)=1$.

Nel caso si abbia sempre $l=n$, allora otteniamo la ricorrenza

$$G(n) = G(\lceil \frac{n}{2}\rceil) +G(\lfloor \frac{l}{2}\rfloor) +n$$

Che ha soluzione $G(n)= \Theta(n\log n)$ (è la stessa ricorrenza che per il MergeSort), come si può dedurre dal Master Theorem, e verificare per induzione.

Vorremmo ora evidenziare che i due casi esaminati sono effettivamente due casi estremi (in senso asintotico, ma provate voi a vedere se sia possibile condurre un'analisi più sottile). Per fare ciò verificheremo che, comunque il nostro Goloson scelga i valori di $l$, avremo $c_1 n \leq G(n) \leq c_2 n \log_n$, per induzione.

Verifichiamo $G(n) \geq 2n-1$, per induzione:

$$G(n) = G(\lceil \frac{l}{2}\rceil) +G(n-\lceil \frac{l}{2}\rceil)... ...\geq 2\lceil \frac{l}{2}\rceil -1 +2(n-\lceil \frac{l}{2}\rceil) -1 +1 = 2n -1$$

Dove nella diseguaglianza abbiamo poggiato sull'ipotesi induttiva ma abbiamo sfruttato anche il fatto che nessuno può trattenere Goloson dal dare almeno una leccatina ($l\geq 1$).

Verifichiamo $G(n) \leq c_2 n\log_2 n$, per induzione:

$$G(n) = G(\left\lceil \frac{l}{2}\right\rceil) +G(n-\left\lceil \frac{l}{... ...lceil \frac{l}{2}\right\rceil)\log_2 (n-\left\lceil \frac{l}{2}\right\rceil) +l$$

$$\leq c_2 \left\lceil \frac{l}{2}\right\rceil\log_2 \left\lceil \frac{l}{2}\right\rceil + c_2 (n-\left\lceil \frac{l}{2}\right\rceil)\log_2 n +l$$

$$= (c_2 \left\lceil \frac{l}{2}\right\rceil\log_2 n - c_2 \left\lcei... ...eq c_2 n\log_2 n - c_2 \left\lceil \frac{l}{2}\right\rceil\log_2 \frac{3}{2} +l$$

$$\leq c_2 n\log_2 n - c_2 \frac{l}{2}\log_2 \frac{3}{2} +l$$

E l'induzione si chiude non appena $c_2\geq 2\log_\frac{3}{2} 2$.