Nozioni Algoritmi e strutture dati

Cose da sapere di algoritmi e strutture dati

Corso del professor Sgarro

L'informatica non riguarda i computer più di quanto l'astronomia riguardi i telescopi. - Edsger Dijkstra

A cura di Gaia Michelazzi

Definizione di algoritmo

Algoritmo: procedura di calcolo ben definita che prende in input uno o più valori e genera un valore, o un insieme di valori, come output. Un algoritmo è quindi una sequenza di passi computazionali che trasforma l'input in output.

Il termine algoritmo deriva dal nome del matematico persiano Al-Khwarizmi, vissuto nel IX secolo d.C., considerato il padre del concetto di algoritmo.

Problema computazionale

Il problema che l'algoritmo deve risolvere.

Istanza di un problema: sequenza di dati di input richiesti per calcolare la soluzione del problema.

Caratteristiche degli algoritmi

• Corretto: per ogni istanza di input termina con l'output desiderato.
• Errato: per qualche istanza di input fornisce una soluzione diversa da quella desiderata o non termina affatto.

N.B. Anche un algoritmo errato può essere utilizzato, a patto che se ne possa controllare il tasso di errore.

Descrizione degli algoritmi

• Flow-chart: sequenza di blocchi di forme diverse (a seconda del ruolo ricoperto) di istruzioni lette dall'alto verso il basso.
• Codice macchina: codice scritto con un linguaggio di programmazione qualsiasi.
• Pseudocodice: codice scritto in un linguaggio che unisce quello macchina a un linguaggio più comprensibile (nel nostro caso l'italiano). [Noi useremo sempre lo pseudocodice per i nostri algoritmi]

Parole chiave

Analizzare un algoritmo: prevedere le risorse che l'algoritmo richiede.

Risorse di primaria importanza: tempo di elaborazione.

Risorse di secondaria importanza: memoria, larghezza di banda, hardware.

Efficienza di un algoritmo

Si misura in base al tempo di esecuzione, ovvero il numero di operazioni primitive (o passi) che vengono eseguite, scritto in funzione della dimensione dell'input di un algoritmo (dipende dal problema che si sta studiando, per la maggior parte dei casi è il numero di elementi dell'input).

Tempo di esecuzione di una riga: costante.

Abbiamo 3 tempi di esecuzione:

• Tempo di esecuzione nel caso migliore
• Tempo di esecuzione nel caso medio (o tempo di esecuzione previsto)
• Tempo di esecuzione nel caso peggiore

N.B. Solitamente si determina sempre il tempo di esecuzione nel caso peggiore, ovvero il tempo di esecuzione più lungo per qualsiasi input, per diversi motivi:

1. Il tempo di esecuzione nel caso peggiore è un limite superiore al tempo di esecuzione per qualsiasi input; conoscendo questo tempo abbiamo la garanzia che l'algoritmo non potrà impiegare più tempo.
2. Per alcuni algoritmi il caso peggiore si verifica molto spesso.
3. Il "caso medio" spesso è brutto quasi quanto quello peggiore.

Efficienza asintotica

Analisi del tasso di crescita del tempo di esecuzione per input di dimensioni sufficientemente grandi. Si studia tramite la notazione asintotica o notazione di Landau.

Notazione asintotica o notazione di Landau

Le notazioni usate per descrivere il tempo di esecuzione sono definite da funzioni il cui dominio è l'insieme dei numeri naturali ℕ (sebbene possano essere applicate anche a numeri reali).

Notazione Θ

Per una data funzione f(n), indichiamo con Θ(f(n)) l'insieme delle funzioni g(n) tali che:

Θ(f(n)) = {g(n) ∶ ∃ c₁, c₂ > 0, ∃ n₀ ∈ ℕ • 0 ≤ c₁ • f(n) ≤ g(n) ≤ c₂ • f(n) ∀ n ≥ n₀}

Una funzione appartiene all'insieme Θ(f(n)) se esistono delle costanti positive tali che essa possa essere compresa fra c₁ • f(n) e c₂ • f(n) per un valore sufficientemente grande di n. In pratica, il tempo di esecuzione di un algoritmo è compreso tra due valori.

Notazione O

Per una data funzione f(n), indichiamo con O(f(n)) l'insieme delle funzioni g(n) tali che:

