Progettazione e analisi di algoritmi

Strutture Dati

Strutture dati

Array e stringhe

array monodimensionale

array monodimensionale rappresentazione compatta

array bidimensionale

array bidimensionale (disomogeneo)

Caratteristiche:

L'operazione di accesso all'i-esimo elemento A[i] lo considereremo indipendente da n (num elementi) - non sempre vero nella realtà: cache e paginazione

CREAZIONE ARRAY = tempo necessario = n carattere, int32, int64...

MEMORIA OCCUPATA = dim_array * SIZEOF(Item)

Array multidimensionale:

ACCESSO ad un elemento A[i₁, j₂, ..., l_k] avviene in un tempo indipendente da n₁, ..., s ≤ k

INIZIALIZZAZIONE T_ik

Stack

LAST-IN-FIRST-OUT — LIFO

Nelllo Stack è possibile avere un accesso limitato, oppure possiamo dire una malusta ordinata o collezione o contenitore una sortatatura, rispetto alla regole delle aberazione o cancellazione dei dati: LA CANCELLAZIONE e L’INSERIMENTO sono possibili solo da un lato

Esempio per capire

Contenuto CD

Se vogliamo inserire un CD possiamo solo inserirlo sopra! Cosí come se vogliamo togliere un CD possiamo farlo solamente nella parte alta della pila dello Stack. Se vogliamo prendere il primo CD che abbiamo messo

l'unica speranza sarà di togliere tutti i CD che stanno al di sopra di quel disco e solo dopo possiamo togliere il CD interessato

3 operazioni:

• INSERIMENTO di un elemento PUSH (s: Stack, x: Item)
• RIMOZIONE della cima POP (s: Stack): Item
• INTERROGAZIONE della cima TOP (s: Stack): Item

Empty (x: List) Boolean

return (x.head = NIL)

Head (x: List) Item

if EMPTY(x) then return error

else return x.head.key

Tail (x: List) Item

if EMPTY(x) then return error

else return x.tail.key

Insert Front (x: List, x: Item)

n ← new Node, n.key ← x

n.next ← x.head, n.prev ← NIL

if Empty (x) then

x.head ← n, x.tail ← n

else

x.head.prev ← n

x.head ← n

Insert Back (x: List, x: Item)

n ← new Node, n.key ← x

n.next ← NIL, n.prev ← x.tail

if Empty (x) then

x.head ← n, x.tail ← n

else

x.tail.next ← n

x.tail ← n

SEARCH (x: List, x: Item): Boolean

n ← LISTSEARCH (x, x)

return (n ≠ NIL)

LIST SEARCH (x: List, x: Item): Node

n ← x.head

while (n ≠ NIL) and (n.key ≠ x) do

n ← n.next

return n

DELETE FRONT (x: List): Item

if (x = NIL) then return error

x ← x.head.key

LIST DELETE (x, x.head)

return x

LISTDELETE (x: List, n: Node)

if (n.prev ≠ NIL) then

n.prev.next ← n.next

else

x.head ← n.next

if (n.next ≠ NIL) then

n.next.prev ← n.prev

else

x.tail ← n.prev

*fuoriesce il valore che è stato emulato

Alberi ordinati

Un albero ordinato è un albero radicato in cui i figli di ogni vertice sono ordinati.

Nota che T₁ e T₂ sono alberi radicati, ma T₂ e T₂ sono alberi ordinati.

Albero binari

Un albero binario T è definito ricorsivamente come un insieme finito di nodi che:

