Algoritmi e strutture dati - Appunti completi

Introduzione agli algoritmi

Un algoritmo è una sequenza finita di passi interpretabili da un esecutore, che non deve essere necessariamente un computer. Nonostante la sequenza sia finita, non è detto che l'esecuzione richieda un tempo finito (l'esempio del ciclo for che potrebbe durare all'infinito se non gli diamo una condizione di uscita). L'algoritmo è a un livello di astrazione superiore rispetto ai linguaggi di programmazione, come ad esempio Java, C o Python, perché lo stesso algoritmo può essere implementato in ogni linguaggio. Il nome deriva da un matematico persiano, Al-Khwarizmi. L'algoritmo può essere applicato in ogni ambito della vita, si usava secoli fa e continua ad essere usato tutt'oggi. Una ricetta di cucina è un algoritmo, l'addizione e la moltiplicazione sono degli algoritmi, la ricerca su internet è un algoritmo ecc...

Tipi di algoritmi

• Numero di passi:
  • Sequenziali → un passo alla volta
  • Paralleli → più passi per volta, ma con più esecutori
• Risoluzione scelta
  • Deterministici → Scelte precise senza dubbi (if - else)
  • Probabilistici → Scelte davanti a insicurezze, casualità
  • Non deterministici → Non esistono nella pratica, scegliere contemporaneamente più opzioni per vedere la più conveniente

Problemi, algoritmi e correttezza

I → insieme delle istanze dei dati in input
S → insieme delle soluzioni
P → Problema
P I x S → Il problema è un sottoinsieme di ogni possibile input e di ogni soluzione ⊆

I problemi possono essere di:

• Dimensione (S = [0, 1]) → vero o falso, sì o no, 0 o 1
• Ricerca → trovare una generica soluzione per ogni dato di ingresso
• Ottimizzazione → trovare la soluzione ottima rispetto a un criterio prefissato, tipo un navigatore che ti sceglie la strada più veloce o più sicura

Il problema descrive il cosa (input), mentre l'algoritmo il come (da input ad output).

Correttezza → l'algoritmo è corretto se per ogni input, esso termina con una soluzione. L'algoritmo può anche essere parzialmente corretto, se non termina per ogni input ma solamente con qualcuno. Tutti gli algoritmi che sono corretti per un dato problema possono essere confrontati in base alle risorse computazionali, ovvero:

• Tempo di calcolo
• Spazio di memoria
• Banda trasmissiva

Strutture dati

La struttura dati è l'insieme di dati logicamente correlati tra di loro e opportunamente memorizzati, per i quali sono definiti degli operatori di costruzione, selezione e manipolazione. Ci sono 2 tipi di strutture dati:

• Statiche → non cambiano dimensione
  • Array
• Dinamiche → cambiano dimensione
  • Liste
  • Grafi
  • Alberi

Classi di problemi

I problemi si dividono in:

• Decidibili
  • Esiste un algoritmo che produce la corrispondente soluzione per ogni istanza dei dati in ingresso
• Indecidibili
  • Non esiste un algoritmo che produce la corrispondente soluzione per ogni istanza dei dati in ingresso

I problemi decidibili si classificano in base alla loro trattabilità, ovvero sulla possibilità di risolverli in modo efficiente.

Problemi trattabili e intrattabili

Un problema decidibile è:

• Intrinsecamente intrattabile se non è risolvibile in tempo polinomiale
• Non intrinsecamente intrattabile se è risolvibile in tempo polinomiale o esponenziale

P: problemi risolvibili in tempo polinomiale da un algoritmo deterministico (efficienti)
NP:

• Problemi risolvibili in tempo polinomiale da un algoritmo non deterministico (non efficienti perché richiedono infinite risorse computazionali)
• Problemi la cui soluzione può essere verificata in tempo polinomiale da un algoritmo deterministico

P è contenuto in NP → P ⊆ NP

Problema della soddisfacibilità (SAT)

