ALGORITMI
DEFINIZIONE : (LIMITE ASINTOTICO SUPERIORE) date due funzioni f(n) , g(n)>= 0 si dice che f(n) è un O(g(n)) se esistono 2 costanti c ed n0 tali che 0<= f(n)< c g(n) per ogni n>=n0
REGOLA : sia f(n) un polinomio di grado m allora f(n) è un O(n^m)
DEFINIZIONE : (LIMITE ASINTOTICO INFERIORE) date due funzioni f(n) , g(n) >= 0 si dice che f(n) è un omega(g(n)) se esistono due costanti c e n0 tali che f(n) > = g(n) per ogni n > n0
REGOLA : sia f(n) un polinomio di grado m : allora f(n) è un omega (n^m)
DEFINIZIONE : (LIMITE ASINTOTICO STRETTO) date due funzioni f(n) , g(n) si dice che f(n) è un teta di g(n) se esistono 3 costanti c1 , c2 ed n0 tali che c1 g(n)<= f(n) <= c2g(n) per ogni n >= n0
REGOLA : sia f(n) un polinomio di grado m : allora f(n) è un teta di (n^m)
ALGEBRA DELLA NOTAZIONE ASINTOTICA :
1A per ogni k > 0 e per ogni f(n) > 0 , se f(n) è un O(g(n)) allora lo è anche k(n)
questa regola vale anche per la funzione omega e teta , in poche parole stiamo dicendo che le costanti moltiplicative le possiamo ignorare
REGOLA SULLA COMMUTAZIONE SULLA SOMMA:
2A per ogni f(n),d(n) > 0 , se f(n) è un O(g(n)) e d(n) è un O(h(n)) allora f(n) + d(n) è un O(g(n) + h(n)) = O (max(g(n),h(n)))
informalmente possiamo dire che le notazioni asintotiche commutano con l'operazione di somma
REGOLA SULLA COMMUTAZIONE DEL PRODOTTO:
3A per ogni f(n) , d(n) > 0 , se f(n) è un O(g(n)) e d(n) è un O(h(n)) allora f(n)d(n) è un O(g(n)h(n))
informalmente si può dire che le notazioni asintotiche commutano con l'operazione di prodotto
COSTO DI UN ALGORITMO :
è una funzione monotona crescente della dimensione dell'input che rappresenta il tempo di esecuzione
un algoritmo potrebbe avere tempi di esecuzione diversi a seconda dell'input , quello che noi dobbiamo fare è trovare il caso migliore e il caso peggiore
usiamo la notazione asintotica teta in modo da sapere che il costo non è minore ne maggiore di un certo valore , nei casi non riusciamo ad avere una notazione asintotica teta ci dobbiamo accontentare di una omega e di una o grande
REGOLE GENERALI :
1) il costo di un algoritmo è pari alla somma delle complessità che lo compongono
2) le istruzioni elementari hanno tutte costo costante , questa costante è diversa da istruzione ad istruzione ma noi possiamo farla ricadere in teta(1)
3) l'istruzione if (condizione) then istruzione1 else istruzione2 a costo pari al costo di verifica della condizione (di solito costante) piu il massimo dei costi di istruzione1 e istruzione2
4) le istruzioni iterative hanno un costo pari alla somma dei costi massimi di ciascuna delle iterazioni . se tutte le iterazioni hanno costo costante allora è pari al prodotto del costo massimo di una singola iterazione per il numero di iterazioni , la condizione viene valutata una volta in piu per uscire dal ciclo
LA RICERCA SEQUENZIALE : ispezioniamo uno alla volta gli elementi del vettore , confrontiamo ciascun elemento con v , restituiamo il risultato appena trovato v
LA RICERCA BINARIA : ipotesi gli elementi della sequenza devono essere ordinati , ispezioniamo l'elemento centrale della sequenza , se esso è uguale al valore cercato ci fermiamo , se il valore cercato è piu piccolo proseguiamo nella ricerca nella parte sinistra della sequenza se è piu grande nella parte destra , poi itero il procedimento finche non rimane un solo valore nella seuquenza
FUNZIONI MATEMATICHE RICORSIVE : è detta ricorsiva quando la sua definizione è espressa in termini di se stessa
esempio : il n! = n * (n-1) questa è la parte ricorsiva della funzione , che si esprime in termini di se stessa meno un intero 0! = 1 questo determina un altro aspetto fondamentale , detto CASO BASE : che determina la fine della ricorsività della funzione ; in una espressione matematica ricorsiva il caso basse deve esserci sempre
ALGORITMO RICORSIVO : un algoritmo ricorsivo ha sempre queste proprietà , il problema viene diviso in sotto problemi di dimensione minore risolvibili con lo stesso algoritmo poi ricombina i risultati tra loro per determinare il risultato finale.
La successione dei sottoproblemi che sono sempre piu piccoli deve sempre convergere ad un sottoproblema che costituisce un caso base (detto anche CONDIZIONE DI TERMINAZIONE)
ogni funzione richiede per la sua esecuzione , una certa quantità di me moria RAM .
1) caricare in memoria il codice della funzione
2) passare i parametri alla funzione
3) memorizzare i valori delle variabili locali della funzione
quindi le funzioni ricorsive hanno bisogno di piu memoria di quelle ricorsive
click to edit
EQUAZIONI DI RICORRENZA : servono per determinare costo computazionale di algoritmi ricorsivi
è costituita da due oggetti che sono FORMULAZIONE RICORSIVA e CASO BASE
La parte generale di un equazione di ricorrenza deve essere costituita sempre dalla somma di almeno due addendi di cui almeno uno contiene la parte ricorsiva , mentre uno rappresenta il costo computazionale di tutto cio che viene eseguito fuori dalla chiamata ricorsiva
MODI PER RISOLVERE L'EQUAZIONE DI RICORRENZA :
1) METODO DI SOSTITUZIONE
2) METODO ITERATIVO
3) METODO DELL'ALBERO
4) METODO PRINCIPALE (che non faremo si presta a piccoli errori)
METODO DI SOSTITUZIONE : si ipotizza una soluzione per l'equazione di ricorrenza e si verifica se essa funziona , questo metodo è indispensabile in delle dimostrazioni
METODO ITERATIVO : sviluppare l'equazione di ricorrenza ed esprimerla come somma di termini da n e dal caso base