Algoritmi

[Gianni911]

Ciao a tutti,vorrei dei chiarimenti sulla relazione di ricorrenza di questa g(f(x))..

//FUNZIONE 1
int f( int x) {
if (x ==0)
return 1;
else
for ( int i =1;i <= x; i ++)
cout << i+x;
return f(x -1)+4;
}
//FUNZIONE 2
int g( int y) {
if (y ==0)
return 2;
else
return f(y )+3* g(y /3);
}

Analizzo la prima relazione di ricorrenza,e dico
T f (0) = a
T f (n) = a+T f (n-1) ??-NO!!-->Risultato T f (0) = T f (n1) + bn
Per quanto riguarda la seconda ho calcolato la relazione..
T g (0) = a
T (n) = a+3*T (n-3) ,ma anche questa é errata
Risultato::
T g (0) = a
T (n) = T (n=3) + bn^2
Come dovrei comportarmi??
Grazie

[hamming_burst]

Ciao,
vediamo...
prima cosa dal codice non mi sembra che $g(x)$ abbia come parametro una funziona, perciò quello che hai scritto $g(f(x))$ non ha senso. Più corretto dire che $g(x)$ ha una chiamata ad una funzione annidata, ma come vedrai non ha seguito nell'equazione (come forma estesa) ma solo come complessità a sè.

Vediamo di analizzare il codice:

int f( int x) {
if (x ==0)
return 1;
COSTO: $c$

else
for ( int i =1;i <= x; i ++)
cout << i+x;
COSTO: $2x+1$

return f(x -1)+4;
COSTO: $b$
}

l'equazione di ricorrenza della funzione1 sarà con i costi:

$T_1(x) = {(c if x=0),(T(x-1) + 2x+1 + b \ other):}$

o più in generale:

$T_1(x) = {(\Theta(1) if x=0),(T(x-1) + O(x) \ other):}$

ipotizziamo che $T(x) in O(f(x))$.

La FUNZIONE 2 te la riscrivo in questo modo:

int g( int y) {
int t;

if (y ==0)
return 2;
else

t=f(y)
return t+3* g(y /3);
}

secondo te, l'equazione di ricorrenza e la complessità, ora qual è rispetto a quello che hai scritto?

[Gianni911]

Innanzitutto grazie per l'aiuto..
Il problema é non riesco a capire bene come raggionare per il calcolo della complessità
perchè fai $ b*other $ a cosa si riferisce other??
Altra cosa il
for ( int i =1;i <= x; i ++)
cout << i+x;
COSTO: 2x+1
Non capisco il 2x+1,la complessità non é o(n)??
Forse faccio confusione tra il calcolo della complessita é la relazione di ricorrenza,ma sono legate le due cose giusto??
Tra l'altro sulle mie slide si parla anche di R(n),ma non capisco come ricavarlo..
Grazie

[hamming_burst]

devo dirlo, hai un pochetto di confusione un po' su tutto...

"Gianni91":perchè fai $ b*other $ a cosa si riferisce other??

qua è solo notazione schematica per dire:

$Theta(1)$ quando/if $x=0$
$T(x-1) + O(n)$ altrimenti (other)
"other" è una parola come: pluto, pippo, nebbiolo, ...
non devi moltiplicarla.

Altra cosa il
for ( int i =1;i <= x; i ++)
cout << i+x;
COSTO: 2x+1
Non capisco il 2x+1,la complessità non é o(n)??

$2x+1$ è la funzione di costo, derivata dall'analisi dell'algoritmo, cioè dal numero di operazioni eseguite:

- $x+1$ assegnamenti/confronti dell'iterazione $i$
- $x$ stampe
e per essere pignoli ora che vedo:
- $x$ addizioni (i+x)
perciò sarebbe: $3x+1$ che appartiene alla classe di complessità $O(x)$ o se preferisci $O(n)$.

Forse faccio confusione tra il calcolo della complessita é la relazione di ricorrenza,ma sono legate le due cose giusto??

certo che sono legate, ci sono almeno tre diversificazioni o analisi a diversi livelli:
- analisi del costo di un algoritmo, calcoli brutalmente il numero di iterazioni, assegnamenti, ecc.. per stimare i costi "liberi" non legati a ricorsioni.
- sviluppo e generalizzazione di un algoritmo (ssse ricorsivo) in termini di equazioni di ricorrenza.
- cercare una classe di complessità che delimiti/stimi il mio algoritmo (tramite calcolo della ricorrenza, o analisi dei costi).

