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

F.I.2

{Modelli}

By ThePres

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 quidi) è più semplice da implementare
• Non posso misurarlo in secondi perché non sarebbe obiettivo

1. F.C. usato
2. linguaggio
3. 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: istru 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}

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

Proprietà

1. Costanti non contano
2. Quando ho una funzione come somma di f, mi concentro su quella che cresce di più
3. Dato a_n con a_ch
   • n^a ∈ Θ(n^b)
   • h^b ∉ Θ(n^a)
4. 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 che vengono più eseguite più volte ⇒ quelle dei cicli interni.

1. Guarda istr. in cicli interni
2. 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"

COSTO RICERCA ELEM.IN ARRAY CON N ELEM

Ω (log (n))

COSTO ORDINAMENTOARRAY N ELEM

Ω (n log (n))

NOTAZIONE Θ

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

1. Ho programma XXX sol con costo f(n) = O(g(n))2. 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