Trovare la combinazione di variabili per cui l'espressione è vera:
(x' ∨ y ∨ z') ∧ (x ∨ y' ∨ z) ∧ (x ∨ y ∨ z) ∧ (x' ∨ z')

Con la tabella di verità si hanno 2 combinazioni tra cui scegliere (con la forza bruta poi), il che rende l'algoritmo in tempo esponenziale, quindi non efficiente. Non conosciamo algoritmi più efficienti, però possiamo verificare in modo efficiente se una data soluzione è corretta.

Riducibilità

Dati i problemi:

• P1 → (riducibile in tempo polinomiale) P2 (P1 <= P2)
  • P1 I1 = {0, 1}⊆
  • P2 I2 = {0, 1}⊆

Se esiste un algoritmo deterministico polinomiale che calcola una funzione f tale che:

• f : I1 → I2 tale che ∀i ∈ I1, ∀s ∈ {0, 1}, allora (i, s) ∈ P1 ⇔ (f(i), s) ∈ P2

La riducibilità in tempo polinomiale di P1 a P2 implica che la soluzione di ogni istanza di P1 può essere ottenuta risolvendo la corrispondente istanza di P2 calcolabile in tempo polinomiale. Il concetto di riducibilità ci permette di formalizzare la nozione: "è il problema B difficile almeno quanto il problema A?" Se A → B in tempo polinomiale allora B è difficile (dal punto di vista computazionale) almeno quanto A. Se A → (riducibile) B, allora:

• Se B ∈ P, allora A ∈ P
• Se A non può essere risolto in tempo polinomiale, nemmeno B può essere risolto in tempo polinomiale

Teorema di Cook

Ogni problema in NP è riducibile in tempo polinomiale al problema della soddisfacibilità (SAT). Se esiste un algoritmo che risolve SAT in tempo polinomiale, allora P = NP. Dal teorema di Cook segue che risolvere SAT è almeno tanto difficile che risolvere ogni altro problema in NP.

NP-completezza

Un problema in NP viene detto NP-completo (NPC) se SAT è riducibile ad esso in tempo polinomiale. Ogni problema in NPC è riducibile uno all'altro.

Complessità asintotica

Gli algoritmi che risolvono lo stesso problema decidibile vengono confrontati sulla base della loro efficienza, misurata attraverso il loro tempo d'esecuzione.

Tempo di esecuzione = T(n)
n = dimensione input
L'algoritmo deve essere indipendente da tecnologia, senza misurare:

• CPU
• Implementazione
• Compilatore
• Sistema operativo

Ogni algoritmo viene eseguito su un modello di calcolo, uno dei massimi esempi è il modello RAM di Von Neumann, che ha le seguenti proprietà:

• Compie operazioni elementari
  • Aritmetiche → addizione, moltiplicazione, elevamento a potenza ecc.
  • Di confronto → maggiore, minore, uguale
  • Logiche → and, or, not
  • Di trasferimento → trasferire e cambiare il valore di una variabile
  • Di controllo → cicli, while, do-while
• Queste operazioni hanno un costo uniforme, o meglio, ogni istruzione ha la stessa dimensione

Il tempo d'esecuzione di un algoritmo è dato dal numero di passi base compiuti durante l'esecuzione dell'algoritmo.

In C, un passo base è:

• Istruzione di assegnamento (non funzione)
  • x = 3;
  • x = funzione(a, b, c); → non è passo base
• Valutazione di un'espressione (non funzione)
  • x = (3 + a + b) * c;
  • x = (3 + funzione(a, b, c)) * 3 → non è passo base

Il tempo d'esecuzione di un algoritmo può essere calcolato in tre diversi casi:

• Pessimo
  • Input che massimizza T(n) → limite superiore
• Medio
  • Somma dei T(n) pesata per la probabilità di occorrenza
• Ottimo
  • Input che minimizza T(n) → limite inferiore

Complessità computazionale asintotica

Poiché il confronto degli algoritmi che risolvono lo stesso problema decidibile si riduce a confrontare delle funzioni, di solito si ragiona in termini di complessità computazionale asintotica. Le funzioni tempo d'esecuzione dei vari algoritmi che risolvono lo stesso problema decidibile vengono dunque confrontate considerando il loro andamento al crescere della dimensione n dei dati di ingresso.

Limiti asintotici e notazioni

Esistono diverse notazioni per esprimere le relazioni asintotiche tra funzioni, le più usate sono:

• O → limite asintotico superiore
  • g(n) = O(f(n)) ⇔ ∃c, ∀n ≥ n0, g(n) ≤ c * f(n)
  • g(n) cresce al più come f(n) per n → ∞
• Ω → limite asintotico inferiore
  • g(n) = Ω(f(n)) ⇔ ∃c, ∀n ≥ n0, g(n) ≥ c * f(n)
  • g(n) cresce almeno come f(n) per n → ∞
• Θ → limite asintotico stretto
  • g(n) = Θ(f(n)) ⇔ ∃c1, c2, ∀n ≥ n0, c1 * f(n) ≤ g(n) ≤ c2 * f(n)
  • g(n) cresce come f(n) per n → ∞

Classi di complessità asintotica degli algoritmi

Useremo il limite asintotico superiore.

• T(n) = O(1)
  • Complessità costante
• T(n) = O(log n)
  • Complessità logaritmica
• T(n) = O(n)
  • Complessità lineare
• T(n) = O(n · log n)
  • Complessità pseudolineare
• T(n) = O(n²)
  • Complessità quadratica
• T(n) = O(n³)
  • Complessità cubica
• T(n) = O(n^k), k > 0
  • Complessità polinomiale
• T(n) = O(kⁿ), k > 1
  • Complessità esponenziale
• T(n) = O(n!)
  • Complessità fattoriale

Esempio 2

Un algoritmo con complessità O(n³) viene eseguito su una CPU in grado di effettuare 100 milioni di istruzioni al secondo. Calcolare il tempo di esecuzione se l'input ha dimensione n = 10⁶.

• Calcolare il numero di istruzioni totali
  • num = n * T(n) → 10⁶ * n² → (10⁶)³ → 10¹⁸
• Calcolare il tempo di esecuzione
  • num / CPU → 10¹⁸ / 100.000.000 → 0,01 secondi

Calcolo della complessità di algoritmi non ricorsivi

Il tempo d'esecuzione di un algoritmo non ricorsivo può essere calcolato utilizzando le seguenti regole definite per induzione sulla struttura dell'algoritmo:

• Istruzione di assegnamento x = e;
  • T(n)
    • O(1) se priva di chiamate di funzioni
    • T'(n) + 1 = O(f'(n)) se con chiamate di funzioni
