Dati e Algoritmi 1 - appunti essenziali ed esercizi

Introduzione al corso

• Cos'è un algoritmo?

  È un metodo risolutivo di un problema attraverso una sequenza finita di passi. Risolve problemi computazionali che prevedono dato un certo input di produrre un certo output.

• Differenza tra un algoritmo e un programma?

  L'algoritmo sta alla base di un programma e ne cattura l'idea essenziale che c'è nella risoluzione ed è un distillato del programma (codice).

• Cos'è una struttura dati e perché le strutture dati sono importanti per gli algoritmi?

  È un'organizzazione logica dei dati. Un algoritmo, che deve risolvere un problema ha bisogno che i dati siano organizzati in una certa maniera. La scelta di questa organizzazione è fondamentale per la qualità dell'algoritmo (Es. vettore di interi e ricerca di un valore, conviene che il vettore sia ordinato così da poter fare ricerca binaria).

• Quali caratteristiche deve avere un buon algoritmo?

  Svolgere il suo compito ed essere efficiente e parsimonioso nell'uso delle risorse computazionali.

• Cosa rende difficile il progetto di algoritmi buoni?

  Per risolvere un problema esiste sempre un algoritmo banale, che spesso non è l'algoritmo migliore.

• Perché è importante studiare algoritmi e strutture dati?

  Un ingegnere è spesso chiamato a dover risolvere computazionalmente un problema con alta probabilità di dover realizzare una soluzione ad hoc.

Complessità in Tempo

Dire che InsertionSort è O(n²), data un'istanza di taglia n, l'algoritmo risolve il problema in al più n² operazioni elementari.

Se le operazioni che consideriamo sono davvero elementari possiamo considerare l'esecuzione di queste operazioni come un'unità di tempo.

In realtà una moltiplicazione costa più di una somma e un accesso in memoria costa più di un accesso in memoria cache.

Approssimando a meno di costanti possiamo considerare le operazioni elementari come un'unità di misura del tempo.

Con questa approssimazione il numero di operazioni elementari è una buona approssimazione del tempo di esecuzione.

Riepilogo:

La complessità in tempo dev'essere una stima del tempo di esecuzione. Non possiamo misurare il tempo di esecuzione per vari problemi (vedi slides). La nostra stima è il numero di operazioni elementari che l'algoritmo esegue per risolvere un'istanza. Le istanze le raggruppiamo in funzione della taglia e per ogni taglia consideriamo l'istanza peggiore.

Consideriamo quindi il massimo numero di operazioni fatte dall'algoritmo per risolvere quella data istanza.

Questa è la complessità al caso pessimo dell'algoritmo.

Trovare il numero max di operazioni fatte dall'algoritmo per un'istanza di taglia n non è facile perché è difficile determinare l'istanza peggiore e fare un conteggio esatto delle operazioni è complicato → analisi asintotica.

complessità polinomiale → algoritmo buono

complessità esponenziale → algoritmo non buono

GIUSTIFICAZIONE

supponiamo che la complessità esprima un tempo in nS. Dato un budget di tempo τ, qual è la massima taglia di un’istanza risolvibile in tale tempo?

• Esempio:

  • complessità logaritmica: log₂(n₂) = τ ⇔ n₂ = 2^τ

    la taglia dell’istanza risolvibile in tempo τ da un algoritmo con complessità log

  • complessità esponenziale: 2^n₂ = τ ⇔ (n₂) = log₂(τ)

    la taglia dell’istanza risolvibile in tempo τ da un algoritmo con complessità esp.

Esercizio slide 77

A matrice n×n, scendendo di riga in riga il numero di uni può solo aumentare.

Contare quanti uni ci sono nella matrice.

Algoritmo Count(A)

input: matrice A n×n binaria con caratteristiche descritte sopra

output: #1 in A

riga i ← 0, j ← 0, count ← 0

colonna while (i < n) {

• if (j < n) && (A[i, j] = 1) then j ← j + 1
• else { count ← count + j; i ← i + 1 }

}

return count;

Esercizio slide 86

T(n) =

• 1 se n=0,1
• 2T(⌊n/2⌋) + 3n se n>1

BASE n=0,1

T(0) = 6 ⋅ 0

T(1) = 6 ⋅ 1

T₀ = 0 ≤ 6 ⋅ 0

T₁ = 1 ≤ 6 ⋅ 1

dalla relazione di ricorrenza

PASSO

Fisso n≥1 e Hp. Induttiva T(m) ≤ 6m os ≤ m ≤ n

T(n+1) = 2T(⌊(n+1)/2⌋) + 3(n+1)

≤ 2 ⋅ 6 ⌊n+1/2⌋ + 3(n+1)

≤ 2 ⋅ 6 ⋅ n+1/2 + 3(n+1) = 6(n+1) □

Tolgo le parti basse perché sto maggiorando

Algoritmi ricorsivi:

• Specifica
• Complessità
  • esprimere la compless tramite una relazione di ricorrenza
  • dimostrare per induzione una qualche affermazione relativa alla complessità usando la relazione di ricorrenza.

Analisi della complessità

Considerando una generica iterazione, se abbiamo trovato una corrispondenza oppure no (se J>0 per esempio), i può solo aumentare (nel senso che non viene mai decrementato).

Se invece non ho trovato corrispondenza e J≠0, i non va avanti e J→0.

Se J→0, nell'iterazione successiva i aumenterà per forza. i sta fermo al max una iterazione e quindi aumenta almeno ogni due.

Quante iterazioni fa il while? Al più n.

Quindi dopo max 2n operazioni l'algoritmo si conclude.

La complessità perciò è proporzionale a n (iterazioni del while, all'interno del quale si fanno un numero costante di operazioni).

Analisi della correttezza

Complessità

• Calcolo f Θ(m)
• altre operazioni: Θ(n)

⇒ Θ(n+m)

Correttezza

Invariante:

i, j

• P[0...j-1] = T[i-j...i-1]
• P non è sottostringa del resto a partire da un indice <i-j
• (R, q) = lunghezza e inizio del più lungo prefisso di P in T[0...i-1]

Esercizio. Slide 25

HeightSum(T,v)

input: nodo v∈T

output: somma di tutte le altezze dei nodi nel sottoalbero Tv, in più, l'altezza del nodo(v)

if(T.isExternal(v)) then return (0,0)

• (sumL, heightL) ← heightSum(T, T.left(v))
• (sumR, heightR) ← heightSum(T, T.right(v))
• h ← max { hL, hR } + 1
• δ ← SL + SR + h visita
• return (δ,h)

Algoritmo maxImbalance(T,v)

input: v ∈ T

output: imbalance(T_v), in più, numero di Foglie in T_v

if(T.isBternal(v)) then return (0,1); // caso base

(b_l, m_l) ← maxImbalance (T, T.left(v))

(b_r, m_r) ← maxImbalance (T, T.right(v))

b ← max { b_l , b_r , | m_l - m_r | }

m ← m_l + m_r

return (b, m);

Complessità:

lineare rispetto al numero di nodi sul quale viene invocato l'algoritmo. Quindi Θ(n)

Complessità

|a| ≤ 2m => O(m²log(m))

• Dire cosa contengono S e Q alla fine della i-esima iterazione del For.
• S contiene le entry di P con chiave più piccola
• Q = … righe di S in P che non sono in S