Algoritmi help!
Ciao a tutti,sto preparando l'esame di algoritmi e strutture dati ma ho delle difficoltà.
Avrei bisogno di una mano per quanto riguarda gli esercizi...
ricorrenza,divide et impera e programmazione dinamica...
Il mio docente e il libro non sono stati sufficienti a farmi capire...sarò 1pò ignorante
se qualcuno mi aiuta gliene sarei grato.
ho allegato questi...mi basta anche 1...grazie.
Avrei bisogno di una mano per quanto riguarda gli esercizi...
ricorrenza,divide et impera e programmazione dinamica...
Il mio docente e il libro non sono stati sufficienti a farmi capire...sarò 1pò ignorante
se qualcuno mi aiuta gliene sarei grato.
ho allegato questi...mi basta anche 1...grazie.
Risposte
ciao,
se scrivi qua i tuoi dubbi, qualche esercizio e qualche tuo passaggio, siamo sempre lieti di dare una mano
se scrivi qua i tuoi dubbi, qualche esercizio e qualche tuo passaggio, siamo sempre lieti di dare una mano
dovrei calcolare la complessità...
Allora vediamo, non sono difficili.
Prima cosa ti mostro come si inizia la risoluzione di un esercizio di questi, prendo il secondo che hai iniziato. Lo lascerò finire a te, così da invogliarti a risolverli.
per analizzare questo codice devi capire i vari costi e le volte che vengono sviluppate le operazioni.
Questo codice è di tipo iterativo, perciò molto semplice da comprendere. Devi poi capire quale sia l'invariante dei vari cicli.
invarianti:
- ciclo for: $j$
- ciclo while: $k$
per capire il numero di volte vengono svolte le operazioni basta che guardi come venga modificato nel tempo $k$, in questo caso viene moltiplicato per $2$ successivamente, cioè esponenziale.
Questo in funzione di $n$, essendo che per avvicinarsi ad n nel $<=$ si salta valori logaritmicamente, perciò si avrà $log_2(n)$, da notare la base 2.
Per analizzare bene il codice, e facendo bene le cose si divide il codice in tabelle così:
(azz non mi vengono allineati, ma è chiaro comunque)
Sommando tutti i costi in notazione ricorsiva:
$T(n) = c_1 + c_2 + c_3(log_2(n)+1) + c_4(n*log_2(n)) + c_5((n-1)*log_2(n)) + c_6log_2(n) =$
$= c_1 + c_2 + c_3log_2(n) + c3 + c_4nlog_2(n) + c_5nlog_2(n) - c_5log_2(n) + c_6log_2(n) =$ raccogliamo
$= (c_4 + c_5)nlog_2(n) + (c_3 - c_5 + c_6)log_2(n) + (c_1 + c_2 + c_3)$
Perciò, raccogliendo le costanti:
$T(n) = anlog_2(n) + blog_2(n) + d$
adesso calcoliamo la complessità, ma questo lo lascio fare a te.
Ti ho mostrato tutti i passaggi, perchè se non hai compreso come arrivare qua non saprai mai come risolvere un banale codice.
Ho anche notato che alcuni libri lasciano per scontato questi passaggi.
A te finire. Se hai problemi non esitare a chiedere.
Gli altri esercizi spero che provi a farli e pubblichi almeno uno svolgimento di un altro esercizio, così se hai problemi gli risolviamo.
Per il primo esercizio, un attimo diverso dagli altri, è banalmente la definizione di limitazione asintotica. Basta che la applichi e estrapoli bene le costanti. Poi la dimostrazione viende da se.
Ti ricordo che per trovare $Theta()$ devi trovare $Omega()$ e $O()$, se corrispondono hai una limitazione ottima $Theta()$.
Spero sia utilie
PS: per equazioni di ricorrenza e la loro risoluzione ti consiglio di fare una ricerca nel forum nella sezione Informatica, ho già risposto domande su questo argomento, perciò esercizi svolti ce ne sono.
PS2: che libro utilizzi?
Prima cosa ti mostro come si inizia la risoluzione di un esercizio di questi, prendo il secondo che hai iniziato. Lo lascerò finire a te, così da invogliarti a risolverli.
Algoritmo(n)
k <- 1
s <- 0
while k<=n do
for j<-0 do n
s <- k*j
k <- 2*k
per analizzare questo codice devi capire i vari costi e le volte che vengono sviluppate le operazioni.
Questo codice è di tipo iterativo, perciò molto semplice da comprendere. Devi poi capire quale sia l'invariante dei vari cicli.
invarianti:
- ciclo for: $j$
- ciclo while: $k$
per capire il numero di volte vengono svolte le operazioni basta che guardi come venga modificato nel tempo $k$, in questo caso viene moltiplicato per $2$ successivamente, cioè esponenziale.
Questo in funzione di $n$, essendo che per avvicinarsi ad n nel $<=$ si salta valori logaritmicamente, perciò si avrà $log_2(n)$, da notare la base 2.
Per analizzare bene il codice, e facendo bene le cose si divide il codice in tabelle così:
Algoritmo(n) costo volte k <- 1 $c_1$ $1$ s <- 0 $c_2$ $1$ while k<=n do $c_3$ $log_2(n)+1$ for j<-0 do n $c_4$ $n*log_2(n)$ s <- k*j $c_5$ $(n-1)*log_2(n)$ k <- 2*k $c_6$ $log_2(n)$
(azz non mi vengono allineati, ma è chiaro comunque)
Sommando tutti i costi in notazione ricorsiva:
$T(n) = c_1 + c_2 + c_3(log_2(n)+1) + c_4(n*log_2(n)) + c_5((n-1)*log_2(n)) + c_6log_2(n) =$
$= c_1 + c_2 + c_3log_2(n) + c3 + c_4nlog_2(n) + c_5nlog_2(n) - c_5log_2(n) + c_6log_2(n) =$ raccogliamo
$= (c_4 + c_5)nlog_2(n) + (c_3 - c_5 + c_6)log_2(n) + (c_1 + c_2 + c_3)$
Perciò, raccogliendo le costanti:
$T(n) = anlog_2(n) + blog_2(n) + d$
adesso calcoliamo la complessità, ma questo lo lascio fare a te.
Ti ho mostrato tutti i passaggi, perchè se non hai compreso come arrivare qua non saprai mai come risolvere un banale codice.
Ho anche notato che alcuni libri lasciano per scontato questi passaggi.
A te finire. Se hai problemi non esitare a chiedere.
Gli altri esercizi spero che provi a farli e pubblichi almeno uno svolgimento di un altro esercizio, così se hai problemi gli risolviamo.
Per il primo esercizio, un attimo diverso dagli altri, è banalmente la definizione di limitazione asintotica. Basta che la applichi e estrapoli bene le costanti. Poi la dimostrazione viende da se.
Ti ricordo che per trovare $Theta()$ devi trovare $Omega()$ e $O()$, se corrispondono hai una limitazione ottima $Theta()$.
Spero sia utilie
PS: per equazioni di ricorrenza e la loro risoluzione ti consiglio di fare una ricerca nel forum nella sezione Informatica, ho già risposto domande su questo argomento, perciò esercizi svolti ce ne sono.
PS2: che libro utilizzi?
ti ringrazio per la disponibilità,cmq utilizzo introduzione agli algoritmi e strutture dati della mcgraw...
Ho capito che c'è un ciclo for e ciclo while e quali sono le invarianti...
Il mio problema è impostare l'esercizio,nel senso che,una volta capite le invarianti...come vado avanti?cosa devo guardare?Il ciclo for viene iterato n volte e il while log(n) ?sono cose che il libro da per scontato e il mio docente altrettanto...
Ho capito che c'è un ciclo for e ciclo while e quali sono le invarianti...
Il mio problema è impostare l'esercizio,nel senso che,una volta capite le invarianti...come vado avanti?cosa devo guardare?Il ciclo for viene iterato n volte e il while log(n) ?sono cose che il libro da per scontato e il mio docente altrettanto...
bhe ti ho mostrato tutti i passaggi...
rileggi meglio ciò che ti ho scritto ed applicalo ad un altro esercizio.
Una volta capito quale sia l'invariante (sai cos'è un'invariante?) guardi come cambia nel tempo. Cioè guardi che valore assume nei cicli successivi, e questo fa capire l'andamento del ciclo.
Un normale ciclo for va da 1 ad n, linearmente, cioè j assume tutti i valori e viene confrontato $n$ volte. Ma essendo che è all'interno di un altro ciclo lo moltiplichi per le volte del ciclo più esterno.
Poi sommi tutti i costi moltiplicati per le volte, e risulta l'equazione di ricorrenza, per poi trovare la complessità cercata.
PS: Se è il Cormen, il libro, è uno dei più famosi ed utilizzati, il metodo di studio degli autori del libro, è di tipo americano, cioè un po' un mattone in certe parti, anche se è il migliore.
rileggi meglio ciò che ti ho scritto ed applicalo ad un altro esercizio.
Una volta capito quale sia l'invariante (sai cos'è un'invariante?) guardi come cambia nel tempo. Cioè guardi che valore assume nei cicli successivi, e questo fa capire l'andamento del ciclo.
Un normale ciclo for va da 1 ad n, linearmente, cioè j assume tutti i valori e viene confrontato $n$ volte. Ma essendo che è all'interno di un altro ciclo lo moltiplichi per le volte del ciclo più esterno.
Poi sommi tutti i costi moltiplicati per le volte, e risulta l'equazione di ricorrenza, per poi trovare la complessità cercata.
PS: Se è il Cormen, il libro, è uno dei più famosi ed utilizzati, il metodo di studio degli autori del libro, è di tipo americano, cioè un po' un mattone in certe parti, anche se è il migliore.
ok,grazie mille,ora ci provo...cmq no,il libro non è questo...
il while va da 1 a log(n) ?
Si esatto.
se la metti così:
k varia nel tempo per moltiplicazioni successive per 2.
Perciò, esponenzialmente in base 2, e il ciclo termina quando k > n.
$2^k = n$
$log_2(2^k) = log_2(n)$ per $n>0$
$k = log_2(n)$
con $k > log_2(n)$ il ciclo termina. ok?
PS: per un buon libro di algoritmi, ti consiglio "Algoritmi e strutture dati - Seconda Edizione" di Bertossi e Montresor, completo di tutto gli argomenti di un corso base ed avanzato. Ha tutte le soluzioni degli esercizi, al contrario del Cormen. Per approfondire invece usa il Cormen, come ho fatto io.
se la metti così:
k varia nel tempo per moltiplicazioni successive per 2.
Perciò, esponenzialmente in base 2, e il ciclo termina quando k > n.
$2^k = n$
$log_2(2^k) = log_2(n)$ per $n>0$
$k = log_2(n)$
con $k > log_2(n)$ il ciclo termina. ok?
PS: per un buon libro di algoritmi, ti consiglio "Algoritmi e strutture dati - Seconda Edizione" di Bertossi e Montresor, completo di tutto gli argomenti di un corso base ed avanzato. Ha tutte le soluzioni degli esercizi, al contrario del Cormen. Per approfondire invece usa il Cormen, come ho fatto io.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo