I cinque algoritmi sui grafi da sapere

Kruskal, Prim, Dijkstra, Bellman-Ford, Floyd-Warshall

Kruskal

L'amico Kruskal vuole trovare l'albero (o gli alberi) che collega i vertici tramite gli archi più leggeri possibile.

Per fare questo, divide i vertici di un grafo in tanti sottoinsiemi quanti sono i vertici, poi ordina gli archi e considera le coppie di vertici partendo dall'arco più leggero: se i vertici appartengono allo stesso insieme, ignora l'arco; altrimenti aggiunge l'arco all'albero di copertura e unisce i due sottoinsiemi.

Il risultato è un albero di copertura minimo, il tempo di esecuzione è Θ(E log E).

_(, )
1.  ← ∅
2.  ℎ  ∈ []  //per [] intendiamo l’insieme dei vertici di 
3.   _() //abbiamo creato  insiemi, ognuno dei quali contiene un vertice
4.   ℎ        // tipico degli algoritmi Greedy
5.  ℎ (, ) ∈ []  //che sono ordinati
6.    _() ≠ _() ℎ
7.      ←  ∪ {(, )}
8.     (, )
9.  

Prim

L'amico Prim vuole trovare l'albero (o gli alberi) che collega i vertici tramite gli archi più leggeri possibile.

Per fare questo, sceglie uno dei vertici e lo inserisce nell'albero, poi controlla quale tra gli archi adiacenti è il più leggero (o i più leggeri), aggiunge il vertice all'albero e gli attribuisce un peso pari all'arco. Se durante la visita un vertice è già stato visitato, ma ha un peso maggiore dell'arco corrente, si cambia l'arco connesso e si aggiorna il peso del vertice.

Il risultato è un albero di copertura minimo, il tempo di esecuzione è O(E V log V) a patto di utilizzare per l'archiviazione dell'elenco dei vertici uno heap di Fibonacci.

_(, , )
1.  ← [] //inizializziamo Q con tutti i vertici di G
2.  ℎ  ∈  
3.   [] = ∞
4. [] = 0
5. [] = 
6. ℎ  ≠ ∅ 
7.    ← _() //estrae il vertice con campo key minore
8.    ℎ  ∈ []  //per ogni vertice adiacente al vertice estratto
9.       ∈  && (, ) < [] ℎ
10.       [] ←  //u diventa il padre di v
11.       [] ← (, ) //aggiorna il valore di key e riorganizza l’heap
12.   = {(, []) |  ∈  \ {}}

Dijkstra

L'amico Dijkstra vuole raggiungere nel tempo/spazio minore un vertice partendo da un altro vertice.

Per fare questo, come l'amico Dijkstra, inizializza tutti i vertici con peso ∞ e parent = NIL, poi iniziando dal vertice sorgente imposta nei vertici adiacenti il peso degli archi. Se arriva a un vertice già esplorato, ma il peso del vertice è maggiore del vertice "nuovo padre" più l'arco che li congiunge, ne cambia il padre e aggiorna il peso del vertice (rilassamento).

Il risultato è un albero in cui ciascun vertice è collegato alla sorgente con il percorso più breve possibile. Il costo dipende dall'implementazione dell'elenco dei vertici, e segue questa tabella:

Grafo sparso Grafo denso
Array lineare O(n2) O(n2)
Heap binario O(n log n) O(n2 log n)

dove per "Grafo sparso" si intende un grafo in cui il numero di vertici e il numero di archi tende ad essere uguale E = Θ(V), mentre per "Grafo denso" si intende che E = Θ(V2).

NOTA: Dijkstra si incasina se ci sono archi con peso negativo.

__(, )
1.  ℎ  ∈ []
2.   [] ← +∞
3.   [] ← 
4. [] ← 0

(, , )
1.  [] > [] + (, ) ℎ
2.   [] ← [] + (, ) //aggiorna il peso del cammino da  a 
3.   [] ←  //aggiorna il predecessore

