Algoritmi e Strutture Dati con domande riassuntive

Algoritmi

1.1: Algoritmi

• Algoritmo: sequenza di istruzioni elementari che portano alla soluzione di problemi computazionali.
• Problema computazionale: fornire parametri che descrivano input e output.
  • Input: un array di interi.
  • Output: un numero intero.
  • Vincoli: descrivono il legame fra input e output.
  • Istanza: si ottiene specificando i valori nell’input -> esempi di input (gli input sono diversi se contengono diversi valori).
• Esercizio: ordinare array.
  • Input: array di n interi.
  • Output: un array (può essere anche uno diverso) di n interi.
  • Vincoli: L’array di output è la permutazione dell’array di input tale che: primo elemento <= secondo elemento <= terzo elemento ecc.
  • Istanza: 10 7 9 3 4 74 3.
• T_(n): Caso peggiore, ossia l’algoritmo più lento nell’effettuare l’operazione p.
• T_(n): Caso migliore, ossia l’algoritmo più veloce nell’effettuare l’operazione m.
• T_(n): Caso medio, ossia “tempo dell’esecuzione previsto” (linea sopra la M piccola).

Elementi utilizzati per gli algoritmi

• Pseudocodice simil Java - C.
• If / else / then (poco usato).
• Commenti */ /*.
• Assegnamenti x <- 1 / x = 1 / x:= 1.
• Test x == 1.
• Variabili locali a meno dei vettori.
• Array V[i] 1...n (si parte da 1, non da 0).
• Puntatori.
• Passaggio di parametri (per valore).
• Macchina su cui si eseguono gli algoritmi è la RAM (Random Access Machine).
• Esempio: 6.
  • Algoritmo elabora 10 op./sec.
  • Dimensioni dell’input: n.
  • T(n) ? p.

Tempo alg. n 20 100 10000 1000n 0.02” 0.1” 1” 10n (1/100)*0.02” 100” 1/100” 2 100n 0.04” 10” 2’ n 6² 1” 3*10 anni 1000000n 20” 1000”.

Esercizio: Ricerca sequenziale

Ricerca Sequenziale (trovare valore K nel vettore V).

• Input: vettore V, valore K.
• ricercaSequenziale(V,K).
• i = 1.
• while(i < V.length && V[i] == K).
• i++;
• if (i <= length(V).
• return(i).
• else.
• return(-1).

Calcolo tempo dell’esecuzione

• Caso migliore: K è in V[1] (array vanno da 1 a n). t_wi = 1.
• Caso peggiore: K non c’è in V.
• Caso medio: K si trova in V[n/2].
• Tempo: C1 + C2 * t_wi + C3 * t_wi -1 + C4 + C5 * t_if + C6 * t_if.
• T_mig(n): C1 + C2 * 1 + C3 * 0 + C4 + C5 * 1 + C6 * 0.
• T_p(n): C1 + C2 * (n + 1) + C3 * n + C4 + C5 * 0 + C6 * 1.
• T_M(n): C1 + C2 * ((n + 1)/2) + C3 * (n/2) + C4 + C5 * 1 + C6 * 0.

Esercizio: Ricerca dicotomica

Ricerca Dicotomica (per trovare valore K nel vettore V provo a vedere se si trova a metà. Il programma mi dirà in quale metà si trova e si opererà su essa e così via).

• Input: vettore V, valore K.
• ricercaDicotomica(V[],K).
• sx = 1.
• dx = length(V);
• m = (sx + dx)/2;
• while (V[m]!=k && dx >= sx) {
• if V[m] > k {
• dx = m - 1.
• else sx = m + 1 }
• m = (sx + dx)/2 }
• if sx <= dx.
• return(m).
• else return(-1).

Calcolo tempo dell’esecuzione

• Caso migliore: K è in posizione m. t_wi = 1 V[m] = k.
• Caso peggiore: K non c’è in V. t_wi = max. t_if + f_if = t_wi -1.
• Caso medio: ciclo while 1 passo n, 2 passi n/2, 3 passi n/3, i - passi n/2ⁱ, n/2ⁱ = 1, 2ⁱ = n, i = log₂ n -> max = log₂ n.
• Tempo: C1 + C2 + C3 + C4 t_wi + C5(t_wi -1) + C6 t_if + C7 f_if + C8(t_wi -1) + C9 + C10 t_if2 + C11 f_if2.
• T_mig(n): C1 + C2 + C3 + C4 + C9 + C10. 6 istruzioni.
• T_p(n): C1 + C2 + C3 + C4 * max + C5 * max + C6 (max - 1) + C8 (max - 1) + C9 + C11.
• T_M(n): (log₂ n)/2.

Algoritmi di ordinamento

Selection sort

• Cerca minimo e lo mette in 1.
• Riparte da 2 -> cerca minimo -> mette in 2.
• Ecc.
• sel_sort(V[]).
• for i = 1 to length V[] - 1.
• pmin = 1.
• for j = i + 1 to n.
• if V[j] < V[pmin].
• pmin = j.
• Scambia (V, i, pmin) 3 istruzioni.

• Caso migliore: Array già ordinato. t_if = 0.
• Caso peggiore: Array ordinato al contrario. t_if = max.
• Tempo: (C1 + C2 + 3C6)n + (C3 + C4)(∑ i) + C5 t_if, i=1, n-2.
• T_mig(n): (C1 + C2 + 3C6)n + (C3 + C4)(∑ i), i=1, n-2.
• T_p(n): (C1 + C2 + 3C6)n + (C3 + C4 + C5)(∑ i), i=1.

Insertion sort

• Array diviso in due: ordinati e non ordinati.
• Si prendono gli elementi non ordinati e si inseriscono nella apposita posizione.
• void ins_sort(V[]).
• for i = 2 to n.
• k = V[i]; j = i -1;
• while k < V[j] and j > 0.
• V[j + 1] = V[j].
• j--;
• V[j+1] = k.

• Caso migliore: Array già ordinato. t_wi = 1 + 1 + 1.. = n -1.
• Caso peggiore: Array ordinato in modo decrescente. t_wi = i.
• Tempo: C1n + (C21 + C22 + C6)(n - 1) + C3(∑ t_wi) + (C4 + C5)(∑ t_wi -1), i=2, n.
• T_mig(n): C1n + (C21 + C22 + C6)(n - 1) + C3(n-1) -> asintotico a n.
• T_p(n): C1n + (C21 + C22 + C6)(n - 1) + C3(∑ i) + (C4 + C5)(∑ i - 1), i=2, n.
• ∑ i = n(n +1)/2 -1, i=2, n.
• ∑ i - 1 = 2 + 3 + 4 +...(n-1) = ∑ i -2, i=2.
• Il tempo peggiore è asintotico a n².
• Tempo medio = n²/2.

Limiti asintotici

Si eliminano le costanti e i termini di ordine inferiore.

• O(f(n)) = limite asintotico superiore (O grande).
• Ω(f(n)) = limite asintotico inferiore (Omega grande).
• Θ(f(n)) = limite asintoticamente stretto (Theta).

O grande - limite asintoticamente superiore (caso peggiore)

• t(n) = O(f(n)) se esiste n₀, c | ∀n > n₀, t(n) < c*f(n).
• Esempio: 3n² = O(2n²).
• c = 2, n₀ = 10.
• 3n² <= (2n)² -> 3x² 1 <= 2x² 2 1 -> 3 <= 4.

Omega grande - limite asintoticamente inferiore (caso migliore)

• t(n) = Ω(f(n)) se esiste n₀, c > 0 | ∀n > n₀, t(n) > c*f(n).
• Esempio: 3n² = Ω(n²).
• c = 2, n₀ = 10.
• 3x² 1 >= 2x² 1 -> 3 >= 2.

Theta - limite asintoticamente stretto

• t(n) = Θ(g(n)) se e solo se t(n) = O(f(n)) e t(n) = Ω(g(n)).
• Θ(g(n)) = {f(n) : esistono costanti positive c₁, c₂ e n₀ tali che 0 < c₁g(n) < c₂g(n) per ogni n > n₀}.
• Una funziona f(n) appartiene all’insieme Θ(g(n)) se esistono costanti positive c₁, c₂ tali che f(n) possa essere compresa tra le due costanti, per un valore sufficientemente grande di n.
• In sostanza theta esiste se e solo se O grande e Omega grande sono uguali.
• Nel grafico, se dopo n₀ f(n) coincide e sta sotto a c₁g(n) e coincide o sta sopra a c₂g(n), allora si dice che g(n) è un limite asintoticamente stretto per f(n).
• f(n) deve essere non negativa quando n è sufficientemente grande (ovvero nessun membro di f(n) appartenente a Θ(g(n)) deve essere asintoticamente non negativo).

Algoritmo

V₁ e V₂ sono due array contenenti n valori. Contare quanti elementi di V₂ stanno in V₁.

• c = 0.
• for i = 1 to V₂ length.
• j = 1.
• while(V₂[i] != V₁[j]) and (j < V₂ length).
• j++.
• if j < V₁ length.
• c++.
• return c.

• Tempo → C₂ + C₃ · n + C₂ · ∑ t_wi + C · t_if, i=1, n.
• Caso peggiore: non ci sono elementi di V₂ in V₁.
  • t_wi = n; t_if = 0.
  • t_p(n) = C₂ + C₃ · n + C₂ · ∑ n ~ C₂ + C₃ · n + C₂ · n² ~ O(n²).
• Caso migliore: V₂ ha un solo numero ripetuto n volte e quel numero è al primo posto di V₁.
  • t_wi = 0; t_if = n.
  • t_m(n) = C₂ + C₃ · n + C · n ~ Ω(n).
• N.B: O e Ω sono diversi, quindi non esiste.

Limiti asintotici

• 3n² -> O(n²) -> o(n²).
• 3n² -> Ω(n²) -> w(n²).
• 4n² − 2n -> O(n²) -> o(n²).
• 4n² − 2n -> Ω(n²) -> w(n²).
• Esiste una costante che, dopo un certo n₀, moltiplicata per n² sia più piccola di 4n² − 2n.
• n = 10, c = 1, 4(10²) − 2(10) = 380, Ω(n²) = 1/100.
• log n -> O(n) sarebbe meglio nlogn o n -> O((log n)) -> O(n).
• log n -> Ω(logn) -> w(1).
• k log n -> O(nlogn), log n, k log n -> k è costante quindi va via.
• max{f(n); g(n)}.
  • f(n) = 2n.
  • g(n) = 3n.
  • Considero la più grande quindi f(n).
  • f(n) = 2n² + 3 -> O(n²).
  • f(n) = 2n² + 3 -> Ω(n²).
• N.B: b(n + a)^b, a,b sono costanti! O(n^b).
• Esempio: (n + 10)⁷ O(n⁷). NON risolvere tanto tutte le n con esponente minore di 7 vanno via! (n + 10)⁷.

Algoritmo

2 array contenenti n bit da sommare in un terzo array di dimensioni n + 1.

Esempio: A 10110 + B 10100 = C 101010.

• void Somma (A[], B[]).
• resto = 0.
• for i = n down to 1.
• C[i+1] = A[i] + B[i] + resto.
• if C[i+1] < 1.
• resto = 0.
• else.
• C[i+1] = C[i+1] - 2.
• resto = 1.
• C[i] = resto.

• Tempo C₂ + C₃ · n + C t_if + C f_if.
• Caso peggiore: 0101 ultimo bit di A e B = 1 e poi A[i] o B[i] = 1 1011, c’è sempre riporto.
  • t_if = 0; f_if = n.
  • t_p(n) = C₂ + C₃n + C₂n = C₂ + C₅n = O(n).
• Caso migliore: non si ha mai riporto.
  • A[i] and B[i] = 0.
  • t_if = n; f_if = 0.
  • t_m(n) = C₂ + C₃n + Cn + 0 = C₂ + C₄n = Ω(n).
• Siccome nel caso migliore è Ω(n) e nel peggiore l’algoritmo è O(n), l’algoritmo è Θ(n).
• Tempo medio: C₂ + C₄n + C₂.

Algoritmo

Trasformare numero da decimale a binario.

• z = n.
• t = 0.
• while z > 0.
• x = z mod 2.
• z = z div 2.
• if x == 0 then.
• for i = 1 to n.
• t = t + 1.
• return t.

• Tempo C₃ + C₄ · t_wi + Cn · t_if.
• Caso peggiore: n = potenza di 2 = 2^h -> h = log₂(n).
  • t_wi = h; t_if = h.
  • t_p(n) = C₂ + Cn log₂(n).
  • = O(n log n).
• Caso migliore: n - 1 = 2^h.
  • t_wi = h; t_if = 0.
  • t_m(n) = C₃ + C₄ · logn.
  • Ω = O(logn).

Algoritmo

• for i = 1 to n.
• b[i] = 0.
• j = n.
• while j > i.
• b[i] = b[i] + a[j].
• j--.

• Non c’è caso migliore o peggiore perché sono due for e devono essere eseguiti per forza.
• t(n) = 3C_n + 3 · C ∑ n − i = 3C_n + 3 · C ∑ i = 3C_n + 3C n(n−1)/2 = Θ(n²).

Algoritmo con cicli For innestati

• for i = 1 to n.
• for j = 1 to n.
• for k = 1 to j - 1.
• A[k] = B[j].

• 3 for innestati = n³.
• Non è mai maggiore di n³.
• Può essere minore di se il for più interno viene eseguito poche volte.
• Non c’è caso migliore o peggiore perché devono essere eseguiti tutti almeno una volta.
• Tempo n n (n)(n−1)n.
• t(n) = C n² + C n² + 2 · Cn ∑ j − 1 = C n² + C n² + 2 · Cn ∑ j = C n² + C n² + 2 · Cn n(n−1)/2 = Θ(n³).

Sommatorie cicli innestati

∑_i=1ⁿ⁻¹ i(i+1) − n(n+1)/2 = 2/2.

∑_i=1ⁿ⁻¹ (n−1) · i(i+1) − n(n+1)/2 = 2/2.

∑_i=1ⁿ⁻¹ (n−1) · i(i + 1) − n(n+1)/2 = 1/2.

∑_i=1ⁿ⁻¹ (n−1) · 2i + i − n(n+1)/2 = 1/2.

∑_i=1ⁿ⁻¹ (n−1) · 2i + i − n(n+1)/2 = 1/2.

∑_i=1ⁿ⁻¹ (n−1) · 2i + ∑_i=1ⁿ⁻¹ i − n(n+1)/2 = 1/2.

∑_i=1ⁿ⁻¹ (n−1) · 2i + ∑ i − n(n+1)/2 = n(n+1)(2n+1)/6.

n(n+1)/2 − n(n+1)(2n+1)/6 + n(n−1)(n−1)/2.

Ordine massimo quindi n³, in questo caso non c’è caso migliore o un caso peggiore Θ(n³) perché in ogni caso i 3 for vengono eseguiti.

Principio di induzione & Ricorsione

• La ricorsione è basata sul principio di induzione matematica.
  • Proprietà p(n).
  • 1. p(n) vera ∀n ≥ n₀.
    • a. p(n₀) vera.
    • b. p(n) implica p(n+1) vera.
  • 2. n₀ < m < n-1 p(m) implica p(n).
• L’induzione si basa sull’