Progettazione di Algoritmi

Esercizio [grado]    Dimostrare che in un grafo non diretto e connesso G ci sono sempre almeno due nodi che hanno lo stesso grado.

Esercizio [alberi]    Dato un grafo diretto G, si spieghi come un suo nodo u con almeno un arco entrante ed almeno un arco uscente, possa finire nella foresta DFS prodotta da una visita in profondità di G, in un albero DFS che contiene solo u.

Esercizio [Hamiltoniano]    Un cammino Hamiltoniano è un cammino (orientato) che passa per ogni nodo esattamente una volta. Descrivere un algoritmo che dato un grafo diretto e aciclico G, determina se G contiene un cammino Hamiltoniano. La complessità dell’algoritmo deve essere O(n + m).

Esercizio [lontani]    Descrivere un algoritmo che, dato un grafo diretto G e un suo nodo s, restituisce il numero dei nodi raggiungibili da s che si trovano alla massima distanza da s. L'algoritmo deve avere complessità O(n+m).

Esercizio [copertura]    Dato un grafo non diretto G si vuole trovare un suo albero di copertura. Si propone il seguente algoritmo:

INPUT un grafo non diretto G = (V, E)
SOL <- ∅
R <- {s} dove s è un qualsiasi nodo di V
WHILE E ≠ ∅ DO
    Estrai un qualsiasi arco {u, v} da E
    IF |{u, v} ∩ R| = 1  THEN
        SOL <- SOL ∪ {{u, v}}
        R <- R ∪ {u, v}
OUTPUT SOL
  1. Dare un'implementazione dell'algoritmo di complessità O(n + m).
  2. Dire se l'algoritmo proposto risolve il problema e in caso affermativo spiegare perché l'algoritmo è corretto (meglio ancora dimostrarne la correttezza) mentre in caso negativo fornire un controesempio.

Esercizio [MaxST]    Si consideri l'algoritmo di Prim modificato in modo che venga scelto ogni volta l’arco di peso massimo anziché quello di peso minimo. Provare che l'algoritmo trova l'albero di copertura di peso massimo o fornire un controesempio.

Esercizio [accoppiamento]    Un accoppiamento in un grafo non diretto G è un sottoinsieme di archi disgiunti di G. Dato G si vuole trovare un accoppiamento di massima cardinalità. Viene proposto il seguente algoritmo greedy

INPUT un grafo non diretto G = (V, E)
SOL ← ∅
WHILE E ≠ ∅ DO
    Tra gli archi in E prendi un arco {x, y} per cui il nodo x ha grado minimo
    SOL <- SOL ∪ {{x, y}}
    Cancella da E tutti gli archi che hanno per estremo x o y
OUTPUT SOL
  1. Dare un'implementazione dell'algoritmo di complessità O(n2).
  2. Mostrare che l'algoritmo non produce necessariamente un accoppiamento di massima cardinalità.
  3. Mostrare che nel caso di grafi aciclici l'algoritmo è corretto.

Esercizio [conta]    Dato un grafo diretto e pesato G ed un suo nodo s, l'algoritmo di Dijkstra calcola l'albero dei cammini minimi da s ad un qualsiasi altro nodo di G raggiungibile da s. In generale, tra il nodo s e un altro nodo u di G può esserci più di un cammino minimo. Dare lo pseudo-codice di un algoritmo che dato un grafo diretto G ed un suo nodo s, calcoli per ogni nodo u il numero di cammini distinti di peso minimo da s a u. Suggerimento: modificare l'algoritmo di Dijkstra. Discutere la complessità dell’algoritmo.

Esercizio [CD]    Si supponga di voler creare un CD di brani musicali contente il maggior numero di brani dalla nostra collezione di musica. Si assuma che la somma delle dimensioni dei brani nella collezione ecceda la capacità del CD. Il problema sta nel selezionare un sottoinsieme degli n brani musicali che abbia cardinalità massima e che possa essere memorizzato sul CD.

  1. Descrivere un algoritmo greedy che risolve il problema, provarne la correttezza e valutare la complessità di una sua efficiente implementazione.
  2. Si supponga di volere anche che i brani da memorizzare appartengano a cantanti differenti. Descrivere un algoritmo per questo problema.

