Magazine Università

5 concetti importantissimi in Informatica

Creato il 21 giugno 2010 da Ewilly

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:

image

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:

image

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:

image

image

3.Teorema Fondamentale

E un teorema che ci permette di risolvere molto velocemente una ricorrenza della forma:

image

dove  a >=1 e b > 1 sono costante e f(n) è una funzione e n rappresenta interi positivi.  Ci sono 3 casi:

image

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:

image

Lemma2:

image

Lemma3:

image

Grazie per aver letto l’articolo. Dubbi,domande e suggerimenti?? spazio commenti si trova qui sotto.

avatar firma



Potrebbero interessarti anche :

Ritornare alla prima pagina di Logo Paperblog

Possono interessarti anche questi articoli :

  • I will survive!

    will survive!

    Sono viva. Così, a titolo informativo. Sono sopravvissuta al #NoDietDay facendo la dieta e sentendomi dire, con tanto amore, quanto da me condiviso su... Leggere il seguito

    Da  Doppiogeffer
    DIARIO PERSONALE, PER LEI, TALENTI, UNIVERSITÀ
  • Troppe cose....

    Onta e disonore su me e il mio blog.Di questo passo, il fatto di pubblicare un random post alla settimana mi pare un lusso sfrenato. Leggere il seguito

    Da  Doppiogeffer
    DIARIO PERSONALE, PER LEI, TALENTI, UNIVERSITÀ
  • Fatti li cazzi tua formato RAW.

    Fatti cazzi formato RAW.

    <<Non puoi dire sempre "cazzo",dannazione!>>Uhhh, madò che sei pignola!<<Io sarò pignola ma tu sei scurrile. Inoltre nemmeno un paio di... Leggere il seguito

    Da  Doppiogeffer
    DIARIO PERSONALE, PER LEI, TALENTI, UNIVERSITÀ
  • Violenza, quella oltre lo schiaffo

    Violenza, quella oltre schiaffo

    A me non è mai piaciuta l’idea secondo cui ci debba essere la festa della donna, la festa della mamma/papà, la festa per qualcuno. Leggere il seguito

    Da  Nonchiamatemiborgia
    DIARIO PERSONALE, PER LEI, UNIVERSITÀ
  • Ci sono giorni in cui è bene non metter le zampe fuori dal letto

    sono giorni bene metter zampe fuori letto

    Non so voi ma...<<E che palle, non puoi sempre iniziare tutti i post con "non so voi"! Cioè, ormai loro lo sanno che tu non sai niente, però non puoi... Leggere il seguito

    Da  Doppiogeffer
    DIARIO PERSONALE, PER LEI, TALENTI, UNIVERSITÀ
  • Povia, Governo Ladro (e Signorini poco educato)

    Povia, Governo Ladro Signorini poco educato)

    "Ohibò, e cos'è successo mai? Son saltate altre due listography!Vuoi vedere che Doppio Geffer è sparita di nuovo dalla circolazione? Vuoi vedere che non ci... Leggere il seguito

    Da  Doppiogeffer
    DIARIO PERSONALE, PER LEI, TALENTI, UNIVERSITÀ
  • Rosso di sera e dispense alla pera

    Si sa; il rientro post vacanze estive è deleterio per il corpo e per la mente. La solita routine, i soliti orari impossibili con pasti improponibili, le solite... Leggere il seguito

    Da  Doppiogeffer
    DIARIO PERSONALE, PER LEI, TALENTI, UNIVERSITÀ

Dossier Paperblog

Magazine