Dati e Algoritmi I - Teoria per esame

ABSTRACT DATA TYPE

Modello che specifica tipo di dati, operazioni, accessibilità/parametri in stato realizzato per ogni tramite interfaccie che contengono solo dichiarazioni di osserva e metodi

ALBERI GENERALI

DEFINIZIONE DI ALBERO RADICATO / ANTENATI / DISCENDENTI

NODI ESSENI / ALBERO ORDINATO

height (T) = max_{v∈T,v foglia} (depth (v))

procedura per inclusione

piano basso T ≡ r → banale

passo annotazione vale ≅ albero con 1 ≤ m ≤ n nodi

procedura su albero con n+1 nodi

height (T) = 1 + max_i (height (T_i))

height (T) = max_{v∈T,v foglia} (depth (v))

height (T_i) = 1 + max_{v∈Ti,v foglia} (depth (v))

= max_i (1 + max_{v∈Ti foglia} (depth (v)))

= max

(✓/✓✓✓) completezza di depth

if T is root r 0

else rek T.root depth (T.pout)

Θ(d(v+1)) ~ Θ(n)

Complessità di Height

h = 0

for v∈T.children prendendo h ← max {h, height(T_iv)}

costo accaduto ad ogni nodo Θ(c_u+1) C_u = # figli di u

Σ c_u = n-1 (ogni nodo, eccetto la radice, ha un padre e contribuisce una volta alla somma)

Visite Preorder / Postorder

Visita v

foreach w∈T.children(u)

preorder T_w

Alberi Binari

Alberi Binari: Propri/Pieni

• n = # nodi
• m = # foglie
• m = n - m + 1
• h + 1 ≤ m ≤ 2^h

Visita Inorder

if (T.left ≠ null) then inorder T.left (w)

visita v

if (T.right (v) = null) then inorder T.right

ORDINAMENTO

• INSERTIONSORT
• QUICKSORT
• HEAPSORT
• BUCKETSORT
• RADIXSORT

DESIGN PATTERN DIVIDE / CONQUER / COMBINE

MERGESORT

if n < 2 then return S S₁, S₂ ← sequenze vuote for i = 1 to ⌊n/2⌋ do S₁[i] ← S[i] for i = ⌊n/2⌋ to n do S₂[i - ⌈n/2⌉] ← S[i] Mergesort(S₁) Mergesort(S₂) Merge(S₁, S₂) return S

int k, i, j ← 0 while (i < S₁.size && j < S₂.size) if S₁[i] <= S₂[j] then S[k++] ← S₁[i++] else S[k++] ← S₂[j++]

GUARDIAMO ADESSO L'ANALISI DI k-SORT PARTIAMO DALLA COMPLESSITÀ DI MERGE con n = |S₁| + |S₂| Complessità data dall'input ciascuna operazione è Θ(1) e esegue una due cod |S₁| + |S₂| operazioni da una cod → Θ(n)

Lower Bound per Algoritmi

Basati su Confronti

Per istanze di taglia n, un algoritmo di ordinamento A basato su confronti esegue Θ(n log n) confronti al caso pessimo.Tale lower bound vale anche per confronti “n” alta probabilità o in media nel caso A sia probabilistico

A algoritmo deterministico basato os confronti I_n = {permutazioni di 1, ..., n}, ed |I_n| = n!

• I confronti eseguiti da A sulle istanze Se In possono essere rappresentate tramite un decision tree
  • radice = primo confronto fatto da A
  • nodo interno = confronto S[i], S[j] e i possibili 3 archi uscenti S[i] < S[j] o S[i] = S[j] o S[i] < S[j] rappresentano il prossimo confronto fatto da A
• Ogni istanza Se In segue un percorso radice foglio distinto in T[In].Se non fosse distinto esisterebbero S1, S2, ∈ In, S1 ≠ S2, che non verrebbero distinte da A [avendone come medesimo percorso] => una delle due non sarebbe ordinata correttamente

Segue che T[In] albero binario proprio con n! foglie L’altezza ⎣⎡(n log n)

1. S pcu esegua ⎣⎡(bgn!) = Θ(n log n) confronti

Al caso medio la complessità è O(1 + λ)

Tabella hash con separate chaining e load factor λ

E vale sia per ricerca con successo/senza successo

Si suggerisce λ < 0,9 — In Java λ = 0,75

Rehashing Creare un nuovo bucket array

Scelta di una nuova funzione hash (comp. funct)

Trasferimento di entry

• Facile
• Buone prest al caso medio
• Non richiede universo ordinato delle chiavi
• di calcolo penultima complementare.
• dipende dalla f. hash
• Spreco di spazio per avere un load factor basso