(, , )
1. __(, )
2.  ← ∅ //insieme dei vertici già estratti
3.  ← [] //vertici da estrarre
4. ℎ  ≠ ∅ 
5.    ← _()
6.    ←  ∪ {} // S si riempie
7.    ℎ  ∈ [] 
8.     (, , (, ))

Esempio

Grafo di test con sorgente = 1
  1. V(G) = {1};
    1. (1,2), π(2) = NIL → 1, d(2) = ∞ → 2;
    2. (1,3), π(3) = NIL → 1, d(3) = ∞ → 4
  2. V(G) = {1, 2, 3};
    1. i nodi esplorati sono:
      1. π(1) = NIL, d(1) = 0
      2. π(2) = 1, d(2) = 2
      3. π(3) = 1, d(3) = 4
    2. (2, 4), π(4) = NIL → 2, d(4) = ∞ → d(2) + 7 = 9
    3. (2, 3), π(3) = 1 → 2, d(3) = 4 → d(2) + 1 = 3
    4. (3, 5), π(5) = NIL → 3, d(5) = ∞ → d(3) + 3 = 6
  3. V(G) = {1, 2, 3, 4, 5}
    1. i nodi esplorati sono:
      1. π(1) = NIL, d(1) = 0
      2. π(2) = 1, d(2) = 2
      3. π(3) = 2, d(3) = 3
      4. π(4) = 2, d(4) = 9
      5. π(5) = 3, d(5) = 6
    2. (5, 4), π(4) = 2 → 5, d(5) = 9 → d(5) + 2 = 8
    3. (5, 6), π(6) = NIL → 5, d(6) = ∞ → d(5) + 5 = 11
    4. (4, 6), π(6) = 5 → 4, d(6) = ∞ → d(4) + 1 = 10

Bellman-Ford

Gli amici Bellman e Ford vogliono raggiungere nel tempo/spazio minore un vertice partendo da un altro vertice, ma in un grafo che può avere pesi negativi.

Uno dei motivi per cui i grafi con pesi negativi sono più incasinati di quelli con pesi solo positivi è che se c'è un ciclo e il suo bilancio è negativo (es. a→b = +2, b→a = -5) per ridurre il peso del cammino basta ciclare all'infinito il loop.

L'algoritmo è piuttosto semplice: per ogni vertice per ogni arco applica il rilassamento; poi controlla che per ogni arco il suo peso sia minore o uguale della somma del vertice più l'arco che li congiunge. In caso contrario è di fronte a un cappio con bilancio negativo e l'algoritmo si ferma restituendo falso.

Il costo dipende dal tipo di grafo, se sparso o denso:

Grafo sparso Grafo denso
Dijkstra - Array lineare O(n2) O(n2)
Dijkstra - Heap binario O(n log n) O(n2 log n)
Bellman-Ford O(n2) O(n3)
_(, , )
1. __(, )
2.   = 1  |[]| − 1 
3.    ℎ (, ) ∈ [] 
4.     (, , (, ))
5.  ℎ (, ) ∈ [] 
6.    [] > [] + (, ) ℎ
7.      
8.  

Floyd-Warshall

Gli amici Floyd e Warshall vogliono raggiungere nel tempo/spazio minore qualunque vertice partendo da un altro vertice qualunque, cioè vogliono calcolare tutti i percorsi minimi possibili.

In modo simile a una matrice M di adiacenza, creano una matrice n*n tale con w: E→R che per ogni cella i,j:

  • se i == j allora M[i, j] = 0
  • se i != j e (i, j) è un arco, allora M[i, j] = w(i, j)
  • se i != j e (i, j) non è un arco, allora M[i, j] = ∞

Per ogni vertice controllano se la somma di ciascun vertice entrante più ciascun vertice uscente ha un peso minore dell'arco diretto o del valore calcolato precedentemente.

Il costo spaziale di questo algoritmo è n2, perché abbiamo bisogno di iniziare con quella che - di fatto - è una matrice nxn di adiacenza. Il costo temporale dell'algoritmo è n3, perché per ogni arco (compresi quelli con valore ∞, cioè compresi gli archi "assenti", che quindi corrispondono a ogni coppia nxn) dobbiamo iterare ogni vertice.

Esempio

La matrice di partenza richiede che siano valorizzati tutti gli archi e che gli "auto-archi" siano impostati a zero.

A
DA 1 2 3 4
1 0
2 0
3 0
4 0

Gli archi da nodo verso se stesso sono impostati a zero

1 2 3 4
1 0 3 7
2 8 0 2
3 5 0 1
4 2 0

Gli altri archi sono riportati (senza calcoli). Gli archi rimanenti, che non esistono, sono impostati a infinito.

Passaggio vertice 1: si riportano gli zeri, tutta la riga 1 e tutta la colonna 1, poiché rappresentano archi diretti che non è neccessario calcolare.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 7
2 8 0
3 5 0
4 2 0

Ora cerchiamo di calcolare il cammino da 2 a 3. L'arco diretto riporta il peso 2, dobbiamo capire se arrivare da 2 a 3 passando per 1 è più conveniente. (2,1) pesa 8, (1, 3) pesa infinito, 8+∞ = ∞, quindi ci conviene tenere l'arco diretto.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 7
2 8 0 2
3 5 0
4 2 0

Ora cerchiamo di calcolare il cammino da 2 a 4. L'arco diretto riporta il peso ∞, dobbiamo capire se arrivare da 2 a 4 passando per 1 è più conveniente. (2,1) pesa 8, (1, 4) pesa 7, 8+7 = 15, quindi ci conviene passare per 1.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 7
2 8 0 2 15
3 5 0
4 2 0

Da 3 a 2 l'arco diretto è ∞, mentre passando per 1 è 5+3 = 8, quindi cambiamo in 8.

Da 3 a 4 l'arco diretto è 1, mentre passando per 1 è 5+7 = 12, quindi teniamo 1.

Da 4 a 2 l'arco diretto è ∞, mentre passando per 1 è 2+3 = 5, quindi cambiamo in 5.

Da 4 a 3 l'arco diretto è ∞, mentre passando per 1 è 2+∞ = ∞, quindi lasciamo ∞.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 7
2 8 0 2 15
3 5 8 0 1
4 2 5 0

Partendo da questa tabella, si ripete per gli altri tre vertici.

_()
1.  ← [] //calcolo il numero di righe, ovvero il numero di vertici
2. 0 = 
3.   = 1  
4.     = 1   
5.       = 1   
6.       [,]() = min([,](−1) + [,](−1), [](−1))
7.  

Compiti ASD

Tempi di esecuzione (teoria)

Alcune soluzioni si trovano qui.

27/05/2015

Si confrontino le seguenti funzioni utilizzando le relazioni O, Ω e Θ (giustificando le risposte):

f(n) g(n)
10n3 + log n + 2n n2 + log n5
n! 2n
2n 2n+100

28/01/2015

Si risolvano le seguenti ricorrenze:

  • T(n) = 3T(n/2) + n2
  • T(n) = 4T(n/2) + n2
  • T(n) = T(n/2) + 2n

23/01/2014

Si definiscano formalmente le relazioni O, Ω, Θ e, utilizzando le definizioni date e
nient’altro, si dimostri la verità o la falsità di ciascuna delle seguenti affermazioni:

  1. n logn = Θ(n2)
  2. n + √3n = Ω(logn)
  3. 4n log n = Ο(4n + log n2)
  4. 2n+k = Ο(2n ), dove k è una costante intera positiva
  5. 2n+n = Ο(2n)

08/09/2014

Per un certo problema sono stati trovati due algoritmi risolutivi (A1 e A2) con i seguenti tempi di esecuzione:

A1 : T(n) = 3·T(n/2) + n2
A2 : T(n) = 4·T(n/2) + n2

Si dica, giustificando tecnicamente la risposta, quale dei due algoritmi è preferibile per input di dimensione sufficientemente grande.

12/06/2014

Si confrontino le seguenti funzioni utilizzando le relazioni O, Ω e Θ:

f(n) g(n)
100 n + log n n + (log n)2
log n log n3
2n 3n

01/09/2015

Utilizzando la definizione di O, e nient’altro, si stabilisca se le seguente affermazioni sono vere o false:
a) f(n) = O(n)
b) f(n) = O(n2)
dove f(n) = (2n − 1) / 2.

Costi di esecuzione (strutture dati)

27/05/2015

Completare la seguente tabella indicando la complessità delle operazioni che si riferiscono a un dizionario di n elementi. Per l’operazione Successore si assuma di essere sull’elemento x a cui si applica l’operazione.

Ricerca Massimo Successore Minimo Costruzione
Albero binario di ricerca
Min-Heap

Soluzione: https://diario.softml.it/costi-di-esecuzione-strutture-dati-27-05-2015/

Funzioni efficienti (grafi)

27/05/2017

Il seguente algoritmo accetta in ingresso la matrice di adiacenza di un grafo non orientato e restituisce un valore Booleano (TRUE / FALSE)

MyAlgorithm( A )
1. n = rows(A) /* determina il numero di vertici del grafo */
2. let B an n x n matrix /* alloca memoria per una matrice B n x n */
3. for i = 1 to n
4.   for j = 1 to n
5.     b[i,j] = 0
6.     for k = 1 to n
7.       b[i,j] = b[i,j] + a[i,k]*a[k,j]
8. for i = 1 to n
10.  for j = i + 1 to n
11.     if a[i,j]*b[i,j] <> 0 then
12.return FALSE
13.return TRUE

Si calcoli la complessità computazionale di MyAlgorithm e si determini la sua funzione (in quali casi restituisce TRUE? in quali casi FALSE?). (Nota: Nel determinare la   complessità si ignori per comodità la complessità delle istruzioni 1 e 2).
Si simuli inoltre il suo comportamento sui seguenti due grafi, verificando che restituisca il risultato atteso:

La soluzione è riportata qui: https://diario.softml.it/funzioni-efficienti-grafi-27-05-2017/

28/01/2015

Si scriva l’algoritmo di Floyd-Warshall, si dimostri la sua correttezza, si fornisca la sua complessità computazionale e si simuli accuratamente la sua esecuzione sul seguente grafo:

28/01/2015

Un piroscafo collega regolarmente n città portuali. Ad ogni porto u il proprietario del piroscafo ricava P(u) euro, ma per andare dal porto u al porto v spende in totale C(u,v) euro. Se P(u)/C(u,v) > 1, il proprietario del piroscafo ha quindi realizzato un guadagno. Si vuole stabilire se esiste un itinerario ciclico di k città (x0, x1, ..., xk = x0) per il quale

i=1kPxii=1kCxi-1xi

dove μ ≥ 1 è una quantità stabilita a priori che rappresenta il guadagno minimo che il proprietario del piroscafo intende realizzare.

Si scriva un algoritmo che accetti in ingresso i ricavi P per ogni porto, i costi C per ogni coppia di porti e la costante μ, e stabilisca se un tale itinerario esiste o meno. Si discuta la correttezza dell'algoritmo proposto e la sua complessità computazionale.

08/09/2014-1

Sia G = (V, E) un grafo orientato e pesato, sia s∈V un vertice “sorgente” e si supponga che G sia stato inizializzato con INIT-SINGLE-SOURCE(G, s). Si stabilisca se la seguente affermazione è vera o falsa: «Se G non contiene un ciclo di peso negativo raggiungibile dalla sorgente s, allora nessuna sequenza di passi di rilassamento potrà assegnare al campo d[s] un valore diverso da 0.»

Nel primo caso si fornisca una dimostrazione, nel secondo un controesempio.

08/09/2014-2

Si vuole costruire una rete stradale che colleghi cinque città (A-E), minimizzando i costi complessivi di realizzazione. I costi per la costruzione di una strada tra due città sono sintetizzati nella seguente tabella (dove +∞ significa che la strada è irrealizzabile):

A B C D E
A 0 3 5 11 9
B 3 0 3 9 8
C 5 3 0 +∞ 10
D 11 9 +∞ 0 7
E 9 8 10 7 0

