Maggio 2018 Archive

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.

Svolgimento

Un max-heap è un albero in cui gli elementi sono tutti non maggiori dell'elemento padre.

L'implementazione ad array di uno heap binario consiste nel posizionare come primo elemento la radice dell'albero (23, nell'esercizio) e poi per ogni livello l 2^l elementi, in posizione 2^l e 2^l+1.

L'albero corrispondente all'array è quindi

               23
      17              14
  6        13      10     1
5   7    12

Dal momento che 7 > 6, questo non è un max-heap.

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.

Svolgimento

Caso A:

1. 23 mod 17 = 6 → 6[0] = 23
2. 40 mod 17 = 6 → 6[1] = 40
3. 15 mod 17 = 15 → 15[0] = 15
4. 58 mod 17 = 7 → 7[0] = 58
5. 85 mod 17 = 0 → 0[0] = 85

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23, 40; 7: 58; 8:; 9:; 10:; 11:; 12:; 13:; 14:; 15: 15; 16:;

Caso B

1. i = 0, k = 23: (23 mod 17 + 0 * 2*23 mod 5) mod 17 = 6
2. i = 1, k = 40: (40 mod 17 + 1 * 2*40 mod 5) mod 17 = 6: c'è una collisione, quindi si scorre fino al numero 7
3. i = 2, k = 15: (15 mod 17 + 2 * 2*15 mod 5) mod 17 = 15
4. i = 3, k = 58: (58 mod 17 + 3 * 2*58 mod 5) mod 17 = 10
5. i = 4, k = 85: (85 mod 17 + 4 * 2*85 mod 5) mod 17 = 0

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23; 7: 40; 8:; 9:; 10: 58; 11:; 12:; 13:; 14:; 15: 15; 16:;

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 * 2^{k mod 5}) mod m
Indicare per ogni chiave le posizioni scandite nella tabella e la posizione finale dove viene allocata.

i = 0, k = 18 → (18 mod 17 + 1 * 2^{18 mod 5}) mod 17 = (1 + 0 * 8) mod 17 = 1

i = 1, k = 36 → (36 mod 17 + 1 * 2^{36 mod 5}) mod 17 = (2 + 1 * 2) mod 17 = 4

i = 2, k = 155 → (155 mod 17 + 2 * 2^{155 mod 5}) mod 17 = (2 + 2 * 1) mod 17 = 4: collisione

i = 3, k = 155 → (155 mod 17 + 3 * 2^{155 mod 5}) mod 17 = (2 + 3 * 1) mod 17 = 5

i = 4, k = 19 → (19 mod 17 + 4 * 2^{19 mod 5}) mod 17 = (2 + 4 * 16) mod 17 = 15

La hash finale è la seguente (l'indicizzazione è 0 - n-1):

[_] [18] [_] [_] [36] [155] [_] [_] [_] [_] [_] [_] [_] [_] [_] [19] [_]

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):

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.

Svolgimento

Il grafo è non orientato, poiché la matrice di adiacenza è simmetrica.

Si può utilizzare l'algoritmo di Kruskal, che è corretto, poiché è composto da

1. un'inizializzazione con tempo O(n) che termina sicuramente, in quanto è un ciclo
2. un ordinamento degli archi con costo O(m log(m)), che termina sicuramente, utilizzando un algoritmo di ordinamento che termina (es. mergesort o quicksort)
3. un ciclo per ciascun arco O(m) per ciascuno dei quali è necessario verificare se i due vertici appartengono allo stesso insieme O(log(n)) ⇒ O(m log(n)), operazione che termina sicuramente
4. l'aggiunta dell'arco e l'unione (eventuale) dei due sottoinsiemi, con costo O(log(m)), che termina sicuramente.

e che ha un costo complessivo di esecuzione O(m log(m))

