Anteprima
Vedrai una selezione di 7 pagine su 29
Algoritmi e Strutture dati - Schemi riassuntivi Pag. 1 Algoritmi e Strutture dati - Schemi riassuntivi Pag. 2
Anteprima di 7 pagg. su 29.
Scarica il documento per vederlo tutto.
Scarica
Algoritmi e Strutture dati - Schemi riassuntivi Pag. 6
Anteprima di 7 pagg. su 29.
Scarica il documento per vederlo tutto.
Scarica
Algoritmi e Strutture dati - Schemi riassuntivi Pag. 11
Anteprima di 7 pagg. su 29.
Scarica il documento per vederlo tutto.
Scarica
Algoritmi e Strutture dati - Schemi riassuntivi Pag. 16
Anteprima di 7 pagg. su 29.
Scarica il documento per vederlo tutto.
Scarica
Algoritmi e Strutture dati - Schemi riassuntivi Pag. 21
Anteprima di 7 pagg. su 29.
Scarica il documento per vederlo tutto.
Scarica
Algoritmi e Strutture dati - Schemi riassuntivi Pag. 26
1 su 29
D/illustrazione/soddisfatti o rimborsati
Disdici quando
vuoi
Acquista con carta
o PayPal
Scarica i documenti
tutte le volte che vuoi
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(m2)

BINARY SEARCH (A, key, l, r)

  1. if r < l
    • return
  2. m = l + (r - l) / 2
    • if A[m] = key
    • return m
  3. 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(m2))

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)

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(m2)

    T(m) = O(nlogn)

    T(m) = θ(n)

    T(m) = θ(n2)

    T(m) = O(mocosenga)

    LIMITE ASINTOTICO SUP

    f(m) ≤ g(m)

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

    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( nk )if n >= * k >= 0O(nlog b a log nc)O(n logb)

    MAX-HEAPIFY(A, i)

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

    HEAP-SORT(A)

    build-max-heap(A)for(A.length / A1) 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(dh2 / h1)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 (TR)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(TNL, SNL) =1) AND4: Tree-Comparison (Tr 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 è ≤ 2h

    Tracce del verbale:

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

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

    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 ≤ 2h+1 - 1 < 2h+1 → log 2x+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 ….

    1. sotto. → selez attività … punto … sottosob → tutte le attività di invarso ái a1 attività di inaviso dopo ai …
    2. Greco. … che si … attività am … di t1 pieno tempo → fine. Alla ins am e atris otisa …. Si … che aj tu in … ax. 2 cosi ax→ pieno tempo di … invari.

    (ax,av) a1+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|

    Dettagli
    Publisher
    gabrieledamiano999
    A.A. 2020-2021
    29 pagine
    SSD Scienze matematiche e informatiche MAT/05 Analisi matematica
    I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher gabrieledamiano999 di informazioni apprese con la frequenza delle lezioni di Algoritmi e strutture di dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Università degli studi della Basilicata o del prof Erra Ugo.