Si formuli il problema dato in termini di un problema di ottimizzazione su grafi, e si descriva un algoritmo per la sua soluzione discutendone correttezza e complessità. Infine, si simuli accuratamente l’algoritmo presentato per determinare una soluzione del problema.

29/05/2014

Si scriva un algoritmo di complessità O(n2 log n) per determinare le distanze tra tutte le coppie di vertici in un grafo sparso G avente pesi sugli archi positivi, dove n è il numero di vertici in G.

12/09/2016

Si stabilisca quale problema risolve il seguente algoritmo, che accetta in ingresso un grafo non orientato G = (V, E):

MyAlgorithm(G)
1. A = ∅
2. ordina i vertici di G per grado crescente
3. for each u ∈ V[G] do /* vertici estratti secondo l’ordine stabilito nel passo 2 */
4.    if MyFunction(G,A,u) then
5.       A = A ∪ {u}
6. return A
MyFunction(G,A,u)
1. for each v ∈ A do
2.    if (u,v) ∈ E[G] then
3.       return FALSE
4. return TRUE

Si dimostri la correttezza dell’algoritmo, si determini la sua complessità e si simuli infine la sua esecuzione sul seguente grafo:

01/09/2015

Il seguente algoritmo accetta in ingresso la matrice di adiacenza A di un grafo orientato ed un intero k (con k ≥ 2), e restituisce un valore Booleano (TRUE / FALSE):

MyAlgorithm(A,k)
1. n = rows(A) /* determina il numero di vertici del grafo */
2. let B be the n x n identity matrix
3. for i = 1 to k - 1
4.   B = MyFunction(A,B)
5.   for i = 1 to n
6.     for j = i + 1 to n
7.       if B[i,j]*A[j,i] ≠ 0 then
8.       return FALSE
9. return TRUE

L’algoritmo utilizza la seguente funzione che accetta in ingresso due matrici quadrate (di dimensione identica) e restituisce un’altra matrice quadrata della stessa dimensione:

MyFunction(X,Y)
1. n = rows(X)
2. for i = 1 to n
3.   for j = 1 to n
4.     Z[i,j] = 0
5.     for k = 1 to n
6.       Z[i,j] = Z[i,j] + X[i,k]*Y[k,j]
7. return Z

Si calcoli la complessità computazionale complessiva di MyAlgorithm e si determini qual è il problema che risolve (ovvero: in quali casi restituisce TRUE? in quali casi FALSE?). (Nota: Nel determinare la complessità si ignori per comodità la complessità delle istruzioni 1 e 2 di MyAlgorithm e dell’istruzione 1 di MyFunction).

Si simuli inoltre il suo comportamento sui seguenti due grafi, verificando che restituisca il risultato atteso:

Grafi (cammini minimi)

27/05/2015-1 e 12/06/2014 e 12/09/2016

Il problema di determinare i cammini minimi tra tutte le coppie di vertici di un grafo pesato G=(V, E, w) con pesi positivi si può risolvere iterando |V| volte l'algoritmo di Dikstra oppure utlizzando l'algoritmo di Floyd-Warshall. Si riempia la tabella sottostante, specificando le complessità degli algoritmi indicati in funzione della
tipologia di grafo utilizzato:

Grafo sparso Grafo denso
Iterated_Dijkstra (array)
Iterated_Dijkstra (heap)
Floyd-Warshall (27/05/15)
Bellman-Ford (12/06/14)

Supponendo che il grafo sia aciclico, quale algoritmo conviene usare? Perché?

27/05/2015-2

Sia G = (V, E) un grafo non orientato, connesso e pesato e sia (S, V \ S) un taglio di G. Si supponga che l'arco leggero che attraversa il taglio sia unico e lo si denoti con (u,v). In altri termini, per tutti gli altri archi (x,y) che attraversano il taglio, si avrà w(u,v) < w(x,y). Si dimostri che tutti gli alberi di copertura minima di G dovranno necessariamente contenere l'arco (u,v).

28/01/2015

