Dati e Algoritmi I - Teoria per esame

ABSTRACT DATA TYPE

Modello che specifica tipi di dati, operazioni, accessibilità, parametri in Java realizzato perciò più tramite interfacce che con classi. Sono dichiarazioni di operazioni e protocolli.

ALBERI GENERALI

Definizione di albero radicato / antenati / discendenti nodi esterni / albero ordinato

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

Procedura per induzioneCaso base T = r → banalePasso induttivo vale ∀ alberi con 1 ≤ m ≤ n nodi.Prendiamo un albero con n+1 nodi.

• height(Γi) = max_{v∈T, v foglia} (depth(v_i))
• height(Γ) = 1 + max_i max_{v∈Ti, v foglia} (depth(v)) = ^{max_{v∈Ti, v foglia}}

Completes a di depthIf T is root else depth(T.root)Θ(dv+1) ~ Θ(n)

ABSTRACT DATA TYPE

Modello che specifica tipo di dati, operazioni, accessibilità, parametri.In java realizzato perciò più tramite interfacce che con classi.Sono dichiarazioni di osserva e regola.

ALBERI GENERALI

Definizione di albero binario / antenati / discendentiNodi esterni / albero ordinato

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

Procedura per induzioneCaso base T=r → banalePasso induttivo vale per alberi con 1 ≤ m ≤ n nodiProviamo su albero con n+1 nodi

height(τ_i) = 1 + max(... height(τ_i))

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

height(τ_i) = 1 + max_{v∈T, v figlia} depth(v)

= max (1 + max_{v∈T, v figlia} depth(v))

Quello lui maxSo tutte le foglie

IIII complessità di depth

If T is root etc.else return 1 + depth(T.par)Θ(dw+1) ~ Θ(n)

Complessità di height

h = 0

for v ∈ T.children prerrendo h = max {h, height(T_w)}

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

∑_v∈Tu c_v = n-1 (ogni nodo, eccetto la radice, ha un padre e contribuisce una volta alla sua)

Visite preorder/postorder

visita v

foreach w ∈ T.children(v)

preorder T_w

Alberi Binari

Alberi binari propri/pieni

Propietà

Visita inorder

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

visita v

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

Priority Queue

Collezione di entry in cui le chiavi rappresentano la priorità e provengono da un universo totalmente ordinato

Entry = (chiave valore)

Liste

• Insert Θ(1)
• RemoveMin Θ(n)
• Min Θ(n)

Lista non ord | Lista ord

• Insert Θ(n)
• Min Θ(1)
• RemoveMin Θ(1)

Heap

Albero binario (completo e bilanciato) che al livello i ha 2ⁱ nodi (al massimo) e nell'ultimo livello tutti i nodi interni hanno 2 foglie tranne questo più a dx che può avere solo il figlio dx

Un albero binario completo con n nodi ha altezza h=⌊log₂n⌋

Definizione Min Heap

∀i, min≤{e₁,e₂,e₃}

la chiave massima sta in una foglia dato che il nodo ogni alberico ha chiave maggiore

Level Numbering

Rappresentato tramite array/radice in P[1]

Figli sono P[2i],P[2i+1] | genitore P[⌊i/2⌋]

Struttura dati implicita

RemoveMin/Insert Θ(logn)

Costruzione di uno heap a partire da n entry date

1. Approccio Top/Down

Parto dal primo e vado fino all'ultimo facendo un up-heap/bubbling

Θ (∑_j=2ⁿ log j) Demonstriamo Θ(n log n)

∑_j=1ⁿ log j ≤ ∑_j=1ⁿ log j ≤ n log n

Istanza cattiva, ordine decrescente

2. Approccio Bottom-Up

Eseguo ⌊n/2⌋ iterazioni

P[⌊n/2^k⌋ nodo più piccolo più a dx dell’ultimo livello

Ad ogni iterazione faccio un down-heap/bubbling

Per ogni nodo a livello i: 0 ≤ i ≤ h-1 il down-heap bubbling costa O(h-i) e ho 2ⁱ nodi al livello i.

Θ (n + ∑_j=1^⌊h/2⌋) = O(n + ∑_j=1^h-1 2ⁱ(h-i))

Vogliamo mostrare ∑_j=1ⁿ e_(1/2) j < 3

Faccio una stima con serie geometrica

∑_e^j/2(1/2) < 3 (3)^j = 36/3^-1/3 3

∑_{e1 2ⁱ(h-i) = 2^h}

∑_e1