• Sequenza di s ≥ 2 istruzioni
  • T(n) = ∑_i=1^sO(max {f_i(n) | 1 ≤ i ≤ s}) → limite asintotico
• Istruzione di selezione if (β) S1 else S2
  • β → T₀(n) = O(f₀(n))
  • S1 → T₁(n) = O(f₁(n))
  • S2 → T₂(n) = O(f₂(n))
  • T(n) = T₀(n) + op (T₁(n), T₂(n))
  • O(max {f₀(n), op (f₁(n), f₂(n))})
  • op è max nel caso pessimo e min nel caso ottimo.
• Istruzione di ripetizione while (β) S
  • i(n) = O(f(n)) → Il numero di volte in cui viene eseguita S
  • β → T₁(n) = O(f₁(n))
  • S → T₂(n) = O(f₂(n))
  • T(n) = i(n) · (T₁(n) + T₂(n)) + T₁(n)
  • O (f(n) · max {f₁(n), f₂(n)})
  • Se T₁(n) o T₂(n) dipende anche dalla specifica iterazione j dove 1 ≤ j ≤ i(n) allora T(n) = ∑_j=1ⁱ⁽ⁿ⁾(T₁(n, j) + T₂(n, j)) + T₁(n, i(n) + 1)

Esempi

Il seguente algoritmo non ricorsivo per calcolare il fattoriale di n ≥ 1:

int calcola_fatt(int n) {
    int fatt, i;
    for (fatt = 1, i = 2; (i <= n); i++)
        fatt *= i;
    return(fatt);
}

T(n) = 1 + (n - 1) · (1 + 1 + 1) + 1 = 3 · n - 1 = O(n)

Il seguente algoritmo non ricorsivo per calcolare l'n-esimo numero di Fibonacci (n ≥ 1):

int calcola_fib(int n) {
    int fib, ultimo, penultimo, i;
    if ((n == 1) || (n == 2))
        fib = 1;
    else 
        for (ultimo = penultimo = 1, i = 3; (i <= n); i++) {
            fib = ultimo + penultimo;
            penultimo = ultimo;
            ultimo = fib;
        }
    return(fib);
}

Casoo pessimo (n ≥ 3): T(n) = 1 + 1 + (n - 2) · (1 + 1 + 1 + 1 + 1) + 1 = 5 · n - 7 = O(n)

Casoo ottimo (n ≤ 2): T(n) = 1 + 1 = 2 = O(1)

Il seguente algoritmo non ricorsivo per calcolare il massimo di un insieme di n ≥ 1 interi:

int calcola_max(int a[], int n) {
    int max, i;
    for (max = a[0], i = 1; (i < n); i++)
        if (a[i] > max)
            max = a[i];
    return(max);
}

Casoo pessimo (array ordinato rispetto a <): T(n) = 1 + (n - 1) · (1 + 1 + 1 + 1) + 1 = 4 · n - 2 = O(n)

Casoo ottimo (massimo contenuto in a[0]): T(n) = 1 + (n - 1) · (1 + 1 + 1) + 1 = 3 · n - 1 = O(n)

Calcolo della complessità di algoritmi ricorsivi

Il tempo d'esecuzione di un algoritmo ricorsivo non può essere definito in forma chiusa attraverso le regole viste in precedenza, ma in modo induttivo attraverso una relazione di ricorrenza le cui incognite costituiscono una successione di numeri interi positivi corrispondenti ai valori di T(n). Ci concentriamo su due tipi di relazioni di ricorrenza lineari: quelle di ordine costante e quelle di ordine non costante.