Si determinino due diversi alberi di copertura minimi nel seguente grafo:

12/06/2014-1

Si scriva l’algoritmo di Kruskal, si dimostri la sua correttezza, si fornisca la sua complessità computazionale e si simuli accuratamente la sua esecuzione sul seguente grafo:

12-06-2014-2

Si supponga di voler cambiare una banconota da P euro in monete da a1, a2, …, ak euro. E’ possibile? In caso affermativo, qual è il minimo numero di monete da utilizzare per effettuare il cambio? Per esempio, se si volesse cambiare una banconota da 5 euro in monete da 1 e da 2 euro, sarebbero necessarie almeno 3 monete.

Se si disponesse soltanto di monete da 2 euro, invece, il cambio non sarebbe possibile.

Si formuli questo problema come un problema di cammini minimi su grafi. (Suggerimento: si costruisca un grafo con P + 1 vertici numerati da 0 a P e si inseriscano archi e pesi in modo tale che i cammini dal vertice 0 al vertice P corrispondano a possibili sequenze di monete da utilizzare per il cambio.)

A titolo esemplificativo, si consideri il caso di una banconota da P = 10 euro e monete da a1 = 1 e a2 = 2 euro.

Si costruisca il grafo corrispondente e si utilizzi l’algoritmo di Dijkstra per risolvere il problema.

29/05/2014-1

Si scriva l’algoritmo di Bellman-Ford, si dimostri la sua correttezza, si fornisca la sua complessità computazionale e si simuli accuratamente la sua esecuzione sul seguente grafo (utilizzando il vertice A come sorgente):

29/05/2014-2

Sia G = (V, E) un grafo pesato non orientato e connesso e sia w : E → R la funzione peso.
Sia Tmin un albero di copertura minimo di G e sia T un qualsiasi altro albero di copertura (non necessariamente minimo). Inoltre sia (u,v) ∈ E un arco di peso massimo in Tmin e (x,y) ∈ E un arco di peso massimo in T. Si dimostri che:

w(u,v) ≤ w(x,y).

In altri termini, fra tutti gli alberi di copertura, l’albero di copertura minimo ha il più piccolo arco di peso massimo. (Suggerimemto: si ragioni per assurdo e si usi la classica tecnica del “taglia-e-incolla”.)

12/09/2016

Si determini un albero di copertura minimo nel seguente grafo:

01/09/2015

Sia G = (V, E) un grafo non orientato, connesso e pesato. Dato un taglio (S, V \ S) di G, sia (u,v) un arco che lo attraversa tale che per tutti gli altri archi (x,y) che attraversano il taglio risulta w(u,v) ≤ w(x,y) (arco leggero). Si stabilisca, giustificando formalmente la risposta, se la seguente affermazione è vera o falsa: «Se T è un albero
di copertura di G che non contiene (u,v), allora T non è un albero di copertura minimo.»

Si può affermare la stessa cosa se si assume che tutti i pesi di G siano distinti? Perché?

Nota: nel fornire le giustificazioni non si faccia ricorso al teorema fondamentale degli MST.

Funzioni efficienti (alberi)

27/05/2015

Dato un albero binario, i cui nodi sono colorati di bianco, rosso o verde:

a. scrivere una funzione efficiente che stabilisca se esiste un cammino di tre nodi nell’albero i cui colori formano la bandiera italiana. (Il cammino può partire da un nodo qualsiasi, non necessariamente dalla radice.)

b. Fornire la chiamata della funzione dal programma principale.

c. Analizzare la complessità di tale funzione.

Il tipo Node utilizzato per rappresentare l’albero binario è il seguente:


typedef struct node{
char * colore;
struct node * left;
struct node * right;
} * Node;

28/01/2015

Un nodo di un albero binario u è detto intermedio se la somma delle chiavi contenute nei nodi del sottoalbero di cui u è radice è uguale alla somma delle chiavi contenute nei nodi sul percorso che collega u alla radice dell’albero (u escluso).

a) Scrivere un algoritmo efficiente che restituisca il numero di nodi intermedi.

