Riassunto esame Fondamenti d'informatica 2, Prof. Spaccamela Alberto, libro consigliato Dispense Docente, Spaccamela

F.I.2{Modelli} By ThePres

Complessità PT1 minima complessità di un programma

Efficienza = risolvere problema con poche risorse di calcolo (programmi più eff. altro che gli altri usano meno risorse di calcolo).

Tempo di calcolo →↳ spazio (memoria).

Risorsa critica.

Costa semplice (meno quindi) è più semplice da implementare.

Non posso misurarlo in secondi perché non sarebbe obiettivo.

• F.C. usato
• Linguaggio
• Dati

Necessità quindi una sintassi generale indipendente da 1, 2, 3.

Scriviamo quindi una funzione matematica il cui arg è dim. dell'input e per svincolarci da calcolatori particolari uso↳ modello Macchina V. Neumann, visto che è adattabile ad ogni linguaggio/pseudocodice.

Analisi costi

Ogni: istr. elementare ha costo unitario.

Ciclo, if, sottoprogrammi vanno fatti i calcoli.

Oss.

_t₁ = tempo exec. istr 1.

_t₂ = n . . . 2↳ _t₂ grande di _t₁ o meno di costante.

_c ↔ costo equivalente istr. semplice o meno di costante.

def₁

Il costo di un programma viene valutato in funzione della dimensione dell'input con riferimento al caso peggiore, assumendo che il costo di ogni singola istr. elementare sia uno.

Analisi asintotica: notazione O

def₁

Un programma ha costo/complessità O(g(n)) se: il suo tempo di esec. (k isti.) è t(n) ∃ a, b, n₀ t.c. t(n) ≤ a g(n) + b ∀ n ≥ n₀.

Oss.

O(1) → # costanti di op.

def _{Upper Bound}

• Un problema ha una delimitazione superiore O(f(n)) alla sua complessità, se ∃ alg. di sol. che ha complessità Θ(f(n)).
• Se g(n) ∈ O(f(n)) ⇒ g(n) cresce al + come f(n).
• Per note: _n→∞ lim f(n) / f(n) = 1 ⇒ _n→∞ lim f(n) / g(n) ⇒ ∞.

Proprietà

• Costanti non contano.
• Quando ho una funzione come somma di f, mi concentro su quella che cresce di più.
• Dato a_n con a_ch n^a ∈ Θ(n^b).
• H^b ∉ Θ(n^a).
• Logaritmo < polinomiale < esponenziale.

Vantaggi: semplice da calcolare.

Svantaggi: perdo le costanti (le posso immaginare a intuito).

Oss. Costo medio dipende dalle probabilità.

Grandezza max input

È un altro modo di verificare l'efficienza, cambiando maxi dell'input che un programma può risolvere in un dato tempo.

Istruzioni dominanti

Sono le istruzioni dominanti che vengono più eseguite più volte ⇒ quelle dei cicli interni.

• Guarda istr. in cicli interni.
• Quante volte sono eseguite? → in funzione input.

Notazione Ω (Upper bound)

Rappresenta una delimitazione inferiore quindi f cresce almeno come g.

Un programma ha costo Ω(f(n)) sse:

Tempo di esecuzione è t(n).

∃ a>0, n₀ t.c. t(n) > a f(n) ∀ n > n₀.

Non la possiamo sfruttare comodamente per esprimere la complessità intrinseca del problema.

Questo perché per farlo dovremmo considerare anche gli sviluppi di futuri algoritmi, che potenzialmente potrebbero essere migliori.

Costi notevoli

"Costi notevoli"

Costo ricerca elem. in array con n elem.

Ω (log (n))

Costo ordinamento array n elem.

Ω (n log (n))

Notazione Θ

Se g(n) rappresenta sia un upper bound che un lowerbound del problema, i.e.

• Ho programma XXX sol con costo f(n) = O(g(n)).
• Posso dim. che compl. probl è Ω(f(n)) ⇒ in problema ha complessità Θ(f(n)).

Recap

• Costo - quante istruzioni vengono eseguite.
• Correttezza - costo del suo programma migliore.

Problemi P/NP

Classe P

Insieme dei problemi per i quali esiste una molt. che li risolve in tempo polinomiale nella dim. dell'input.

Esempi

• Vedere se un elemento è in una lista.
• Decidere il valore di una formula booleana dati i dati delle var.
• Ord. array.
• Somma 2 int.

Calcolabilità

Teo

Il numero dei programmi ha cardinalità pari a ℵ1, quindi, il numero dei programmi è numerabile↳ dim su elenco testi.

Problemi di decisione

È una arbitraria domanda del tipo sì/no, vero/falso, relativa ad un insieme infinito di possibili ingressi, che vengono partizionati in 2 insiemi, di quello che