Algoritmi e Strutture dati - Schemi riassuntivi

Allego qui di seguito una carrellata di schemi svolti da me (in cartaceo e in digitale) dei vari algoritmi e argomenti svolti a lezione, per potersi esercitare e preparare in vista dell'esame oppure da consultare velocemente come formulario.

Esame Algoritmi e strutture di dati

Facoltà Ingegneria

Dal corso del Prof. Erra Ugo

Università Università degli studi della Basilicata

Publisher gabrieledamiano999

A.A. 2020-2021

29 pagine

Schemi e mappe concettuali

Vota 3,5 / 5 (2)

Scarica

Estratto del documento

MIN (A)

_{min = A[1]}

for i = 2 to A.length

if A[i] < min
min = A[i]

return min

T(m) = O(m)

MAX (A)

_{max = A[1]}

for i = 2 to A.length

if A[i] > max
max = A[i]

return max

T(m) = O(m)

INSERTION SORT (A)

for i = 2 to A.length

key = A[i]

j = i - 1

while j > 0 and A[j] > key

A[j+1] = A[j]
j = j - 1

A[j+1] = key

T(m) = O(m²)

BINARY SEARCH (A, key, l, r)

if r < l

return

m = l + (r - l) / 2

if A[m] = key
return m

else

if A[m] > key
return binarysearch (A, key, m+1, r)
else
return binarysearch (A, key, l, m-1)

(Caso migliore: T(m) = O(1))

(Caso peggiore: T(m) = O(m²))

T(m) = O(log n)

HERGE SORT (A, p, r)

if p < r

q = [(p + r) / 2]

HERGE SORT (A, p, q)

HERGE SORT (A, q + 1, r)

MERGE (A, p, q + 1)

m1 = q - p + 1

m2 = r - q

BRUTE FORCE SORT (A)

for i = 1 to A.length

min = i

for j = i to A.length

if A[j] < min
min = A[j]

index = j

temp = A[i]

A[i] = min

A[index] = temp

T(m) = O(m²)

T(m) = O(nlogn)

T(m) = θ(n)

T(m) = θ(n²)

T(m) = O(mocosenga)

LIMITE ASINTOTICO SUP

f(m) ≤ g(m)

↔
∃c, m₀ t.c f(m) ≤ c.g(m)
∀m > m₀

STACK

s.top ⇨ indica ultimo elemento inserito

STACK-EMPTY(S)if S.top = 0 return trueelse return falsePUSH(S, x)S.top = ma[m + 1] ⇧ S.topS.top = S.top + 1POP(S)if STACK-EMPTY(S) return “underflow”else S.top = S.top - 1 return S.top[S.top + 1]

O(1) COSTANTE

CODE

s.head ⇨ inizio del primo codice