b) Analizzare la complessità della soluzione trovata. Il tipo Node utilizzato per rappresentare l’albero binario è il seguente:

typedef struct node{
int key;
struct node * left;
struct node * right;
} * Node;

23/01/2014

Dato un albero binario i cui nodi sono colorati di bianco o di nero, scrivere una funzione C efficiente che calcoli il numero di nodi aventi lo stesso numero di discendenti bianchi e neri. (Un nodo è discendente di se stesso.)

Inoltre analizzare la complessità di tale algoritmo.

Il tipo Node utilizzato per rappresentare l’albero binario è il seguente:

typedef struct node{
char * colore;
struct node * left;
struct node * right;
} * Node;

Si può ordinare un dato insieme di n numeri costruendo un albero binario di ricerca che contiene questi numeri (usando ripetutamente Tree-Insert per inserire i numeri uno alla volta) e stampando poi i numeri utilizzando un certo tipo di visita. Scrivere l’algoritmo che realizza questo ordinamento e specificare il tipo di visita effettuata e il relativo algoritmo.

Quali sono i tempi di esecuzione nel caso peggiore e nel caso migliore per questo algoritmo di ordinamento?

08/09/2014

Dato un albero binario, scrivere un procedura efficiente che cancelli il figlio sinistro di ogni nodo se è una foglia e contiene la stessa chiave del nodo padre.

Calcolare la complessità al caso pessimo della funzione indicando la corrispondente relazione di ricorrenza.

La rappresentazione dell’albero binario utilizza esclusivamente i campi left, right e key e il prototipo della procedura è:

void cancella(Node u)

12/06/2014-1

Dato un albero binario di ricerca T, scrivere la funzione Tree-maximum(Node x) che restituisce un nodo con chiave massima di un sottoalbero di T radicato nel nodo x (x è un nodo dell’albero T e x ≠ NULL). Quale è la complessità di questa funzione? Quale è il caso migliore? E il caso peggiore?

12/06/2014-2

Progettare un algoritmo efficiente per stabilire se un albero binario è quasi completo, cioè tutti i livelli dell’albero sono completamente riempiti, tranne eventualmente l’ultimo che ha le foglie addossate a sinistra.

Calcolare la complessità al caso pessimo dell’algoritmo indicando, e risolvendo, la corrispondente relazione di ricorrenza.

La rappresentazione dell’albero binario utilizza esclusivamente i campi left, right e key.

12/09/2016

Scrivere una funzione efficiente check che dato un albero binario di ricerca verifica se è soddisfatta la seguente condizione: per ogni intero k, se le chiavi k e k+2 sono nell'albero allora anche la chiave k+1 è nell'albero.

Analizzare la complessità della funzione. È preferita una soluzione con spazio aggiuntivo O(1).

Funzioni efficienti (divide-et-impera e altro)

28/01/2015

Scrivere un algoritmo efficiente, di tipo divide et impera, che conta il numero di occorrenze della sequenza ‘a’ ‘r’ memorizzata in posizioni adiacenti in un array di caratteri.

Analizzare la complessità indicando e risolvendo la corrispondente relazione di ricorrenza.

Esempio:

Per l’array ‹a, b, c, r› la risposta sarà 0.
Per l’array ‹b, a, r, c, a, r› la risposta sarà 2.

08/09/2014

Progettare un algoritmo efficiente che, dato un array A di n numeri interi e un intero x, determini se esistono due elementi in A (in posizioni diverse) la cui somma è esattamente x.

Calcolare la complessità al caso pessimo dell’algoritmo.

29/05/2014-1

Si determini la complessità asintotica dell’algoritmo AlgA definito come segue:

AlgA(n)
1. s ← 0
2. for i ← 1 to n
3. do s ← s + AlgB(n)
4. return s
AlgB(m)
1. if m = 1
2. then return 0
3. else return B(m/2) + m

29/05/2014-2

Progettare un algoritmo efficiente di tipo divide et impera che dato un vettore di interi restituisce true se tutti i valori sono distinti, false altrimenti. Analizzare la complessità dell’algoritmo proposto.