Una relazione di ricorrenza lineare, di ordine costante k, a coefficienti costanti e omogenea ha forma:

• x_n = a₁ · x_n-1 + a₂ · x_n-2 + ... + a_k · x_n-k per n ≥ k
• x_i = d per 0 ≤ i ≤ k - 1

Cioè l'n-esima incognita x_n è espressa come combinazione lineare (senza termine noto) delle k incognite che la precedono, a meno che non sia uno dei primi k elementi della successione. Ci sono due casi:

1. Se k = 1, la soluzione in forma chiusa è
   • x_n = d = O(1) se a₁ = 1
   • x_n = d · a₀ⁿ = O(a₁ⁿ) se a₁ > 1
2. Se k > 1, la relazione può essere risolta nel seguente modo. Assumiamo che esistano delle soluzioni in forma chiusa del tipo x_n = c · zⁿ con c ≠ 0 ≠ z._n Allora sostituendole nella prima equazione si ha
   • c · zⁿ · (z^k - ∑_i=1^ka_i · z^k-i) = 0
   • e quindi ∑_i=1^ka_i · z^k-i = 0 → Polinomio associato alla relazione di ricorrenza

Si può anche scrivere così: x_n = ∑_j=1^kc_j · z^jn → Esponenziale
x_n = O(max{z_j | 1 ≤ j ≤ k})

Una relazione di ricorrenza lineare, di ordine costante k, a coefficienti costanti e non omogenea ha forma:

• x_n = a₁ · x_n-1 + a₂ · x_n-2 + ... + a_k · x_n-k + h per n ≥ k
• x_i = d per 0 ≤ i ≤ k - 1

Per renderla omogenea, bisogna fare queste modifiche:

• y_n = x_n + (h / a - 1) = x_n - (h / a - 1)

Quindi x_n = O(y_n)

Ordine non costante, lavoro di ricombinazione

T(n) = a * T([ n / b]) + O(n^d) con

• a>0
• b>1
• d≥0

[ n / b] → approssimato intero superiore

Teorema dell'esperto

• T(n) = O(n^d) se d > log_ba
• T(n) = O(n^d log n) se d = log_ba
• T(n) = O(n^log_ba) se d < log_ba

Esempi

Algoritmo di Fibonacci ricorsivo

int calc_fib_ric (int n) {
    int fib;
    if (n == 1 || n == 2)
        fib = 1;
    else 
        fib = calc_fib_ric(n-1) + calc_fib_ric (n - 2);
    return (fib);
}

T(1) = 2
T(2) = 2
T(n) con n > 2 = 1 + T(n - 1) + T(n - 2) + 1
T(n - 1) + T(n - 2) + 2 → non omogenea, ma è lineare
y_n = x_n + 2
x_n = y_n - 2 → omogenea
Calcoliamo il T(n) con il polinomio associato alla relazione di ricorrenza:
z² - z - 1 = 0
x_n = (1/√5) · ((1 + √5)/2)ⁿ - (1/√5) · ((1 - √5)/2)ⁿ
T(n) = O(φⁿ)

Algoritmo per trovare il massimo tra due insiemi di numeri ricorsivo

int calc_max_ric (int a[], int sx, int dx) {
    int max, max1, max2;
    if (sx == dx)
        max = a[sx];
    else {
        max1 = calc_max_ric(a, sx, (sx + dx) / 2);
        max2 = calc_max_ric(a, (sx + dx) / 2 + 1, dx);
        if (max1 > max2)
            max = max1;
        else 
            max = max2;
    }
    return (max);
}

T(1) = 2
1 + T(n/2) + T(n/2) + 2 → 2T(n/2) + 5
T(n) = O(n)
Applichiamo il Teorema dell'esperto
a=2
b=2
d=0
log₂ 2T(n) = O(n)

Algoritmi per array

Array: definizioni di base e problemi classici

Un array è una struttura dati che contiene un insieme di elementi dello stesso tipo e la cui dimensione non varia durante l'esecuzione del programma. I suoi elementi sono memorizzati in modo consecutivo in memoria e possono essere individuati dalla loro posizione, che viene indicata dall'indice dell'elemento all'interno dell'array. L'indirizzo di ciascun elemento dell'array può essere calcolato sommando l'indirizzo del primo elemento dell'array con l'indice dell'elemento in questione. Grazie a questo, l'accesso a ciascun elemento dell'array è diretto e la complessità dell'operazione di lettura o modifica del valore di un elemento è costante.