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 esercizi Torna 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(K_n)| = n(n − 1)/2, |E(K_m,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 K_n: (n − 1)!/2
Aggiornamento di Dijkstra: d(v) = min(d(v), d(u) + w(u, v))
Cammini di lunghezza L: (Mᴸ)_ij

Metodo

Scrivi il grado di ogni vertice; la somma dei gradi è il doppio del numero di lati.
Nelle domande su Eulero, verifica che il grafo sia connesso e conta i vertici di grado dispari.
Per gli alberi, usa n − 1 lati e il lemma delle strette di mano.
Per Dijkstra, tieni una tabella delle distanze provvisorie e a ogni passo fissa il vertice non ancora fissato con la distanza minima.
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

Che cosa calcola l'algoritmo di Floyd–Warshall, e con quale velocità?

AUn ordinamento topologico in O(V²)
BI cammini minimi tra tutte le coppie di vertici in O(V³)
CI cammini minimi da un vertice sorgente a tutti gli altri in O(V + E)
DUn albero ricoprente minimo in O(E log V)

2.Algoritmi e complessitàDifficile

Usando il teorema dell'esperto (master theorem), T(n) = 8T(n/2) + O(n²) ha come soluzione:

AΘ(n²)
BΘ(n³)
CΘ(n log n)
DΘ(n² log n)

3.Strutture datiMedia

Qual è il costo di inserire un elemento al centro di un array di n elementi?

AO(log n), per via della ricerca binaria
BO(n), perché gli elementi successivi devono essere spostati
CO(n²), perché ogni elemento si sposta n volte
DO(1), perché l'indice è noto

4.Strutture datiDifficile

Quale garanzia danno le regole degli alberi rosso-neri sull'altezza di un albero con n chiavi?

AL'altezza è al massimo n / 2
BL'altezza è al massimo 2 log₂(n + 1)
CL'altezza è al massimo log₂ n + 1
DL'altezza è esattamente log₂ n

5.Teoria dei grafiMedia

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

|V| = 10|E| = 11

k =

6.Teoria dei grafiDifficile

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

partenza: Aarrivo: C

d(C) =

3Soluzioni

1.Algoritmi e complessità

Risposta: B · I cammini minimi tra tutte le coppie di vertici in O(V³)

Perché è questa la risposta

Floyd–Warshall è un algoritmo di programmazione dinamica che ammette a turno ogni vertice come punto intermedio, con tempo O(V³).

Risposta

B · I cammini minimi tra tutte le coppie di vertici in O(V³)

2.Algoritmi e complessità

Risposta: B · Θ(n³)

Perché è questa la risposta

log₂ 8 = 3 e n² cresce più lentamente di n³, quindi dominano le foglie: Θ(n³).

Risposta

B · Θ(n³)

3.Strutture dati

Risposta: B · O(n), perché gli elementi successivi devono essere spostati

Perché è questa la risposta

Tutti gli elementi dopo il punto di inserimento si spostano di una posizione a destra, il che richiede un tempo proporzionale a n.

Risposta

B · O(n), perché gli elementi successivi devono essere spostati

4.Strutture dati

Risposta: B · L'altezza è al massimo 2 log₂(n + 1)

Perché è questa la risposta

Ogni cammino ha lo stesso numero di nodi neri e i nodi rossi non possono essere adiacenti, quindi il cammino più lungo è al massimo il doppio del più corto, il che dà un'altezza O(log n).

Risposta

B · L'altezza è al massimo 2 log₂(n + 1)

5.Teoria dei grafi

Risposta: k = 2

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; K_n 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

10 − 1 = 9

Lati da togliere

k = 11 − 9 = 2

Risposta

k = 2

6.Teoria dei grafi

Risposta: d(C) = 12

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: 1, C: 13

B (1): C: 12, D: 11, E: 13

D (11): F: 12

C (12)

F (12)

E (13)

Cammino minimo

A → B → C

d(C) = 12

Risposta

d(C) = 12

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