Remove

Rimuovo solo entry di nodi ad altezza 3. Se la entry è ad altezza > 1

la sostituisco con una entry ad h = 2 e poi rimuovo. Gestisco underflow,

facendo eventualmente diminuire h di 1.

w ⟵ MWTreesucc(t, T.root, u)

If (T_u is External(w)) then return null //foglia

else

• trova e to e.getKey(e') = k
  • y ⟵ e.getValue( )
  • If (altezza (w) = 1) then Delete (e, w, R) //altezza ok
  • else
  • Sia v il figlio di w a sx di e
  • w' ⟵ ultimo nodo nella vista prendete T_v
  • e' ⟵ entry con chiave max m Z
  • metti una copia di e' nel posto di e in MWT
  • L ⟵ Delete (e', z, R)

decremento di z il # of entry in T

return y

Delete (e, y, α)

INPUT: entry e nel nodo v, t.c il figlio a sx (α=L) o a dx (α=R) è cancellabile

OUTPUT: rimozione di e ripristinando le proprietà dei (2-4) tree

Siano A; 2 I figli di v discriminata e con 2 figlio cancellabile

Immetti e e 2

If (u non ha più entry) //underflow

L esegu uno dei casi successivi

DEPTH FIRST SEARCH

DFS

VISITA TUTTI GLI ARCHI E I VERTICI DELLA COMPONENTE CONNESSAE ALLA FINE LI ETICHETTA TUTTI

VISITA IL VERTICE v_j; v: ID ← v_j

for all e ∈ G.incidentEdges(v) do   if (e.label = null)      w ← G.opposite(v,e)      if (w.ID = ∞)      e.label ← DISCOVERY EDGE      DFS(G,w)   else e.label ← BACK EDGE

ANALISI

Supponendo che all'inizio nessuno dei vertici sia statovisitato o etichettato così come nessuno degli archi. Alloraal lume esecuzione- Ho visitato e etichettato tutta la componente connessa- I discovery edge formano uno spanning tree della componente connessa

1. Osserviamo che se tutti i vertici sono visitati allora tutti gli archisono stati etichettati. Per assurdo, supponiamo ci sia un vertice v ∈ C_snon visitato alla fine di DFS(G,v₀) → non ho mai invocato la DFSsu v. Dato che v ∈ C_s esiste un cammino da S a vS = v₀ − v₁ − ... − v_k − vDove v₀ visitato e v non visitato. Sia v_i il primo vertice in camminoche non è visitato. Deve esistere e = (v_j,v_i). Questo vuol dire v_i → non è ¬ visitato e quindi ho invocato DFS(G,v_i) ↔ e nel procedimentol'arco (v_j,v_i) e e.label = null e v_i = ∞ → devo invocare DFS(G,v_i)e visitare v_i

1. Algoritmo SSSP

Algoritmo: ShortestPath(G, s)Input: grafo G = (G, V, w) con pesi non negativi e sorgente s ∈ VOutput: distanze e i cammini minimi da s ∀v ∈ V tramite v.D e v.parent

s.D ← 0; s.parent ← null;forall v ∈ V/{s} do    v.D ← +∞    v.parent ← nullQ ← Priority queue con tutti i vertici v ∈ V (chiave v.D)while (¬Q.isEmpty()) do    u ← Q.removeMin()    forall ((u, v) ∈ E e v ∈ Q) do        if(u.D + w(u, v) < v.D) then            v.D ← u.D + w(u,v)            v.parent ← u        Aggiorno Q in base al cambiamento di v.D

Osserviamo che l'algoritmo esegue per ogni arco di ciascun vertice che visitala cosidetta edge relaxation che si compone del seguente pseudocodiceif(u.D + w(u,v) < v.D) then    v.D = u.D + w(u,v)    v.parent = uche ha il compito di aggiornare le distanza qualora trovi un percorso condistanza minore.

2. Correttezza

Lemma 1. Alla fine di ciascuna iterazione del ciclo while di ShortestPath(G, s)per ogni v ∈ V si ha che

• Se v.D = +∞ allora v.parent = null
• Se v.D < +∞ allora il cammino ottenuto risalendo da v di parent inparent è un cammino da sa vdi lunghezza v.D

Proof. La proprietà vale all'inizio del ciclo. Infatti

• v.D = +∞ ∀v ∈ V/{s} e s.D = 0
• v.parent = null ∀v ∈ V/{s}

ed è immediato vedere che le edge relaxation mantengono questa proprietàinvariata. Infatto se v.parent ≠ null vuol dire che il vertice v è stato scoperto,pertanto ha un padre tramite cui posso risalire in se la sua distanza da assaràminore di +∞