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

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

  1. AEsponenziale
  2. BCostante
  3. CLogaritmica
  4. DLineare
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 Prim a partire da un nodo
  2. BAlgoritmo di Kruskal
  3. CFloyd-Warshall
  4. DAlgoritmo di Dijkstra
3.Strutture datiMedia

In un min-heap binario memorizzato in un array (indici a partire da 0), i figli del nodo all'indice i si trovano a:

  1. Ai + 1 e i + 2
  2. B2i e 2i + 1
  3. Ci/2 e i/2 + 1
  4. D2i + 1 e 2i + 2
4.Strutture datiDifficile

L'algoritmo di Kahn per l'ordinamento topologico rimuove ripetutamente i vertici con grado entrante 0. Quale struttura contiene questi vertici?

  1. AUna coda (o una collezione qualsiasi) dei vertici con grado entrante 0
  2. BUna pila di tutti gli archi visitati
  3. CUna matrice di adiacenza che registra quali vertici sono già stati rimossi
  4. DUn max-heap ordinato per grado uscente
5.Teoria dei grafiMedia

Un grafo connesso ha 15 vertici e 23 lati. Quanti lati k vanno tolti per ottenere un albero di copertura?

|V| = 15|E| = 23
k =
6.Teoria dei grafiDifficile
5324121122ABCDEF

Usa l’algoritmo di Dijkstra per trovare la lunghezza d(F) del cammino minimo da A a F nel grafo pesato.

partenza: Aarrivo: F
d(F) =

3Soluzioni

1.Algoritmi e complessità

Risposta: A · Esponenziale

Perché è questa la risposta

L'albero delle chiamate cresce all'incirca come φⁿ (circa 1,618ⁿ). La memoizzazione la riduce a O(n).

Risposta

A · Esponenziale
2.Algoritmi e complessità

Risposta: B · 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

B · Algoritmo di Kruskal
3.Strutture dati

Risposta: D · 2i + 1 e 2i + 2

Perché è questa la risposta

Negli array con indici da 0, il figlio sinistro è a 2i + 1, il figlio destro a 2i + 2 e il genitore a ⌊(i − 1)/2⌋.

Risposta

D · 2i + 1 e 2i + 2
4.Strutture dati

Risposta: A · Una coda (o una collezione qualsiasi) dei vertici con grado entrante 0

Perché è questa la risposta

I vertici pronti si tengono in una coda; rimuoverne uno riduce il grado entrante dei suoi vicini, e quelli che arrivano a 0 vengono aggiunti, con un tempo O(V + E).

Risposta

A · Una coda (o una collezione qualsiasi) dei vertici con grado entrante 0
5.Teoria dei grafi

Risposta: k = 9

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.

Lati di un albero di copertura

15 − 1 = 14

Lati da togliere

k = 23 − 14 = 9

Risposta

k = 9
6.Teoria dei grafi

Risposta: d(F) = 9

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.

Dijkstra passo per passo

Ogni riga: il vertice fissato, la sua distanza definitiva e i vertici adiacenti la cui distanza migliora.

A (0): B: 5, C: 3
C (3): E: 15
B (5): D: 9, E: 7
E (7): F: 9
D (9)
F (9)

Cammino minimo

A → B → E → F
d(F) = 9

Risposta

d(F) = 9

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