Algoritmi e strutture dati: pacchetto last-minute

Formulari, i passaggi chiave del metodo per ogni argomento e 6 esercizi, con le soluzioni complete in fondo.

Nuovi eserciziTorna al corso

Nella finestra di stampa scegli “Salva come PDF” per conservarne una copia sul tuo dispositivo.

1Formule e metodi

Teoria dei grafi

Lemma delle strette di mano
Σ deg(v) = 2|E|
Grafi completi
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Grafo regolare
|E| = n·k/2
Albero e foresta
|E| = n − 1, |E| = n − c
Foglie di un albero
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Eulero
circuito: tutti i gradi pari; cammino: esattamente 2 gradi dispari
Cicli hamiltoniani in Kn
(n − 1)!/2
Aggiornamento di Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Cammini di lunghezza L
(Mᴸ)ij

Metodo

  1. Scrivi il grado di ogni vertice; la somma dei gradi è il doppio del numero di lati.
  2. Nelle domande su Eulero, verifica che il grafo sia connesso e conta i vertici di grado dispari.
  3. Per gli alberi, usa n − 1 lati e il lemma delle strette di mano.
  4. Per Dijkstra, tieni una tabella delle distanze provvisorie e a ogni passo fissa il vertice non ancora fissato con la distanza minima.
  5. Per un albero di copertura minimo, ordina i lati per peso e salta ogni lato che chiude un ciclo (Kruskal), oppure fai crescere un solo albero a partire da un vertice iniziale (Prim).

2Esercizi

1.Algoritmi e complessitàMedia

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

  1. AO(n)
  2. BO(n log n)
  3. CO(log n)
  4. DO(n²)
2.Algoritmi e complessitàDifficile

Quale algoritmo trova un albero ricoprente minimo aggiungendo ripetutamente l'arco più economico che non forma un ciclo?

  1. AAlgoritmo di Kruskal
  2. BAlgoritmo di Prim a partire da un nodo
  3. CFloyd-Warshall
  4. DAlgoritmo di Dijkstra
3.Strutture datiMedia

Come si trova la chiave minima in un albero binario di ricerca?

  1. ASi visitano tutte le foglie e le si confronta
  2. BSi seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
  3. CSi guarda solo la radice
  4. DSi seguono i figli destri dalla radice finché non c'è più un figlio destro
4.Strutture datiDifficile

La complessità temporale di decrease-key in un heap binario (nota la posizione dell'elemento) è:

  1. AO(1)
  2. BO(n)
  3. CO(n log n)
  4. DO(log n)
5.Teoria dei grafiMedia
ABCDECircuito eulerianoCammino euleriano, nessun circuitonessuna delle due

Il grafo connesso ha un circuito euleriano, un cammino euleriano che non è un circuito, oppure nessuno dei due? Clicca la tua risposta.

|V| = 5|E| = 5
  1. 1Circuito euleriano
  2. 2Cammino euleriano, nessun circuito
  3. 3nessuna delle due
6.Teoria dei grafiDifficile
20181419611183ABCDEFG

L’algoritmo di Prim costruisce un albero di copertura minimo a partire dal vertice F. Clicca il lato che aggiunge come lato numero 3.

partenza: Fk = 3
  1. 1lato AB
  2. 2lato AC
  3. 3lato CE
  4. 4lato DE
  5. 5lato DF
  6. 6lato EF
  7. 7lato GB
  8. 8lato GC
  9. 9lato GD

3Soluzioni

1.Algoritmi e complessità

Risposta: A · O(n)

Perché è questa la risposta

Se la somma è troppo piccola il puntatore sinistro si sposta a destra, se è troppo grande il puntatore destro si sposta a sinistra, quindi ci sono al massimo n passi.

Risposta

A · O(n)
2.Algoritmi e complessità

Risposta: A · Algoritmo di Kruskal

Perché è questa la risposta

Kruskal ordina gli archi per peso e li aggiunge se collegano componenti diverse; Prim fa crescere un unico albero a partire da un vertice iniziale.

Risposta

A · Algoritmo di Kruskal
3.Strutture dati

Risposta: B · Si seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro

Perché è questa la risposta

Il nodo più a sinistra non ha chiavi minori nell'albero, quindi è il minimo; il costo è proporzionale all'altezza.

Risposta

B · Si seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
4.Strutture dati

Risposta: D · O(log n)

Perché è questa la risposta

Dopo aver diminuito la chiave, l'elemento risale (sift-up) al massimo per l'altezza dell'heap. Gli heap di Fibonacci ottengono decrease-key in O(1) ammortizzato.

Risposta

D · O(log n)
5.Teoria dei grafi

Risposta: Cammino euleriano, nessun circuito

Eulero, Hamilton e alberi: un grafo connesso ha un circuito euleriano (ogni lato una volta, di nuovo al punto di partenza) quando ogni vertice ha grado pari, e un cammino euleriano che non è un circuito quando esattamente due vertici hanno grado dispari; il cammino va allora da un vertice dispari all’altro. Un ciclo hamiltoniano visita ogni vertice una volta; Kn ne ha (n − 1)!/2. Un albero con n vertici ha n − 1 lati, e un grafo connesso con m lati mantiene un albero di copertura dopo aver tolto m − n + 1 lati.

Gradi

deg(A) = 1, deg(B) = 3, deg(C) = 2, deg(D) = 2, deg(E) = 2

Vertici dispari

A, B → 2
Cammino euleriano, nessun circuito

Risposta

Cammino euleriano, nessun circuito

Il cammino euleriano parte da un vertice dispari e termina nell’altro.

6.Teoria dei grafi

Risposta: lato GB

Cammini minimi e alberi di copertura: l’algoritmo di Dijkstra fissa un vertice per passo: il vertice non fissato con la distanza provvisoria minima. La sua distanza è allora definitiva, e ogni vertice adiacente v riceve d(v) = min(d(v), d(u) + w(u, v)). L’algoritmo di Kruskal costruisce un albero di copertura minimo prendendo i lati dal più leggero al più pesante e saltando ogni lato che chiuderebbe un ciclo; l’algoritmo di Prim fa crescere un solo albero da un vertice iniziale aggiungendo sempre il lato più leggero che ne esce. Un albero di copertura di n vertici ha n − 1 lati.

Algoritmo di Prim

1. DF (6)
2. GD (3)
3. GB (1)
4. GC (8)
5. EF (11)
6. AC (18)

lato numero 3

GB

Risposta

lato GB

ExamProblems · examproblems.com/courses/data-structures-and-algorithms