si potrebbe parlare anche di complessità di problemi, ma penso che lo vedrai, al momento il discorso è solo sugli algoritmi

Tra l'altro sulle mie slide si parla anche di R(n),ma non capisco come ricavarlo..

R(n), T(n), I(n), P(n) chiama la ricorrenza come vuoi, è una lettera. Di solito la notazione usata è $T(n)$, ma si vede anche $R(n)$ che sta per Recurrence(n). Non saprei se la T di T(n) abbia un equivalente esteso...

vedi se così (almeno a parole) il discorso ti è meno nebuloso; scrivi pure i tuoi dubbi, vediamo di risolverli

[Gianni911]

"hamming_burst":

[quote="Gianni91"]perchè fai $ b*other $ a cosa si riferisce other??

qua è solo notazione schematica per dire:

$Theta(1)$ quando/if $x=0$
$T(x-1) + O(n)$ altrimenti (other)
"other" è una parola come: pluto, pippo, nebbiolo, ...
non devi moltiplicarla.
[/quote]
Si certo non capisco il xchè di other,cosa altro dovremmo metterci??
Rguuardo il codice della seconda funzione
int f( int x) {
if (y ==0)
return 2;
COSTO: $c$

else
t=f(y)
COSTO: $y$

return t+3* g(y /3);
COSTO: $b$
}

l'equazione di ricorrenza della funzione1 sarà con i costi:

$T_1(x) = {(c if x=0),(T(y/3) + y + b \ other):}$

Dovrebbe essere qualcosa di simile....

[hamming_burst]

"Gianni91":
Si certo non capisco il xchè di other,cosa altro dovremmo metterci??

Bhe dipende dall'algoritmo, ci sono equazioni di ricorrenza che possono avere altre condizioni su alcuni valori, tipo:

$Theta(1)$ quando/if $x=0$
$Theta(sqrt(x))$ quando/if $1<=x<100$
$T(x/2) + b$ quando/if $100<=x<1000$
$T(x-1) + O(n)$ altrimenti (other)

else
t=f(y)
COSTO: $y$

perchè $y$? non vedo $y$ operazioni sequenziali.
Pensa, cosa è $f(y)$?

La ricorrenza è impostata correttamente, manca di scrivere correttamente il costo sopra.

[Gianni911]

"hamming_burst":
t=f(y)
COSTO: y
perchè y? non vedo y operazioni sequenziali.
Pensa, cosa è f(y)?

credevo valesse come nel caso originale,ma a quanto ho capito si tratta solo di un assegnamento quindi:
COSTO: $b$


