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

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

  1. AUn albero ricoprente minimo in O(E log V)
  2. BI cammini minimi da un vertice sorgente a tutti gli altri in O(V + E)
  3. CI cammini minimi tra tutte le coppie di vertici in O(V³)
  4. DUn ordinamento topologico in O(V²)
2.Algoritmi e complessitàDifficile

Che cosa ha stabilito il teorema di Cook–Levin?

  1. AIl problema della fermata è indecidibile
  2. BP è diverso da NP
  3. CIl problema della soddisfacibilità booleana (SAT) è NP-completo
  4. DOgni problema NP si può risolvere in tempo esponenziale
3.Strutture datiMedia

Quale condizione di bilanciamento mantiene un albero AVL in ogni nodo?

  1. AOgni nodo è colorato di rosso o di nero
  2. BTutte le foglie sono esattamente alla stessa profondità
  3. CLe altezze dei sottoalberi sinistro e destro differiscono al massimo di 1
  4. DI due sottoalberi di ogni nodo contengono esattamente lo stesso numero di nodi
4.Strutture datiDifficile

La struttura union-find (insiemi disgiunti) con unione per rango e compressione dei cammini ha un costo ammortizzato per operazione di:

  1. AO(n)
  2. BO(α(n)), l'inversa della funzione di Ackermann, praticamente costante
  3. CO(n²)
  4. DEsattamente O(log n)
5.Teoria dei grafiMedia

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

|V| = 13|E| = 15
k =
6.Teoria dei grafiDifficile
6211314121510ABCDEF

Trova il peso totale W di un albero di copertura minimo del grafo pesato.

|V| = 6|E| = 8
W =

3Soluzioni

1.Algoritmi e complessità

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

C · I cammini minimi tra tutte le coppie di vertici in O(V³)
2.Algoritmi e complessità

Risposta: C · Il problema della soddisfacibilità booleana (SAT) è NP-completo

Perché è questa la risposta

Cook e Levin dimostrarono indipendentemente che ogni problema in NP si riduce a SAT in tempo polinomiale, quindi SAT fu il primo problema NP-completo noto.

Risposta

C · Il problema della soddisfacibilità booleana (SAT) è NP-completo
3.Strutture dati

Risposta: C · Le altezze dei sottoalberi sinistro e destro differiscono al massimo di 1

Perché è questa la risposta

Il fattore di bilanciamento (altezza sinistra − altezza destra) deve essere −1, 0 o 1; le rotazioni lo ripristinano dopo inserimenti e cancellazioni.

Risposta

C · Le altezze dei sottoalberi sinistro e destro differiscono al massimo di 1
4.Strutture dati

Risposta: B · O(α(n)), l'inversa della funzione di Ackermann, praticamente costante

Perché è questa la risposta

Con entrambe le ottimizzazioni, le operazioni richiedono un tempo ammortizzato O(α(n)); α(n) ≤ 4 per qualsiasi n realistico.

Risposta

B · O(α(n)), l'inversa della funzione di Ackermann, praticamente costante
5.Teoria dei grafi

Risposta: k = 3

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

13 − 1 = 12

Lati da togliere

k = 15 − 12 = 3

Risposta

k = 3
6.Teoria dei grafi

Risposta: W = 38

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 Kruskal

BC (1): prendi
AC (2): prendi
AB (6): salta, chiude un ciclo
EF (10): prendi
DE (12): prendi
BD (13): prendi

Peso totale

W = 1 + 2 + 10 + 12 + 13 = 38

Risposta

W = 38

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