1. gli archi ordinati sono AB(3), BC(3), AC(5), DE(7), BE(8), AE(9), BD(9), CE(10), AD(11), CD(+∞)
2. AB costituisce il primo arco aggiunto all'albero U, e A, B i primi due vertici (nota: sarebbe stato indifferente iniziare con BC, con un esito diverso ma costi uguali). Ora U = {A, B, (AB)}
3. BC è aggiunto, in quanto C non appartiene a U. Ora U = {A, B, C, (AB), (BC)}
4. AC non è aggiunto, in quanto sia A sia C appartengono a U
5. DE è aggiunto - pur non essendo ancora connesso. Ora U = {A, B, C, D, E, (AB), (BC), (DE)}
6. BE è aggiunto, perché B ed E appartengono a due set diversi. Ora U = {A, B, C, D, E, (AB), (BC), (DE), (BE)}
7. Per brevità riportiamo in un solo passaggio AE, BD, CE, AD, CD, che non sono inclusi.

Le strade da realizzare sono quelle evidenziate in neretto:

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:

Svolgimento

1. l'algoritmo restituisce l'insieme con i gradi più bassi possibile di elementi non collegati tra loro
2. l'algoritmo è corretto, perché, essendo composto da due cicli for innestati, termina sicuramente
3. la complessità è data da
   1. ordinamento O(n log(n))
   2. un ciclo Θ(n), che richiama un altro ciclo Θ(n), quindi il costo complessivo è Θ(n²)
   3. la ricerca dell'arco, che a seconda dell'implementazione può essere O(n) o O(log(n))
   4. la complessità totale è quindi O(n log(n)) + Θ(n²) + O(n) ⇒ O(n²)
4. L'esecuzione:
   1. Si considera l'elemento 6: A è vuoto, quindi MyFunction restituisce true e l'elemento viene aggiunto ad A
   2. Si considera l'elemento 1: A contiene solo 6, che non è collegato a 1. L'elemento è quindi aggiunto.
   3. Si considera l'elemento 5: non è collegato ad alcun vertice in A, quindi l'elemento è aggiunto.
   4. Si considera l'elemento 2: è collegato a 1, che è presente in A, quindi l'elemento non è aggiunto.
   5. Si considera l'elemento 4: è collegato a 5 e 6, che sono presente in A, quindi l'elemento non è aggiunto.
   6. Si considera l'elemento 3: è collegato a 1 e a 5, che sono presente in A, quindi l'elemento non è aggiunto.
   7. Il risultato finale è che A contiene 1, 5, 6.

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:

Risposta

L'algoritmo è trattato nella lezione 10 di Pelillo, in cui si parla del risultato di un prodotto tra la matrice di adiacenza e se stessa, e dei successivi prodotti tra la matrice e il risultato precedente.

Una volta terminato la prima serie di cicli annidati, di costo O(n³), si verifica con un'altra serie di cicli annidati, di costo O(n²), se esistono archi in comune. Se esistono (confronto alla riga 11), il grafo ha almeno un ciclo di lunghezza 3 vertici.
Il costo complessivo è O(n³) + O(n²), quindi O(n³).

Il comportamento si basa su matrice di adiacenza e matrice di appoggio.

Le matrici di adiacenza sono:

e  per il secondo grafo

Una volta terminati le 64 esecuzioni (4 x 4 x 4) della riga 7, si ottengono le seguenti matrici:

Questa matrice è "complementare" a quella del primo grafo, che infatti non presenta cicli.

Questa seconda matrice ha in comune con la seconda matrice di adiacenza i tre archi ((1, 2), (2, 3), (3, 1)) che costituiscono il ciclo.

Definizioni

Taglio

Un taglio è una suddivisione dell'insieme dei vertici V in due sottoinsiemi tali che V₁∈G₁ e V₂∈G₂, inoltre V₁∩V₂ = ∅ e V₁∪V₂ = V.

Attraversamento

Un arco E attraversa un taglio se E(u, v) con u∈G₁ e v∈G₂ cioè se i due vertici appartengono ciascuno a uno dei due insiemi determinati dal taglio.

Rispetto

Dato un sottoinsieme di vertici A ⊆ G si dice che un taglio rispetta l'insieme se nessuno dei suoi archi lo attraversa.