$T_1(x) = {(c if x=0),(T(y/3) +2 b \ other):}$
Scusami,ma adesso che vedo bene,xchè x+1 assegnamenti/confronti dell'iterazione i..
non dovrebbe essere solo x??(nell'analisi della prima funzione)
Nel caso in cui fosse stato for(int i=0;i Grazie

[hamming_burst]

"Gianni91":[quote="hamming_burst"]
t=f(y)
COSTO: y
perchè y? non vedo y operazioni sequenziali.
Pensa, cosa è f(y)?

credevo valesse come nel caso originale,ma a quanto ho capito si tratta solo di un assegnamento quindi:
COSTO: $b$


$T_1(x) = {(c if x=0),(T(y/3) +2 b \ other):}$[/quote]
non ci siamo.
hai ragione per l'assegnamento. Ma qua si parla di una chiamata ad una funzione. Il costo del calcolo della funzione devi aggiungerlo è compreso nell'algoritmo.
perciò devi riportare il valore della complessità di $f(y)$ che hai calcolato tramite la sua equazione di ricorrenza precedentemente, cha sarà tipo $O(t(y))$
perciò:


$T_1(x) = {(c if x=0),(T(y/3) + O(t(y)) + h \ other):}$

Scusami,ma adesso che vedo bene,xchè x+1 assegnamenti/confronti dell'iterazione i..
non dovrebbe essere solo x??(nell'analisi della prima funzione)

hai ragione, è nel ciclo while si fanno x+1 incrementi o confronti.

Nel caso in cui fosse stato for(int i=0;i
esatto

PS: se ti servono esercizi su come calcolare i costi diretti di un algoritmo prova a vedere questi, altro materiale è qui (ci sono anche le soluzioni a quegli esercizi.

[Gianni911]

"hamming_burst":
Ma qua si parla di una chiamata ad una funzione. Il costo del calcolo della funzione devi aggiungerlo è compreso nell'algoritmo.
perciò devi riportare il valore della complessità di $f(y)$ che hai calcolato tramite la sua equazione di ricorrenza precedentemente, cha sarà tipo $O(t(y))$
perciò:

$T_1(x) = {(c if x=0),(T(y/3) + O(t(y)) + h \ other):}$

Bene ci avevo preso prima all'ora ma non lo avevo scritto come dovevo

PS: se ti servono esercizi su come calcolare i costi diretti di un algoritmo prova a vedere questi, altro materiale è qui (ci sono anche le soluzioni a quegli esercizi.

Ottimo grazie mille

[Gianni911]

Scusami ,ma continua a non tornarmi xchè ci sono due soluzioni nei miei esercizi
Prendendo in considerazione il codice..

int g(int x){
 if(x<=0) return 1;
 int a=0;          ----->b
 for(int i=0;i<= x*x;i++) -->n^2
  a+=i;           -->n^2
return a+ g(x/2);---->b
}

Per il T(n)
La mia:
$T_1(x) = {(c if x=0),(T(n/2) +bn^2 ):}$ ----->OK
Riguardo R(n)
il risultato dovrebbe essere
$R_1(x) = {(d if x=0),(R(n/2) +cn^4 ):}$
come lo ricavo??Dovrebbe essere la complessita del risultato della mia funzione..

[hamming_burst]

Per la ricorrenza T(n) ok, ora devi calcolarne la complessità


Scusa da dove esce R(n)? cosa è per te? perchè secondo me gli dai un significato particolare....

[Gianni911]

"hamming_burst":Per la ricorrenza T(n) ok, ora devi calcolarne la complessità

$ T(n)=O(n^2) $

"hamming_burst":
Scusa da dove esce R(n)? cosa è per te? perchè secondo me gli dai un significato particolare....

Guarda nei miei esercizi c'è un R(n),credo sia la conplessità del risultato della funzione,ma non sono sicuro di come calcolaro.
Ti linko,un compito,per farti capire di cosa parlo
http://info.iet.unipi.it/~fondii/Esami/Materiale/Algoritmi-2011-02-25.pdf(Esercizio 3]
Spero si risolva questo problema

[hamming_burst]

Per la complessità, esatto è $O(n^2)$. Che tecnica hai utilizzato per calcolarla?

Da quello che ho capito sembra che R(n) dia tipo una stima sull'output. T(n) da la classica complessità dell'algoritmo.
Una cosa che non avevo mai visto fare.
Mi sapresti dire esattamente dalle tue dispense/slide dove viene spiegata questa cosa? che quasi sicuro è quello che ho scritto, ma vorrei sapere come la introduce il tuo docente.


Ho dato un'occhiata a anche alle dispense linkate, il calcolo lo rende ancora più complesso secondo me; perchè il docente introduce una grammatica ed una semantica (denotazionale), così da interpretare un programma. Molto interessante, ma di nessun scopo in un corso i Algoritmica+DB.
Mah si inventano di tutto per raggruppare argomenti e confondere gli studenti.

[Gianni911]

"hamming_burst":Per la complessità, esatto è $O(n^2)$. Che tecnica hai utilizzato per calcolarla?

Usando il metodo Divide et Impera,essendo
$ aO(n^k)--->O(n^2) $

"hamming_burst":
Da quello che ho capito sembra che R(n) dia tipo una stima sull'output. T(n) da la classica complessità dell'algoritmo.
Una cosa che non avevo mai visto fare.

Quello che avevo pensato anch'io..

"hamming_burst":
Mi sapresti dire esattamente dalle tue dispense/slide dove viene spiegata questa cosa? che quasi sicuro è quello che ho scritto, ma vorrei sapere come la introduce il tuo docente.

Guarda é proprio questo il problema,ho sfogliato tutto quello che ho ma di quella notazione non c'è traccia,sembra strano lo so,ma adesso ricontrollo,cmq a lezione non l'ho mai vista,mah...