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 induzione

Caso base T = r → banale.

Passo 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 depth. If 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, discendenti, nodi esterni, albero ordinato

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

Procedura per induzione

Caso base T=r → banale.

Passo induttivo vale per alberi con 1 ≤ m ≤ n nodi. Proviamo 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 max. So tutte le foglie.

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.

n = # nodi, m = # foglie.

m = n – m + 1

h + 1 ≤ m ≤ 2^h

Proprietà

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) j = 36/3^-1/3 3 ∑_{e1 2ⁱ(h-i) = 2^h}∑_e1.