O-GRANDE. Fondamenti di programmazione.
Mi sapreste dire come si svolge questo esercizio?E' importante, sto utilizzando 3 libri e vari appunti ma non ho molto tempo per capire a volto tutto quanto. Mi fareste un grande favore, grazie. 
Siano f(n) ed g(n) due funzioni. Dimostrare le seguenti affermazioni:
a) 2 f(n) + 3g(n) è O(f(n) + g(n))
b) f(n) + g(n) è O(max{f(n), g(n)})
Siano f(n) ed g(n) due funzioni. Dimostrare le seguenti affermazioni:
a) 2 f(n) + 3g(n) è O(f(n) + g(n))
b) f(n) + g(n) è O(max{f(n), g(n)})
Risposte
Ciao,
è semplicemente l'applicazione della teoria, utilizzi la proprietà della somma, e la definizione di O-Grande. Se vuoi fare le cose bene dimostri per induzione, nulla di complicato.
Da notare \(a \in \text{O}(b) \vee b \in \text{O}(a)\)
Se hai dubbi chiedi pure.
PS: se hai dubbi teorici su queste notazioni e proprietà gurda questi appunti scritti da un utente del forum, gugo82.
è semplicemente l'applicazione della teoria, utilizzi la proprietà della somma, e la definizione di O-Grande. Se vuoi fare le cose bene dimostri per induzione, nulla di complicato.
Da notare \(a \in \text{O}(b) \vee b \in \text{O}(a)\)
Se hai dubbi chiedi pure.
PS: se hai dubbi teorici su queste notazioni e proprietà gurda questi appunti scritti da un utente del forum, gugo82.
Mi servirebbe sapere direttamente la soluzione. Non ho molto tempo per capire tutto e quindi cercherò di andare a intuizione, purtroppo l'ho saputo solo da poco che dovrò rifare l'esame, un esame fatto tanti mesi fa. O.o
Non ho molto tempo per capire tutto e quindi cercherò di andare a intuizione, purtroppo l'ho saputo solo da poco che dovrò rifare l'esame, un esame fatto tanti mesi fa. O.o
Se ti va, spiegami passo passo il procedimento, così avrò subito chiaro il procedimento. Sto nel panico. O.o
ciao,
quello che chiedi di dimostrare è esattamente la proprietà della somma, perciò è descritto in qualunque libro decente, ti linko il primo link che google elenca:
http://www.adt.unipd.it/corsi/Bianco/Complessita.pdf
vedi pag.10 "proprietà della somma"
se poi il tuo dubbio è come risolvere esercizi di questo tipo con "equazioni di ricorrenza" o a "termini generali" è un altro discorso...
quello che chiedi di dimostrare è esattamente la proprietà della somma, perciò è descritto in qualunque libro decente, ti linko il primo link che google elenca:
http://www.adt.unipd.it/corsi/Bianco/Complessita.pdf
vedi pag.10 "proprietà della somma"
se poi il tuo dubbio è come risolvere esercizi di questo tipo con "equazioni di ricorrenza" o a "termini generali" è un altro discorso...
E' lo stesso libro che ho trovato io. 
Cmq si, ho problemi con le relazioni di ricorrenza, in pratica vorrei avere le idee più chiare...vorrei capire di preciso come funziona. Non riesco a fare tutti gli esercizi.
Vedi un po se mi puoi spiegare passo passo, tutti i procedimenti che fai con questo esercizio.
BASE T(1) = 0
PASSO Induttivo T(n) = 4T(n/2) + n/2 per n potenza di 2 e n>1
Si vuole determinare i valori iniziali di T(n):
a) Determinare i valori iniziali di T(1) = , T(2) = , T(4) =
b) Espandere la regola induttiva ed esprimere T(n) in termini di T(n/2^2)
c) Esprimere T(n) in termini di T(n/2^3)
d) Determinare la regola generale per esprimere T(n) in termini di T(n/2^i)
e) Per quale valore di i si può eliminare T(n/2^i) dall'espressione?
f) Utilizzare la risposta ai punti d) ed e) per esprimere T(n) in termini solo di n (cioè non in fuzione di altri valori della funzione T)
DIMMI INVECE SE HO FATTO BENE QUESTO ESERCIZIO.
BASE T(0) = 0
INDUZIONE T(n) = 5T(n-1) +3, per n >1
Si vuole determinare il valore esatto di T(n) per ogni n>1
a) Determinare i valori iniziali di T(n):
T(1) = 3, T(2) = 18, T(3) = 93
b) Espandere la regola induttiva ed esprimere T(n) in termini di T(n-2)
T(n) = 5(5T(n-2) +3)+3
c) Esprimere T(n) in termini di T(n-3)
T(n) = 5(5(5T(n-3)+3)+3
d) Determinare la regola generale per esprimere T(n) in termini di T(n-i)
T(n) = 5^i T(n-i) + [somma per j da i a n(3*5^j)]
e) Per quale valore di i si può eliminare T(n-i) dall'espressione?
i= n-1
f) Utilizzare la risposta ai punti d) ed e) per esprimere T(n) in termini solo di n (quindi non in funzione di altri valori della funzione T)
T(n) = 3*5^n + [somma per j da 1 a n (3*5^j)]
Cmq si, ho problemi con le relazioni di ricorrenza, in pratica vorrei avere le idee più chiare...vorrei capire di preciso come funziona. Non riesco a fare tutti gli esercizi.
Vedi un po se mi puoi spiegare passo passo, tutti i procedimenti che fai con questo esercizio.
BASE T(1) = 0
PASSO Induttivo T(n) = 4T(n/2) + n/2 per n potenza di 2 e n>1
Si vuole determinare i valori iniziali di T(n):
a) Determinare i valori iniziali di T(1) = , T(2) = , T(4) =
b) Espandere la regola induttiva ed esprimere T(n) in termini di T(n/2^2)
c) Esprimere T(n) in termini di T(n/2^3)
d) Determinare la regola generale per esprimere T(n) in termini di T(n/2^i)
e) Per quale valore di i si può eliminare T(n/2^i) dall'espressione?
f) Utilizzare la risposta ai punti d) ed e) per esprimere T(n) in termini solo di n (cioè non in fuzione di altri valori della funzione T)
DIMMI INVECE SE HO FATTO BENE QUESTO ESERCIZIO.
BASE T(0) = 0
INDUZIONE T(n) = 5T(n-1) +3, per n >1
Si vuole determinare il valore esatto di T(n) per ogni n>1
a) Determinare i valori iniziali di T(n):
T(1) = 3, T(2) = 18, T(3) = 93
b) Espandere la regola induttiva ed esprimere T(n) in termini di T(n-2)
T(n) = 5(5T(n-2) +3)+3
c) Esprimere T(n) in termini di T(n-3)
T(n) = 5(5(5T(n-3)+3)+3
d) Determinare la regola generale per esprimere T(n) in termini di T(n-i)
T(n) = 5^i T(n-i) + [somma per j da i a n(3*5^j)]
e) Per quale valore di i si può eliminare T(n-i) dall'espressione?
i= n-1
f) Utilizzare la risposta ai punti d) ed e) per esprimere T(n) in termini solo di n (quindi non in funzione di altri valori della funzione T)
T(n) = 3*5^n + [somma per j da 1 a n (3*5^j)]
Ma in che corso ti hanno insegnato a svolgere le equazioni di ricorrenza in questo strano modo?
Il primo esercizio utilizza il "metodo dell'albero"
il secondo...quello che fai si chiama "metodo dell'iterazione" e non si svolge così. Quei punti alfabetici sono lo svolgiemento di tale metodo, come si può dividerlo così...
Levami una curiosità, questo "Fondamenti di programmazione" è un corso di Ingegneria dove comprimono nozioni di un Cdl di Informatica in soli 12 crediti?
Che libri utilizzi?
PS: se vuoi materiale decente su questi argomenti che sono di algoritmica:
- esercizi e teoria: https://www.matematicamente.it/forum/pos ... tml#479901
- esercizi svolti sulle equazioni di ricorrenza, utilizza la funzione "cerca" nella sezione Informatica; ne ho risolte parecchie in passato con tutto lo svolgimento, ma se rispondi alle domande che ti ho scritto sopra, penso tu non sappia svolgerle in quel modo...
Il primo esercizio utilizza il "metodo dell'albero"
il secondo...quello che fai si chiama "metodo dell'iterazione" e non si svolge così. Quei punti alfabetici sono lo svolgiemento di tale metodo, come si può dividerlo così...
Levami una curiosità, questo "Fondamenti di programmazione" è un corso di Ingegneria dove comprimono nozioni di un Cdl di Informatica in soli 12 crediti?
Che libri utilizzi?
PS: se vuoi materiale decente su questi argomenti che sono di algoritmica:
- esercizi e teoria: https://www.matematicamente.it/forum/pos ... tml#479901
- esercizi svolti sulle equazioni di ricorrenza, utilizza la funzione "cerca" nella sezione Informatica; ne ho risolte parecchie in passato con tutto lo svolgimento, ma se rispondi alle domande che ti ho scritto sopra, penso tu non sappia svolgerle in quel modo...
Eh... ma sopratutto dovresti sapere che la prof. non riesce nemmeno a farsi capire, ha un modo tutto suo. Inoltre c'è stato un corso di trasformazone, l'hanno eliminato questo esame ma io lo dovrò fare, il discorso vale per i nuovi iscritti.
Cmq assolutamente no xD. Non nominiamo Ingegneria... da me si chiama Ingegneria del software ed è un altro esame, un mostro di esame... non lo nominiamo quasi mai da me, ci vogliono fisicamente minimo 4 mesi per prepararlo e ti devi dedicare anima e corpo solo a quello, al massimo ci metti vicino 2 esami "facili". Non è da 12 crediti.
Il libro della prof si chiama Fondamenti di informatica. Autori: alfred v.aho, Jeffrey D. Hullman
Ora mi metto a vedere un po quello che mi hai consigliato, non ti dico la tensione che ho... sta prof è sempre un ? ma devo prendermi sto esame che odio (colpa della prof che lo fa odiare).
Cmq assolutamente no xD. Non nominiamo Ingegneria... da me si chiama Ingegneria del software ed è un altro esame, un mostro di esame... non lo nominiamo quasi mai da me, ci vogliono fisicamente minimo 4 mesi per prepararlo e ti devi dedicare anima e corpo solo a quello, al massimo ci metti vicino 2 esami "facili". Non è da 12 crediti.
Il libro della prof si chiama Fondamenti di informatica. Autori: alfred v.aho, Jeffrey D. Hullman
Ora mi metto a vedere un po quello che mi hai consigliato, non ti dico la tensione che ho... sta prof è sempre un ? ma devo prendermi sto esame che odio (colpa della prof che lo fa odiare).
Cmq se vuoi, per piacere mi svolgi il primo esercizio? Così potrò sapere se ho fatto bene o meno l'esercizio.
Vediamo, te lo svolgo come sono solito farli, è più veloce, se non ti è chiaro il metodo lo convertiamo in "punti" come sei solito fare
$T(n) = 4T(n/2) + n/2$ lo svolgo con il metodo dell'albero, ideale in questi casi perchè ti da una panoramica su cosa stai facendo e penso tu comprenda meglio come svolgere una ricorsione
La radice dell'albero è il parametro $n/2$ libero, su cui la funzione $T(n/2)$ ricorre $4$ volte. Perciò si avranno nodi multipli di $4$, e un'altezza con profondità $log_2(n)$ per via del dimezzamento (e anche perchè è una proprietà che ti da l'esercizio).
Ti ho scansionato l'albero disegnato, con le somme dei vari livelli, non avevo molta voglia e tempo di riscriverlo in vettoriale...
(Clicca sopra per ingrandire)
La somma dei nodi interni (al livello $i$) fino all'altezza $h-1$ verrà calcolata da una sommatoria (non scrivo tutti i vari passaggi, sono banali proprietà delle potenze):
$sum_{i=1}^{log_2(n)-1} 2^(2(i-1))*(n/2^i) = n/4*sum_{i=1}^{log_2(n)-1} 2^(2i)/2^i = n/4*sum_{i=1}^{log_2(n)-1} (2^2/2)^i = n/4*sum_{i=1}^{log_2(n)-1} 2^i = n/4*sum_{k=0}^{log_2(n)-2} 2^k$
che è una serie geometrica che si calcola con la nota formula:
$n/4*sum_{k=0}^{log_2(n)-2} 2^k = n/4*((2^((log_2(n)-2)+1)-1)/(2-1)) = n/4*(2^(log_2(n))/2-1) = n/4*(n/2-1) = n^2/8 - n/4 $
al livello $h$ le foglie sono $n^2$, sommando questo risultato con i nodi interni si avrà:
$n^2/8 - n/4 + n^2 in O(n^2)$ per le proprietà della somma e non considerando le costanti perchè è una limitazione superiore.
perciò l'equazione risulterà avere una limitazione superiore di $O(n^2)$.
NOTA: per fare le cose bene, si dovrebbe dimostrare per induzione su T(n) che tale limitazione è sempre vera perchè questo metodo ipotizza (calcola) una limitazione non dimostra.
I punti non chiari dilli, che cerco di spiegarteli (con un po' di conoscenze di proprietà delle potenze e sommatorie ce se la cava), se vedi non è diverso da quanto l'esercizio chiede, anzi è equivalente.
PS:
Se non è un corso di Ingegneria, presumo ti faccia un cdl di Informatica o una cosa simile (Ingegneria del software si fa quasi sempre in questi corsi). Perciò in questo corso di fondamenti, tratti anche argomenti di algoritmi (programmazione dinamica, backtrack, ecc..)?
$T(n) = 4T(n/2) + n/2$ lo svolgo con il metodo dell'albero, ideale in questi casi perchè ti da una panoramica su cosa stai facendo e penso tu comprenda meglio come svolgere una ricorsione
La radice dell'albero è il parametro $n/2$ libero, su cui la funzione $T(n/2)$ ricorre $4$ volte. Perciò si avranno nodi multipli di $4$, e un'altezza con profondità $log_2(n)$ per via del dimezzamento (e anche perchè è una proprietà che ti da l'esercizio).
Ti ho scansionato l'albero disegnato, con le somme dei vari livelli, non avevo molta voglia e tempo di riscriverlo in vettoriale...
(Clicca sopra per ingrandire)
La somma dei nodi interni (al livello $i$) fino all'altezza $h-1$ verrà calcolata da una sommatoria (non scrivo tutti i vari passaggi, sono banali proprietà delle potenze):
$sum_{i=1}^{log_2(n)-1} 2^(2(i-1))*(n/2^i) = n/4*sum_{i=1}^{log_2(n)-1} 2^(2i)/2^i = n/4*sum_{i=1}^{log_2(n)-1} (2^2/2)^i = n/4*sum_{i=1}^{log_2(n)-1} 2^i = n/4*sum_{k=0}^{log_2(n)-2} 2^k$
che è una serie geometrica che si calcola con la nota formula:
$n/4*sum_{k=0}^{log_2(n)-2} 2^k = n/4*((2^((log_2(n)-2)+1)-1)/(2-1)) = n/4*(2^(log_2(n))/2-1) = n/4*(n/2-1) = n^2/8 - n/4 $
al livello $h$ le foglie sono $n^2$, sommando questo risultato con i nodi interni si avrà:
$n^2/8 - n/4 + n^2 in O(n^2)$ per le proprietà della somma e non considerando le costanti perchè è una limitazione superiore.
perciò l'equazione risulterà avere una limitazione superiore di $O(n^2)$.
NOTA: per fare le cose bene, si dovrebbe dimostrare per induzione su T(n) che tale limitazione è sempre vera perchè questo metodo ipotizza (calcola) una limitazione non dimostra.
I punti non chiari dilli, che cerco di spiegarteli (con un po' di conoscenze di proprietà delle potenze e sommatorie ce se la cava), se vedi non è diverso da quanto l'esercizio chiede, anzi è equivalente.
PS:
Se non è un corso di Ingegneria, presumo ti faccia un cdl di Informatica o una cosa simile (Ingegneria del software si fa quasi sempre in questi corsi). Perciò in questo corso di fondamenti, tratti anche argomenti di algoritmi (programmazione dinamica, backtrack, ecc..)?
Forse abbiamo due nomi uguali ma esame completamente diverso.
Ingegneria del Software in pratica si chiede di creare da zero un software e renderlo esecutivo. Ex: Progetto: voglio creare un software per i sistemi biometrici per la polizia, scelgo il linguaggio di programmazione e tutto quello che mi serve, eseguo il debugging e vedo se funziona nella vita reale. Infine stampo un libro del software, proprio come se fosse un software in commercio. Ovviamente da soli è da suicidio, bisogna essere minimo in 2 ma di solito si è in 4/5.
Questi invece sono gli argomenti di FP:
Selection sort ricorsivo ed iterativo
Mergesort
Tempo di esecuzione di split, merge, mergesort
Induzione strutturale e basilare
Albero ricorsivo, binario, binario di ricerca, ricorsione binaria
Alberi e puntatori
Visite alberi (preorder, postorder, inorder)
Correttezza selection sort, mergesort, lista a puntatori, lista a doppi puntatori, puntatori con mergesort, visite albero
Sorting iterativo
O-grande
Liste mediante array
Code mediante array, array circolare
Stack mediante array, liste a puntatori
Grafi
Automi def e nfa
Piu o meno dovrebbe essere questo il programma.
p.s. cercherò di farlo da solo l'esercizio che mi hai svolto, cosi capirò dove mi blocco. Grazie... sei veramente gentile.
Ingegneria del Software in pratica si chiede di creare da zero un software e renderlo esecutivo. Ex: Progetto: voglio creare un software per i sistemi biometrici per la polizia, scelgo il linguaggio di programmazione e tutto quello che mi serve, eseguo il debugging e vedo se funziona nella vita reale. Infine stampo un libro del software, proprio come se fosse un software in commercio. Ovviamente da soli è da suicidio, bisogna essere minimo in 2 ma di solito si è in 4/5.
Questi invece sono gli argomenti di FP:
Selection sort ricorsivo ed iterativo
Mergesort
Tempo di esecuzione di split, merge, mergesort
Induzione strutturale e basilare
Albero ricorsivo, binario, binario di ricerca, ricorsione binaria
Alberi e puntatori
Visite alberi (preorder, postorder, inorder)
Correttezza selection sort, mergesort, lista a puntatori, lista a doppi puntatori, puntatori con mergesort, visite albero
Sorting iterativo
O-grande
Liste mediante array
Code mediante array, array circolare
Stack mediante array, liste a puntatori
Grafi
Automi def e nfa
Piu o meno dovrebbe essere questo il programma.
p.s. cercherò di farlo da solo l'esercizio che mi hai svolto, cosi capirò dove mi blocco. Grazie... sei veramente gentile.
Se guadi bene cosa ti chiede l'esercizio, e come lo ho svolto io, le risposte sono tutte esplicite; sta solo a te capire cosa voglia dire la domanda, se è questo il tuo problema.
O proprio non sai cosa sia una "equazione di ricorrenza"?
[OT]
Sì, "Ingegneria del software"tratta gli argomenti che ho trattato pure io, con progetto annesso, un mattone di esame
Anche se lo ho trattato in modo diverso...
Per questo corso di fondamenti, tratta forse solo metà di un corso di algoritmica base, forse per questo si chiama fondamenti...
Ne avrai altri che aprofondiranno questi argomenti...spero.
Una curiosità, ma che a che corso di studi sei iscritto? presumo un qualche corso tipo "Informatica e tecnologia dei pupazzi"
[/OT]
O proprio non sai cosa sia una "equazione di ricorrenza"?
[OT]
Sì, "Ingegneria del software"tratta gli argomenti che ho trattato pure io, con progetto annesso, un mattone di esame
Anche se lo ho trattato in modo diverso...
Per questo corso di fondamenti, tratta forse solo metà di un corso di algoritmica base, forse per questo si chiama fondamenti...
Ne avrai altri che aprofondiranno questi argomenti...spero.
Una curiosità, ma che a che corso di studi sei iscritto? presumo un qualche corso tipo "Informatica e tecnologia dei pupazzi"
[/OT]
Auhauhahuahuahuauhauh ma quale tecnologia dei pupazzi. xD Cmq in realtà non ti so dire, cioè la prof è tutta strana, è a come ci gira... o sbaglia a correggere oppure chiama in maniera diversi gli argomenti. Purtroppo ci sono questi prof. Il primo appello l'ho fatto e per 5 punti non l'ho superato! Al prossimo ci devo riuscire, imparerò bene anche questo O-grande, etc.
In che senso veniva trattato in modo diverso l'esame di I.S.?
Sisi, ci sono altri esami che si basano sulla struttura albero e roba simile.
Sono iscritto a Matematica e Informatica al campus di Fisciano (Salerno) e il percorso che ho scelto è Reti Informatiche (programmazione distribuita su ambiente RMI, sicurezza su reti tipo crittografia avanzata, firme digitali, certificati X.509 e altri esami)
Il mio problema non è la volontà, ma capire che minchia vuole la prof. Non spiega bene le cose, le arronza. Questo perché è un corso di trasformazione e non gli stanno dando peso. Cmq non importa, io questo esame me lo devo prendere!
In che senso veniva trattato in modo diverso l'esame di I.S.?
Sisi, ci sono altri esami che si basano sulla struttura albero e roba simile.
Sono iscritto a Matematica e Informatica al campus di Fisciano (Salerno) e il percorso che ho scelto è Reti Informatiche (programmazione distribuita su ambiente RMI, sicurezza su reti tipo crittografia avanzata, firme digitali, certificati X.509 e altri esami)
Il mio problema non è la volontà, ma capire che minchia vuole la prof. Non spiega bene le cose, le arronza. Questo perché è un corso di trasformazione e non gli stanno dando peso. Cmq non importa, io questo esame me lo devo prendere!
Ho fatto i calcoli, ho capito tutti i procedimenti, ma non ho capito i risultati.
Cioè T(1) = , T(2)=, etc, a cosa corrispondono? A T(1) = 4^1 * n/4 e T(2) = 4^2 * n/2^3?
Il problema è che la prof usa un metodo diverso, non lo so se poi usando il tuo metodo per lei va bene, è una schizzata...
Cmq ho capito tutti i procedimenti del disegno.
Non mi vorrei sbagliare, ma vedendo gli appunti di quel tizio che mi hai suggerito su questo sito, la notazione O-grande è diversa da quella della prof.
Nella slide c'è scritto questo:
DEFINIZIONE
Dati il running time T(n) ed una funziona f(n), definita per ogni intero n>= 0
T(n) = O(f(n)) <-> (se e solo se) esistono n0 > 0 e c>0 tali che per ogni n>= n0 risulta T(n) < cf(n)
Es: Dato (T0) = 0 e T(N) = (n+1) * (n+2), n >0
mostriamo che T(n) = O(n^2). Cioè f(n) = n^2
Prendiamo n0 = 1, c=6:
T(n) = (n+1)(n+2) = n^2+3n+2 <= n^2+3n^2+2n^2 ( per n >= 1, n0=1 <= n <= n^2) = 6n^2 = c n^2 = c f(n)
Ora sto studiando su quel libro che scaricai, lo stesso che mi dicesti tu. Penso che la cosa importante sia capire, poi l'approccio passa in secondo piano... almeno spero.
Cioè T(1) = , T(2)=, etc, a cosa corrispondono? A T(1) = 4^1 * n/4 e T(2) = 4^2 * n/2^3?
Il problema è che la prof usa un metodo diverso, non lo so se poi usando il tuo metodo per lei va bene, è una schizzata...
Cmq ho capito tutti i procedimenti del disegno.
Non mi vorrei sbagliare, ma vedendo gli appunti di quel tizio che mi hai suggerito su questo sito, la notazione O-grande è diversa da quella della prof.
Nella slide c'è scritto questo:
DEFINIZIONE
Dati il running time T(n) ed una funziona f(n), definita per ogni intero n>= 0
T(n) = O(f(n)) <-> (se e solo se) esistono n0 > 0 e c>0 tali che per ogni n>= n0 risulta T(n) < cf(n)
Es: Dato (T0) = 0 e T(N) = (n+1) * (n+2), n >0
mostriamo che T(n) = O(n^2). Cioè f(n) = n^2
Prendiamo n0 = 1, c=6:
T(n) = (n+1)(n+2) = n^2+3n+2 <= n^2+3n^2+2n^2 ( per n >= 1, n0=1 <= n <= n^2) = 6n^2 = c n^2 = c f(n)
Ora sto studiando su quel libro che scaricai, lo stesso che mi dicesti tu. Penso che la cosa importante sia capire, poi l'approccio passa in secondo piano... almeno spero.
per cortesia utilizza ASCIIMathML o Latex per scrivere le formule, ci si mette il triplo a capire
Il metodo dell'albero di ricorsione è la rappresentazione grafica del metodo dell'iterazione, che la tua docente utilizza.
Le foglie sono il limite sulla condizione dell'equazione di ricorrenza, che la rende valida.
Cioè il tuo esercizio dice:
$4T(n/2) + n/2$ per n potenza di 2 e n>1
cioè che questa equazione è valida per numeri fino ad n=2 e con potenze di 2. Per n=1 o 0 la funzione diventa $1$ (per semplicità), non è specifato invece cosa fare con numeri non divisibile per 2, mettiamo 1 per semplicità.
Se vedi le foglie si fermano a T(1) (te lo ho scritto) livello $h$, T(2) è $h-1$, T(3) non è valido, ecc... è un albero inverso.
es: l'esercizio chiede:
e) Per quale valore di $i$ si può eliminare $T(n/2^i)$ dall'espressione?
al livello $i$ sull'albero (mi segui?) la somma dei nodi è: $2^(2(i-1))*(n/2^i)$ ($i$ è il livello attuale)
al livello $h$ la formula diverrà a sostituire: $2^(2(h-1))*(n/2^h)$ adesso chiediti che valore elimina $n/2^i= n/2^h$?
$h=log_2(n)$ siamo in potenze di 2 per la divisione.
$n/2^(log_2(n)) = n/n^(log_2(2)) = n/n = 1$ perciò:
$2^(2(h-1))*1 =$ come immagine a livello $h$
abbiamo tolto il valore come richiesto dall'esercizio.
Adesso è più chiaro come convertire, è identico (solo capovolto, parti da T(n) invece che da T(1)).
La notazione O-grande differisce in campi differenti della matematica, più semplicemente in Informatica ha la definzione che hai scritto.
PS: Consiglio di utilizzare anche il must "Introduzione agli algoritmi e strutture dati" di Cormen & Co. li è spiegato tutto e oltre.
Il metodo dell'albero di ricorsione è la rappresentazione grafica del metodo dell'iterazione, che la tua docente utilizza.
Le foglie sono il limite sulla condizione dell'equazione di ricorrenza, che la rende valida.
Cioè il tuo esercizio dice:
$4T(n/2) + n/2$ per n potenza di 2 e n>1
cioè che questa equazione è valida per numeri fino ad n=2 e con potenze di 2. Per n=1 o 0 la funzione diventa $1$ (per semplicità), non è specifato invece cosa fare con numeri non divisibile per 2, mettiamo 1 per semplicità.
Se vedi le foglie si fermano a T(1) (te lo ho scritto) livello $h$, T(2) è $h-1$, T(3) non è valido, ecc... è un albero inverso.
es: l'esercizio chiede:
e) Per quale valore di $i$ si può eliminare $T(n/2^i)$ dall'espressione?
al livello $i$ sull'albero (mi segui?) la somma dei nodi è: $2^(2(i-1))*(n/2^i)$ ($i$ è il livello attuale)
al livello $h$ la formula diverrà a sostituire: $2^(2(h-1))*(n/2^h)$ adesso chiediti che valore elimina $n/2^i= n/2^h$?
$h=log_2(n)$ siamo in potenze di 2 per la divisione.
$n/2^(log_2(n)) = n/n^(log_2(2)) = n/n = 1$ perciò:
$2^(2(h-1))*1 =$ come immagine a livello $h$
abbiamo tolto il valore come richiesto dall'esercizio.
Adesso è più chiaro come convertire, è identico (solo capovolto, parti da T(n) invece che da T(1)).
La notazione O-grande differisce in campi differenti della matematica, più semplicemente in Informatica ha la definzione che hai scritto.
PS: Consiglio di utilizzare anche il must "Introduzione agli algoritmi e strutture dati" di Cormen & Co. li è spiegato tutto e oltre.
Ah scusa, ok lo farò sicuramente.
Cmq penso che sia un problema di argomento, cioè gli alberi. Ora li sto vedendo.
Vedi se mi puoi fare questi esempi.
1) scrivere un esempio di albero binario e albero normale.
2) scrivere un esempio di albero binario e albero normale, tutti e due in forma ricorsiva.
3) scrivere un esempio di ricerca binaria e un altro esempio di ricerca binaria nel linguaggio C
Cmq penso che sia un problema di argomento, cioè gli alberi. Ora li sto vedendo.
Vedi se mi puoi fare questi esempi.
1) scrivere un esempio di albero binario e albero normale.
2) scrivere un esempio di albero binario e albero normale, tutti e due in forma ricorsiva.
3) scrivere un esempio di ricerca binaria e un altro esempio di ricerca binaria nel linguaggio C
"utentemain4":
DEFINIZIONE
Dati il running time T(n) ed una funziona f(n), definita per ogni intero n>= 0
T(n) = O(f(n)) <-> (se e solo se) esistono n0 > 0 e c>0 tali che per ogni n>= n0 risulta T(n) < cf(n)
Spero non sia così, ovvero non $T(n)=O(f(n))$ ma bensì$T(n) in O(f(n))$
Non è questione di lana caprina: non è "uguale" in quanto $T(n)$ è una data funzione e $O(f(n))$ è un insieme di funzioni.
Però è strano: non hanno detto chiaramente prima cosa si intende con quel simbolo, O grande o big-O che dir si voglia?
"Rggb":
[quote="utentemain4"]DEFINIZIONE
Dati il running time T(n) ed una funziona f(n), definita per ogni intero n>= 0
T(n) = O(f(n)) <-> (se e solo se) esistono n0 > 0 e c>0 tali che per ogni n>= n0 risulta T(n) < cf(n)
Spero non sia così, ovvero non $T(n)=O(f(n))$ ma bensì$T(n) in O(f(n))$
Non è questione di lana caprina: non è "uguale" in quanto $T(n)$ è una data funzione e $O(f(n))$ è un insieme di funzioni[/quote]
non ti meravigliare, non è un "errore", ma proprio una consuetudine di certi autori o docenti, che utilizzano impropriamente la simbologia.
Alla base di questo c'è una questione più fine; se mettiamo $T(n) = g(n)$, questi autori, esprimono $g(n) = Theta(f(n))$, intendendo dire che $Theta(g(n)) = Theta(f(n))$, cioè un'uguaglianza tra insiemi.
Spero anche che questi autori sappiano di questa cosa; casomai siamo messi male
PS: bella barba
@utentemain4:
ma perciò la terminologia: profondità, radice, livelli, e compagnia, non ti sono familiari. Perciò i calcoli fatti non sapresti riprodurli, anche se gli alberi sono solo un'astrazione per semplificare le idee e quelle sommatorie si possono riprodurre in altri modi.
EDIT:
corretto errore.
Non ne sono sicuro, sto vedendo come funziona il tutto. Ho riportato pari pari come sta scritto nelle slide.
Cmq ham_burst, non mi dire niente... ma mi servirebbero gli esempi, così cerco di capire a volo il procedimento.
L'esame ci sarà Giovedì.
Cmq ham_burst, non mi dire niente... ma mi servirebbero gli esempi, così cerco di capire a volo il procedimento.
L'esame ci sarà Giovedì.
mmm brutta cosa, cercare di apprendere il giorno prima, una cosa come algoritmica.
E' non mi è chiaro, procedimento su cosa? Sugi esercizi degli alberi (1) o sulle equazioni di ricorrenza (2)?
Per (2) ti ho già mostrato il procedimento, più di così...
Per (1):
- un albero binario ha delle specifiche, ha una radice e sempre due figli.
- un albero normale, penso sia un albero generico che può avere $n$ e più figli.
qua dipende dal contesto in cui è richiesto l'esercizio. Penso che devi scrivere una funzione ricorsiva in pseudo-codice delle due tipologie di strutture dati.
la ricerca binaria è la ricerca binaria. E' la base della minima conoscenza in algoritmica. Con google: "binary search" ed è ampiamente discussa.
E' non mi è chiaro, procedimento su cosa? Sugi esercizi degli alberi (1) o sulle equazioni di ricorrenza (2)?
Per (2) ti ho già mostrato il procedimento, più di così...
Per (1):
1) scrivere un esempio di albero binario e albero normale.
- un albero binario ha delle specifiche, ha una radice e sempre due figli.
- un albero normale, penso sia un albero generico che può avere $n$ e più figli.
2) scrivere un esempio di albero binario e albero normale, tutti e due in forma ricorsiva.
qua dipende dal contesto in cui è richiesto l'esercizio. Penso che devi scrivere una funzione ricorsiva in pseudo-codice delle due tipologie di strutture dati.
3) scrivere un esempio di ricerca binaria e un altro esempio di ricerca binaria nel linguaggio C
la ricerca binaria è la ricerca binaria. E' la base della minima conoscenza in algoritmica. Con google: "binary search" ed è ampiamente discussa.
Ho svolto gli esercizi, dimmi se ho capito bene lo svolgimento degli alberi.
1) albero normale http://imageshack.us/photo/my-images/19 ... rmale.jpg/
2) albero normale ricorsivo http://imageshack.us/photo/my-images/19 ... rsivo.jpg/
3) albero binario e albero binario ricorsivo http://imageshack.us/photo/my-images/89 ... sione.jpg/
4) albero binario di ricerca http://imageshack.us/photo/my-images/69 ... cerca.jpg/
5) albero binario di ricerca in forma ricorsiva con il C http://imageshack.us/photo/my-images/87 ... rsiva.jpg/
1) albero normale http://imageshack.us/photo/my-images/19 ... rmale.jpg/
2) albero normale ricorsivo http://imageshack.us/photo/my-images/19 ... rsivo.jpg/
3) albero binario e albero binario ricorsivo http://imageshack.us/photo/my-images/89 ... sione.jpg/
4) albero binario di ricerca http://imageshack.us/photo/my-images/69 ... cerca.jpg/
5) albero binario di ricerca in forma ricorsiva con il C http://imageshack.us/photo/my-images/87 ... rsiva.jpg/
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
