Di testi non ce ne sono in giro, perché non ti fa usare fogli bianchi durante i test...

Però, se ti serve qualche consiglio... sono qui! :wink:

ti ringrazio per la disponibilità:
ne approfitto per esporti una cosa che penso di aver capito ma forse non è così:

al primo capitolo cè questo esercizio (algoritmo di "Tribonacci": http://gauguin.info.uniroma2.it/~italiano/Teaching/Algoritmi/Esercizi/soluzione1.pdf
-per stabilire la relazione di ricorrenza non ho problemi
-un pò di confusione nello stimare T(n) per n grande:

-capisco che diamo una limitazione inferiore perkè scegliamo 3T(n-3)+c1
-ma come fa 3T(n-3)+c1 ad essere maggiore di 3^2T(n-6)?
-(nello svolgimento dell'esercizio) ad ogni passo in cui aumenta la potenza di 3 e ottengo multipli di tre tra le () e si aggiungono altre costanti, cosa succede? sono da intendersi come passi ricorsivi??

perdona la mia ignoranza, ma è una cosa su cuo ho sbattuto la testa e che ancora faccio difficoltà a capire...

ti ringrazio
ciao ciao

Quello che lui fa, è procedere per sostituzione di passo in passo della T(n) (quindi, ricorsivamente) finché non giunge al risultato che hai visto
per il secondo passo verrebbe una cosa tipo:

3(3T[(n-3)-3] + c[size=2]1[/size]) +c[size=2]1[/size] = (3^2)T(n-6)+ 3c[size=2]1[/size] + c[size=2]1[/size]

e così via....

Alt dato che sei stato gentilissimo e di grande aiuto fino a questo punto potresti fare un altro grande "sforzo?":
negli esercizi del secondo capitolo ho una cosa del genere:
3T(n/3)+n
che applicando il teorema Master è facile vedere che esce T(n)=Teta(n log n)

ma io per vedere se ho capito applico il metodo dell'iterazione.

se applico il metodo dell'iterazione dovrebbe uscire lo stesso risultato no?!

ecco la mia iterazione: (se vuoi vedi se ci sono errori oppure dimmi come fare pls)
3T(n/3) srotolandola ottengo 3^i T(n/3^i):
- n/3^i=1 per i=log in base 3 di n
-3^i dove i=log in base 3 di n da come risulato n
-alla fine quindi mettendo insieme i pezzi verrebbe n*1=n

e questa parte è fatta

ora srotolando n mi viene una serie che risolvo con la geometrica arrivando ad un risultato di n^2


in finale finale avrei una cosa così:
n+n^2

e quindi io direi
T(n)=teta di n^2....che è sbagliato....

se ti va help me
altrimenti grazie lo stesso!!!
ciao ciao

Quel tipo di errore (cioè n^2) con quel metodo viene a causa delle approssimazioni, perché certe costanti le trascuri e via dicendo...
C'era un esempio chiarificatore sul libro di testo che usava prima di scriversene uno SUO.... ma ora non ce l'ho sotto mano...

Come dire, magari ti sembrerà un consiglio un po' "approssimativo", ma quando hai un esercizio, facilmente risolvibile con il Teorema Master, applica direttamente quello, perché lui l'ha modellato su quell' "algoritmo di risoluzione" ed usando lo "srotolamento" potresti complicarti MOLTISSIMO la vita....