Ciao a tutti, oggi vi parlerò di 5 concetti chiave quando si tratta di informatica,programmazione o algoritmi.
1. Caso migliore ,caso peggiore ,caso medio e poi??
Più volte usiamo queste parole per giudicare le prestazioni di un algoritmo. T(n) è numero di operazioni elementari compiuto da un algoritmo. Per valutare la prestazione di un algoritmo ,ci interessa calcolare questo numero.-Caso migliore
termine usato per riferirsi al caso di figura in cui è molto facile risolvere un problema con un certo algoritmo e un certo input. In generale in questo caso il numero di operazioni da eseguire dall’algoritmo il minor possibile.-Caso peggiore
termine usato per riferirsi al caso di figura in cui il numero di operazioni da eseguire dall’algoritmo è il maggior possibile. Si può paragonare questo caso alla realità parlando della sfortuna.
Quindi T(n)=massimo tempo di esecuzione per qualsiasi input di dimensione n.
-Caso medio
termine usato per riferirsi al caso di figura in cui si cerca di predire qual’è il valore medio di T(n) su tutti gli ingressi possibili.
quindi T(n)= valore atteso del tempo di esecuzione su tutti gli ingressi di dimensione n.
Per farlo dobbiamo ipotizzare una distribuzione di probabilità sui dati di input.
Nella valutazione di un algoritmo ,quale caso usare per il calcolo di T(n)?
-
Non si usa quasi mai nella valutazione di un algoritmo perché nei casi reali,non succede quasi mai.-Di solito si usa il caso medio perché copre quasi tutti i casi di figura.
-Conviene però considerare anche il caso peggiore per le seguenti ragioni:
.il caso peggiore ci da un stima massima del tempo di esecuzione
.Capita molto spesso di avere un caso peggiore. Per esempio la ricerca di un dato inesistente in un database.
.A volte il caso medio è molto vicino al caso peggiore.
2.Invariante di ciclo
L’invariante di ciclo è un'affermazione usata per dimostrare la correttezza di un algoritmo. Vediamo come funziona:
Sostanzialmente,vogliamo dimostrare che un’affermazione è vera prima,all’interno e dopo un ciclo. I passi sono 3:
1.Si dimostra che l’affermazione è vera prima del ciclo
2.si dimostra che l’affermazione rimane vera nel passaggio dell’iterazione i all’iterazione i+1.
3.si dimostra che l’affermazione è vera alla fine del ciclo
Nella maggior parte dei casi il verificarsi del caso 3 combacia con la correttezza dell’algoritmo.
3.Tipo di programmazione
Ce ne sono 3 fondamentali per gli algoritmi:
1.Procedurale
La programmazione procedurale è una programmazione lineare nel senso che si va sempre dritto un passo segue l’altro fino al passo finale. E quella più semplice e più naturale da usare.
2.Ricorsiva
La programmazione ricorsiva è una programmazione non lineare perché usa la ricorrenza. La ricorrenza è per un algoritmo ,il fatto di richiamare se stesso una o più volte con argomenti piu piccoli. L’esempio piu naturale è quello del fattoriale : n!= n*(n-1)!
E molto usato e aiuta a risolvere problemi ripetitivi senza dover riscrivere o modificare più volte lo stesso algoritmo.
3.Dinamica
La programmazione dinamica è un modo di programmare che divide il problema in piccole istanze di se stesso per poi risolverli in modo ricorsivo e ricombinare l soluzioni. La cosa che lo rende dinamico è che le istanze del grande problema non sono indipendenti fra di loro,il che significa che bisogna sempre tenere dei risultati ottenuti fino ad ora e cosi via.
Campo di applicazione: Problemi di ottimizzazione.
4.Divide and Impera:
Divide and Conquer è un metodo di risoluzione di problema che consiste nel dividere un problema in piccole istanze di se stesso per poi risolverli in modo ricorsivo e ricombinare l soluzioni. ci sono 3 passi:
1.Divide
Divide il problema in sotto problemi cioè piccole istanze di se stesso.
2.Impera
Risolvere i sotto problemi in modo ricorsivo. Se la dimensione del sotto problema è abbastanza piccola,risolvere in modo diretto.
3.Combina
Combinare le soluzioni dei sotto problemi nella soluzione del Grande problema.
5.Analisi di un algoritmo ricorsivo
Valutare la complessità di un algoritmo ricorsivo ci pone davanti a un problema di ricorrenza cioè l’espressione del tempo di esecuzione è una ricorrenza di questo tipo:
Come si risolve questa ricorrenza?
esistono 3 modi:
1.Metodo di sostituzione
Questo metodo consiste in 2 passi:
-Congettura del valore di T(n)
-Usare l’induzione matematica per dimostrare la congettura appena fatta.
Esempio pratico:
2.Albero di ricorsione
Non è un metodo formale e non dimostra la ricorrenza. Si usa per capire cosa succede in dettaglio e per formulare una congettura.
Esempio pratico:
3.Teorema Fondamentale
E un teorema che ci permette di risolvere molto velocemente una ricorrenza della forma:
dove a >=1 e b > 1 sono costante e f(n) è una funzione e n rappresenta interi positivi. Ci sono 3 casi:
Dimostrazione:
La prima parte della dimostrazione analizza la ricorrenza fondamentale con la supposizione che b sia una potenza esatta di n. Per questa parte ci sono 3 lemmi da dimostrare. Il primo riduce il problema della ricorrenza fondamentale al problema della valutazione di una sommazione. Il secondo lemma valuta questa sommazione. Il terzo lemma mette insieme il primo e il secondo per dimostrare il teorema fondamentale nel caso in cui b è una potenza esatta di n.
Lemma1:
Lemma2:
Lemma3:
Grazie per aver letto l’articolo. Dubbi,domande e suggerimenti?? spazio commenti si trova qui sotto.
Benvenuto caro Lettore!
UF è un blog di ingegneria informatica pieno di articoli più o menoo tecnici. Iscriviti per rimanere aggiornato all'uscità dei prossimi articoli.