O(f(n)) = {g(n) ∶ ∃ c > 0, ∃ n₀ ∈ ℕ • 0 ≤ g(n) ≤ c • f(n) ∀ n ≥ n₀}

Una funzione appartiene all'insieme O(f(n)) se esiste una costante positiva tale che g(n) sia un limite superiore per f(n) per un valore sufficientemente grande di n. In pratica, il tempo di esecuzione di un algoritmo sarà sempre minore di un certo valore.

Notazione Ω

Per una data funzione f(n), indichiamo con Ω(f(n)) l'insieme delle funzioni g(n) tali che:

Ω(f(n)) = {g(n) ∶ ∃ c > 0, ∃ n₀ ∈ ℕ • 0 ≤ c • f(n) ≤ g(n) ∀ n ≥ n₀}

Una funzione appartiene all'insieme Ω(f(n)) se esiste una costante positiva tale che g(n) sia un limite inferiore per f(n) per un valore sufficientemente grande di n. In pratica, il tempo di esecuzione di un algoritmo sarà sempre maggiore di un certo valore.

Proprietà delle notazioni

• Proprietà transitiva: Se f(n) = Θ(g(n)) e g(n) = Θ(h(n)), allora f(n) = Θ(h(n)).
• Proprietà riflessiva: f(n) = Θ(f(n)).
• Proprietà simmetrica: f(n) = Θ(g(n)) se e solo se g(n) = Θ(f(n)).
• Simmetria trasposta: f(n) = O(g(n)) se e solo se g(n) = Ω(f(n)).

Nota bene! Non tutte le funzioni sono asintoticamente confrontabili (non esiste la proprietà di tricotomia dei numeri reali). Esempio: 1 + sin(n) e n non sono confrontabili asintoticamente.

Tipi di algoritmi

• Algoritmi con terminano in tempo polinomiale: f(n) = O(n^k) dove k ≤ costante.
• Algoritmi che non terminano in un tempo polinomiale: f(n) = Ω(n^k) dove k ≥ costante.
• Algoritmi particolarmente difficili da risolvere: f(n) = O(n!), f(n) = Θ(2ⁿ).

Nota bene! Un problema ha un grado di difficoltà minore o uguale di un qualunque problema polinomiale.

Metodi di calcolo della complessità degli algoritmi

• Metodo di sostituzione
• Metodo dell'albero di ricorsione
• Metodo dell'esperto

Metodo di sostituzione

Passaggi:

1. Ipotizzare la forma della soluzione.
2. Usare l'induzione matematica per trovare le costanti e dimostrare che la soluzione funziona. Questo metodo è conveniente quando una complessità è simile a una già calcolata, o posso raggiungere una forma simile tramite una sostituzione di variabili.

Metodo dell'albero di ricorsione

Passaggi:

1. Disegnare un albero di ricorsione.
2. Sommare i costi ottenuti all'interno di ogni livello dell'albero.
3. Sommare i costi di ogni livello.
4. Verificare quanto ottenuto con l'induzione matematica.

Metodo dell'esperto

Posso usarlo per risolvere forme del tipo: T(n) = a • T(n/b) + f(n), con a ≥ 1 e b > 1.

Teorema dell'esperto: date le costanti a e b e la funzione f(n), sia f una funzione definita sugli interi non negativi della ricorrenza T(n) = a • T(n/b) + f(n).

Allora T(n) può essere asintoticamente limitata nei seguenti modi:

• Se f(n) = Θ(n^log_ba-ε) per qualche costante ε > 0, allora T(n) = Θ(n^log_ba).
• Se f(n) = Θ(n^log_ba), allora T(n) = Θ(n^log_ba • log n).
• Se f(n) = Ω(n^log_ba+ε) per qualche costante ε > 0 e se a • T(n/b) ≤ c • f(n) per qualche costante c < 1 e per n sufficientemente grande, allora T(n) = Θ(f(n)).

Strutture dati

Una struttura dati è un'entità usata per organizzare un insieme di dati all'interno della memoria del computer, ed eventualmente per memorizzarli in una memoria di massa.

Array: struttura dati che contiene un numero finito di elementi, individuati in posizioni consecutive, ciascuna delle quali è associata a un indice numerico.