• Non contiene nodi (l'albero vuoto), oppure è composto da 3 insiemi disgiunti di nodi :
• Un nodo, solito radicato ma solitario detto radice
• T₁ e T₂ sono alberi ordinati ma T₁ e T₂ sono alberi binari.

Alberiposizionale e k-ari

In un albero posizionale i figli di un nodo sono etichettati con interi positivi distinti.

Un albero k-ario è un albero posizionale in cui tutti i figli con le etichette maggiori di k sono assenti: es. binario albero k-ario con k=2

• Un albero k-ario è completo se:
• Tutte le foglie hanno la stessa profondità
• Tutti i nodi interi hanno grado K

Realizzazione di alberi radicati e alberi ordinati

Ogni nodo n dell'albero è un oggetto di tipo Node in cui:

• n.key è la chiave dell'elemento n
• n.children è un oggetto di tipo List con i riferimenti ai figli
• n.father è il riferimento al padre di n

Un albero T è un oggetto di tipo Tree con un campo t_root di tipo Node che identifica la radice dell'albero e se t_root è NIL significa che l'albero è vuoto.

Realizzazione di alberi binari

L'oggetto Tree ha la stessa struttura degli alberi radicati.

L'oggetto Node contiene due campi: left right di tipo Node che sostituiscono il campo children

Per un albero posizionale o x-ario si può utilizzare un'array per il campo children invece che una lista.

Efficienza, vi sono due tipologie

• Efficienza in termini di tempo
• Efficienza in termini di spazio

Aspetti aggiuntivi:

• Un singolo parametro dimensionale può non essere sufficiente, in grafi reticolari spesso non basta sapere il numero dei nodi
• La scelta del parametro con cui misurare l’istanza è critica
• Una diversa scelta del parametro comporta risultati differenti dell’analisi

Misura efficienza -> approccio analitico: identificare l’operazione di base all’interno dell’algoritmo, Calcolare il numero di volte che un’operazione viene eseguita dall’algoritmo in funzione della dimensione dell’input

Costo operazioni modello RAM

• Le operazioni elementari hanno un costo unitario
• Per quanto concerne (es.cicli), hanno un costo che dipende dal numero di operazioni eseguite al loro interno
• Quesito in memoria, non ha un costo unitario (Trascuriamo Cache e memoria virtuale)
• La memoria ha un costo in funzione della memoria

Esempio:

• x := x + 1
• x := A[i]
• if (x > 0) then ... test logico

_{costo unitario}

^{costo non unitario}

for i = 0 to n do ... ciclo

AFUNCTION ( ... ) chiamata a funzioni

a meno che la fun. è abbreviato unitaria

Ordini di infinito (efficienza asintotica)

Valori di alcune funzioni del tipo f(n) per valori di n crescenti

nota: una piccola dimensione n non è significativa per valutare l’efficienza comparata

O(g₀(n)) -> come dire limite superiore e l’insieme di tutte le funzioni un ordine di infinito maggiore o uguale a g(n)

Esempio valida n ∈ O(n²) 100 + 5 ∈ O(n²)

Ω(g₁(n)) -> come dire che c’è il limite inferiore insieme di una ordine di infinito di maggiore o uguale a g(n)

Esempio valida

Θ(g₂(n)) -> è l’insieme di tutte le funzioni il cui ordine di infinito è lo stesso di g(n)

Esempio valida per O(n²): an² + bn + c ( ... ) rimane esempio di Θ good, n² log(n)

non valida per Ω(n²): a = 0,3 ;

Per cui se p = 0, cioè l'elemento non è in A, allora sostituisco

C_avg(n) = ⁿ⁺¹/₂ + n(1-0) n

Se invece p = 1, cioè se l'elemento è contenuto in A

C_avg(n) = n + 1 + ¹/₂ n + (1-1) n

Quindi risulta che ⁿ⁺¹/₂ ≤ C_avg(n) ≤ n — definizione di Θ(n)

In media SEQUENTIAL SEARCH ha un costo proporz a ⁿ/₂

Limite inferiore del caso pessimo

Se un algoritmo A per un problema P è tale per cui C^worst(n) = min {max C_θ(I)}, allora diciamo che A ha un caso ottimo nel caso pessimo

Non esiste miglior algoritmo che ha prestazioni migliori di SEQUENTALSEARCH nel caso pessimo.

Dimostriamo che non esiste un algoritmo corretto che esegue meno confronti di SEQUENTALSEARCH nel caso pessimo — quindi è anch'esso il limite inferiore del caso pessimo per la ricerca array

Teorema

Dato un algoritmo di ricerca corretto in un vettore A[0,1... n-1] che esegue

• m confronti fra elementi di A
• e confronti tra K e gli elementi di A,

si ha che m + ℓ ≥ n

//In poche parole: potremmo pensare che riordinare il vettore e dopo cercare il valore K sia una mossa astuta, ma in realtà già il costo ottimo (caso migliore) è n log n, che è maggiore di n / NON CONVIENE

Corollario: Dato che pure SEQUENTALSEARCH vale m = 0 e ℓ = n nel caso pessimo, non esiste alg migliore

Dimostrazione:

• Supponiamo che le m operazioni siano eseguite preliminarmente onde riorganizzare A per facilitare la ricerca (ordino il vettore)
• Al termine di tale fase A è diviso in p parti, ciascuna organizzata utilizzando dei confronti tra i soli elem. di A
• Inizialmente, l'elemento di A è impari a sé stante, e serve almeno un confronto per ridurre delle parti di 1, quindi risulta m ≥ n - p
• Le successive ℓ operazioni devono esaminare ogni parte almeno una volta per non saltare K, quindi ℓ ≥ p
• Sommandole viene: m + ℓ ≥ n - p + p → m + ℓ ≥ n