12/09/2016

Un collezionista di figurine possiede K figurine, non necessariamente distinte. Le figurine vengono stampate con un numero di serie, impresso dal produttore. I numeri di serie sono tutti gli interi compresi tra 1 e N. La collezione sarebbe completa se ci fosse almeno un esemplare di tutte le N figurine prodotte. Purtroppo la collezione non è completa: sono presenti dei duplicati, mentre alcune figurine mancano del tutto. Il vostro compito è di indicare i numeri di serie delle figurine mancanti.

Scrivere un algoritmo efficiente che dato N e l'array S[1..K], ove S[i] è il numero di serie della i- esima figurina posseduta, stampa l'elenco dei numeri di serie mancanti.

L'array S non è ordinato. Ad esempio, se N=10 e S=[1, 4, 2, 7, 10, 2, 1, 4, 3], l'algoritmo deve stampare a video i numeri di serie mancanti 5, 6, 8, 9 (non necessariamente in questo ordine).

Determinare la complessità dell'algoritmo di cui sopra, in funzione di N e K.

Attenzione: K potrebbe essere minore, uguale o maggiore di N.

01/09/2015

Progettare un algoritmo di ordinamento che si comporti come MergeSort, ma che divida ricorsivamente l’array in tre pari anziché due.
a. Scrivere lo pseucodice della nuova procedura MergeSort3.
b. Scrivere lo pseudocodice della nuova procedura Fusione3.
c. Scrivere e risolvere l’equazione di ricorrenza associata.

Hash

28/01/2015

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi numeriche nell’ordine indicato:
18, 36, 155, 19
La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:
h(k, i) = (k mod m + i * 2k mod 5) mod m
Indicare per ogni chiave le posizioni scandite nella tabella e la posizione finale dove viene allocata.

27/05/2015

Nell’ipotesi di indirizzamento aperto, scrivere uno pseudocodice per HASH-DELETE e modificare HASHINSERT per gestire il valore DELETED. Analizzare la complessità delle due procedure nel caso pessimo.

12/06/2014

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi
numeriche nell’ordine indicato:

23, 40, 15, 58, 85

Indicare per ogni chiave la posizione finale dove viene allocata in questi due casi:

a. Funzione Hash:

h(k) = k mod m

Risoluzione delle collisioni mediante concatenamento

b. La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:

h(k, i) = (k mod m + i * 2k mod 5) mod m

Si devono indicare tutte le posizioni scandite nella tabella.

Heap

09/09/2014

Dare la definizione di max-heap e dire se ‹23,17,14,6,13,10,1,5,7,12› è un max-heap giustificando la risposta.

29/05/2014

L’operazione Heap-Delete(A, i), cancella l’elemento nel nodo i dall’heap A. Implementare la procedura Heap-Delete in modo che il suo tempo di esecuzione sia O(lg n) per un max-heap di n elementi.

01/09/2015

Supponete di avere un min-heap di n elementi, e di cercare il valore massimo. In quali posizioni del vettore cercate? Giustificare la risposta.

Scrivere un algoritmo che dato un min-heap non vuoto restituisca il massimo. Calcolare la complessità.

Problemi P/NP/NPC

01/09/2015

Si definiscano le classi P, NP, NPC e si stabilisca, giustificando formalmente la risposta, quale delle seguenti relazioni è ritenuta vera (o verosimile):

12/09/2016

Si definisca formalmente la relazione di riducibilità polinomiale tra problemi decisionali ( ≤P ) e si stabilisca se le seguenti affermazioni sono vere o false:

1) La relazione ≤P è transitiva
2) La relazione ≤P è riflessiva
3) Se ≤P è simmetrica, allora P = NP
4) Se P ≤P Q e Q ∈ P, allora P ∈ P
5) Se P, Q ∈ NPC, allora P ≤P Q se e solo se Q ≤P P

Nel primo caso si fornisca una dimostrazione rigorosa, nel secondo un controesempio.

Nota: in caso di discussioni poco formali l’esercizio non verrà valutato pienamente.