Arco leggero

Si dice leggero l'arco (o gli archi) che, dato un insieme di archi con una proprietà, ha il valore minimo per quella proprietà. Tipicamente si usa chiamare arco leggero quello con valore più basso tra quelli che attraversano un taglio.

Arco sicuro

Dato un grafo G con un taglio (S, V-S), un insieme A che sia rispettato dal taglio, un arco leggero che attraversa (S, V-S) è detto sicuro.

MST

Sta per Minimum Spanning Tree, o albero di copertura minimo. Rappresenta l'albero i cui archi sono quelli meno pesanti possibile.

Teorema fondamentale dei MTS

SIa G = (V, E) un grafo non orientato e connesso e sia w: E → R. Siano inoltre date le seguenti ipotesi:

• A è un insieme di archi tale che A ⊆ E e che A ⊆ MST (che chiameremo T)
• sia (S, V\S) un taglio che rispetta A, ovvero il taglio non attraversa alcun arco di A o viceversa;
• sia (u,v) ∈ E, tale che sia leggero e che attraversa il taglio (S, V\S), ovvero che sia quello di peso minimo tra gli archi che attraversano il taglio

Allora l'arco (u,v) è sicuro per A.

Kruskal

L'algoritmo di Kruskal crea tanti alberi quanti sono i vertici, poi li unisce se non fanno parte della stessa foresta. L'unione avviene ordinando gli archi per peso dal più piccolo, così quando (se) avviene l'unione si memorizza l'arco sicuro di volta in volta.

1. A = ∅; inizializza un insieme vuoto
2. for each v in V, MAKE_SET(v); per ogni vertice nell'insieme dei vertici crea un albero (qui chiamato set)
3. for E order by w; ordina gli elementi di E per peso (w = weight)
4. for each e(u, v) in E
   1. if FIND_SET(u) ≠ FIND_SET(v); se non appartengono allo stesso albero
      1. A ← A ∪ {(u,v)}; si aggiunge l'arco all'insieme degli archi
      2. UNION(u, v); ora u e v fanno parte dello stesso albero
   2. ; se u e v appartengono allo stesso set non fa niente, perché appartengono già allo stesso albero

Domande

L'algoritmo converge? Sì, perché è composto solo da due cicli for, che per definizione convergono.

L'algoritmo è corretto? Sì, perché rispecchia quello che prescrive il teorema master degli MST.

Qual è la complessità dell'algoritmo?

1: O(1)

2: Θ(v) // inizializzazione

3: O(a log a) // ordinamento

4: O(a) // ciclo for

4.1: O(log a) // find set

4.2: O(1) // union

O(1) + O(v) + O(a log a) + O(a log a) + O(1) ⇒ O(a log a), dato che a domina su n e 1 è costante

Prim

L'algoritmo di Prim utilizza due strutture dati aggiuntive: per ogni vertice aggiunge un'informazione sul vertice "padre" π(v) e inserisce ogni vertice in un min-heap binario.

Inizializza tutti i vertici in modo che il loro peso sia ∞ e che i padri siano tutti NIL.
Poi estrae il vertice "root" e assegna 0 come peso.

A questo punto il vertice root non è più presente nell'heap (l'estrazione da un heap binario ha costo di Θ(n)).
A ogni vertice adiacente viene assegnato un peso pari all'arco che lo congiunge al nodo corrente, a meno che il vertice non abbia già un peso e che questo sia minore dell'arco.
Si estrae dall'heap l'elemento minore o - a parità di peso - uno a caso tra gli elementi minori.
Potrebbe succedere che lo stesso vertice sia visitato più volte, e che in una visita successiva l'arco abbia un peso minore di quello già attribuito al vertice. In questo caso, il vertice "cambia di padre" e gli viene assegnato il nuovo peso.
L'algoritmo di Prim è quindi

1. Q ← V(G) // assegno all'heap i vertici di G
2. foreach u ∈ Q, key(u) = ∞
3. key(r) = 0