Esercizio [continuo]    Sia V un vettore di n interi. Si dice che V è continuo se per ogni indice i, 1 ≤ in − 1, vale |V[i + 1] − V[i]| ≤ 1. Si dice zero del vettore un indice k tale che V[k] = 0.

  1. Dato un vettore V di n ≥ 2 interi continuo tale che V[1] < 0 e V[n] > 0, provare che V ha almeno uno zero.
  2. Descrivere un algoritmo che, dato un vettore V di n ≥ 2 interi continuo e tale che V[1] < 0 e V[n] > 0, trovi uno zero in tempo O(logn).

Esercizio [somma]    Sia A un vettore di n interi e x un intero. Descrivere un algoritmo che trovi, se esiste, una coppia di indici i, j tali che A[i] + A[j] = x. L'algoritmo deve avere complessità O(nlogn).

Esercizio [sottosequenza]    Dare lo pseudo-codice di un algoritmo che data una sequenza di interi S trova una sottosequenza crescente di S di somma massima. Discutere la correttezza dell'algoritmo. L'algoritmo deve avere complessità O(n2).

Esercizio [prodotto]    Dato un vettore V di n numeri razionali si vuole trovare un sottovettore il cui prodotto degli elementi sia massimo. Descrivere un algoritmo che risolve il problema in tempo O(n) e discuterne la correttezza.

Esercizio [sistemazioni]    Si supponga di avere n elementi identificati dagli interi 1,…,n, da sistemare in p posizioni {1,2,…,p} con np. Una sistemazione S è lecita se vale S[i] < S[i + 1] dove S[i] è la posizione assegnata all’elemento i. Si dispone di una matrice n×p di interi non necessariamente positivi dove M[i, j] rappresenta il valore che si ottiene assegnando la posizione j all'elemento i. Il valore di una sistemazione è dato dalla somma dei valori ottenuti dagli n posizionamenti scelti.

  1. Descrivere un algoritmo che in tempo O(np) calcola il valore massimo che si può ottenere con sistemazioni lecite. Discutere la correttezza dell'algoritmo.
  2. Modificare l’algoritmo in modo che, con un tempo aggiuntivo O(n), venga trovata una sistemazione lecita di valore massimo.

Esercizio [esami]    Sia dato un insieme di n esami identificati dagli interi 1,2,…,n. Ogni esame i vale ci crediti ed ha un grado di difficoltà di. Ogni studente può redigere il proprio piano di studio individuale scegliendo nella lista degli esami attivati un sottoinsieme di esami tali che la somma dei crediti corrispondenti sia almeno C. Descrivere un algoritmo che redige un piano di studi regolare di difficoltà (la somma dei gradi di difficoltà degli esami del piano) minima in tempo O(nC). Discutere la correttezza dell'algoritmo.

Esercizio [pari]    Dare lo pseudo-codice di un algoritmo che, preso in input un intero n, stampi tutti i sottoinsiemi di {1,2,…,n} che contengono almeno un elemento che è un numero pari. La complessità dell’algoritmo deve essere O(nS(n)), dove S(n) è il numero di sottoinsiemi da stampare.

Esercizio [abc]    Dare lo pseudo-codice di un algoritmo che, preso in input un intero n, stampi tutte le stringhe di lunghezza n sull'alfabeto {a, b, c} tali che il numero di occorrenze di a è minore o uguale al numero di occorrenze di b che a sua volta è minore o uguale al numero di occorrenze di c. Ad esempio se n = 3 allora l'algoritmo deve produrre (non necessariamente in quest'ordine): ccc, bcc, cbc, ccb, abc, bac, bca, acb, cab e cba. La complessità dell'algoritmo deve essere O(nS(n)), dove S(n) è il numero di stringhe da stampare.

Esercizio [matrici]    Dare lo pseudo-codice di un algoritmo che, preso in input un intero n, stampi tutte le matrici n×n con valori in {a, b, c} tali che due elementi adiacenti (per riga o colonna) abbiano valori differenti. Ad esempio se n = 2, le matrici da stampare sono:

ab  ab  ab  ac  ac  ac  ba  ba  ba  bc  bc  bc  ca  ca  ca  cb  cb  cb 
ba  bc  ca  ca  cb  ba  ab  ac  cb  cb  ca  ab  ac  ab  bc  bc  ba  ac

La complessità dell'algoritmo deve essere O(n2S(n)), dove S(n) è il numero di matrici da stampare.