ENQUEUE(A, x)Coda vuotas[A.head, A.tail, A[inizio]DEQUEUE(A)X = Coda head j A.head = 0, lunghezzaif A.head = lunghezza

O(1) COSTANTE

LISTE CONCATENATE

X.key ⇨ valore di xX.next ⇨ elem. successivo xX.pred ⇨ valore successore iX.prev ⇨ primo elementoLIST-INSERT(L, x)X.next = L.headif L.head = NIL L.head = xelse x.prev = x x.next = NILLIST-DELETE(L, x)if x.next != NIL x.next.prev = xelse if head = x.next if x.next != NIL x.next.prev = prev else x.prev.next = NIL

LIST-SEARCH(L, x)

X = L.headwhile x != NIL and x.key = x x = x.nextreturn x

O(m) caso peggiore numero elementi lista

MASTER THEOREM

T(m) := O(a T (n/b) + f(m))

O( n^k )if n >= * k >= 0O(n^{log _b a} log n^c)O(n log^b)

MAX-HEAPIFY(A, i)

Z = LEFT(i)l = RIGHT(i)

HEAP-SORT(A)

build-max-heap(A)for(A.length / A₁) A[i]

HEAP

A.Breeay = ⇦ _F dimensione array

A.size = m _{dimensionamento} massimo non massimo

PARENT(i) return ⌊i/2⌋LEFT(i) return 2iRIGHT(i) return 2i + 1BUILD-MAX-HEAP(A) n = A.length for i = ⌊A.length/2⌋ downto 1 MAX-HEAPIFY O(dh² / h¹)O(n) = θ(n log n)

T(m) = θ((n log n))

ESERCIZIO (Inversione Albero) - Dato un albero binario T si scriva una procedura di albero inverso, ossia un albero in cui ogni genitore viene ottenuto come foglio destro e sinistro con relativo sottoalbero.

TREE-SWAP (T_R)1: rotazione2: memorizzare3: inizio se sinistro4: se nb sinistro5: m para sinistro6: n dst ora destro

ESERCIZIO (Confronto tra due Alberi) - Date due alberi binari di ricerca, T e S. Scrivere una procedura che verifica che siano costantemente uguali, ovvero verificare se saranno strutturalmente identici (se hanno le stesse nodi e gli stessi sottoalberi).

TREE-COMPARISON (T,S)1: T->Null AND S->Null2: problema esisteend if3: if (TNull AND TNull AND Tree-Comparison(T_NL, S_NL) =1) AND4: Tree-Comparison (T_r di br)else5: return 0

ESERCIZIO (Potatura) - Dato un albero binario T, eliminare tutti i nodi fogli che non hanno un brothers. Un albero in cui i nodi foglia non abbiano foglia.Esempio albero TREE-DELETE

Progettare un algoritmo ricorsivo che determini il numero di nodi foglia presenti all'interno di un albero binario di ricerca T.

if x == NULL: return 0 else return x + SUM-TREE(x.left) + SUM-TREE(x.right)

Quick sort: Caso migliore

Se scegliamo un elemento di rango n/2

T(n) = ⎧0 se n=0;⎫

T(n) = (T(n-1) + (n-1) + Θ(n)T(m) = T(m-1 ) + (m-1) + Θ(m).... = 2T(m) + Θ(m)(m log m)

Dimostrare che qualunque algoritmo di ordinamento per confronti richiede (n log n) confronti nel caso peggiore.

Dimostrare prima che in un albero di decisione h, il numero dei figli è ≤ 2^h

Tracce del verbale:

Base: Se h=0, allora esiste un solo nodo che coincide con la foglia 2⁰ = 1

Passo: Induzione Supponga sia vera per h. 2^h se è vera per h, allora esiste un albero che coincide con il numero dei figli dei nodi al massimo 2^h

Supponiamo sia i nodi foglia in un albero di decisione h

n ≥ ⎣h/2⎦ ≥ 1 + ⌈m/2⌉ ≥ 2 + m h ≥ log(n/2) = n h / log(n) = Ω (m log n)

Un Max-Heap è una struttura che per ogni nodo i diverso dalla radice, si ha che A[Parent(i)] ≥ A[i]

Dim.: 2 ^h ≤ n ≤ 2^h+1 - 1 < 2^h+1 → log 2^x+1 = log m = 2

h ≤ log m + 1 = → h = ⌊log⌋

Illustrare l'esecuzione di HEAP-SORT sull'array A = (17, 15, 12, 21, 17, 25, 21, 20, 4, 9). Iniziate disegnano l'albero binario con i valori forniti in input e mostrate i vari passaggi fino ad arrivare all'array ordinato.

/* Funzione che inverte una lista */

INVERTI(L) temp = L.head while(temp != NULL) AGGIUNGI(B, temp.key) temp = temp.next return B

Selez. Attività

In 5.3 select un … insieme attività compatibile. In 5.3 e x finale c è un sottinsieme ai max di attività che si ….

sotto. → selez attività … punto … sottosob → tutte le attività di invarso ái a₁ attività di inaviso dopo ai …
Greco. … che si … attività am … di t₁ pieno tempo → fine. Alla ins am e atris otisa …. Si … che a_j tu in … a_x. 2 cosi a_x→ pieno tempo di … invari.

(ax,av) a₁+1 = …

Greedy Activity – Selector (s,f)

m = _5r length
i = 2, n
for m = 2 to m

return A

GREEDY - SPREGA

cont (P, m) // corrente

i = 1

while i ≤ m AND C > P[i]

C = C - P[i]

i = i + 1

return i - 1

n: oggetti / PC J: array pesi per ogni oggetto / I C: capacità totale per lossi oggetti

minimum: numero di scaloni

SOL. OTTIMA

Se S è una soluzione, ∃ x ∈ S un elemento alla soldi.

Se S - ⋏x, sarà una sol ottima per C - P[⋏x]

SC. GREEDY

Se S è una sol ottima. ∃x è l’elemento massimo, si

possono avere due casi:

x ∈ S, ont
x ∉ S, allora illuminiamo un elemento y ∈ S e lo
sostituomo con x (S - ⋏y)∪{⋏x}, sarà C ≥ S′

perché P[⋏x ≤ P[⋏y], quindi |S′| = |S|

Anteprima

Vedrai una selezione di 7 pagine su 29