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 visita in ampiezza (BFS) su un grafo non pesato trova:

  1. AUn ordinamento topologico in tutti i grafi
  2. BI cammini minimi in numero di archi dal nodo di partenza
  3. CI cammini minimi in grafi che contengono archi con peso negativo
  4. DL'albero ricoprente minimo
2.Algoritmi e complessitàDifficile

Qual è la complessità temporale della costruzione di un heap binario da n elementi non ordinati con il metodo bottom-up?

  1. AO(n²)
  2. BO(n log n)
  3. CO(log n)
  4. DO(n)
3.Strutture datiMedia

Un albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in postordine?

  1. A4 2 5 1 3
  2. B1 2 4 5 3
  3. C5 4 3 2 1
  4. D4 5 2 3 1
4.Strutture datiDifficile

Devi conservare i k valori più piccoli di un flusso di n numeri usando O(k) memoria. Quale approccio funziona in tempo O(n log k)?

  1. AUna coda FIFO degli ultimi k valori
  2. BUn max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
  3. CUn min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli
  4. DUn array ordinato di tutti gli n valori
5.Teoria dei grafiMedia

Quanti cicli hamiltoniani diversi H ha il grafo completo K4? I cicli che differiscono solo per il vertice iniziale o per il verso contano come lo stesso.

K4
H =
6.Teoria dei grafiDifficile
69248141318ABCDEF

L’algoritmo di Kruskal costruisce un albero di copertura minimo. Clicca il lato che aggiunge come lato numero 4; i lati saltati non contano.

k = 4
  1. 1lato AB
  2. 2lato AC
  3. 3lato BC
  4. 4lato CE
  5. 5lato DE
  6. 6lato DF
  7. 7lato EF
  8. 8lato BE

3Soluzioni

1.Algoritmi e complessità

Risposta: B · I cammini minimi in numero di archi dal nodo di partenza

Perché è questa la risposta

La BFS visita i nodi in ordine di distanza (in archi) dalla sorgente, quindi trova i cammini minimi non pesati in O(V + E).

Risposta

B · I cammini minimi in numero di archi dal nodo di partenza
2.Algoritmi e complessità

Risposta: D · O(n)

Perché è questa la risposta

Sommando i costi di discesa (sift-down) su tutti i livelli si ottiene una serie convergente, quindi heapify viene eseguito in tempo lineare.

Risposta

D · O(n)
3.Strutture dati

Risposta: D · 4 5 2 3 1

Perché è questa la risposta

La visita in postordine elabora 4 e 5 prima di 2, poi 3 e infine la radice 1.

Risposta

D · 4 5 2 3 1
4.Strutture dati

Risposta: B · Un max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo

Perché è questa la risposta

La radice del max-heap è il più grande valore conservato; ogni nuovo valore più piccolo la sostituisce in O(log k), quindi l'heap contiene sempre i k valori più piccoli visti finora.

Risposta

B · Un max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
5.Teoria dei grafi

Risposta: H = 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.

Conta

H = (4 − 1)!/2 = 6/2 = 3

Risposta

H = 3
6.Teoria dei grafi

Risposta: lato DE

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

1. BC (2)
2. CE (4)
3. AB (6)
4. DE (8)
5. EF (13)

lato numero 4

DE

Risposta

lato DE

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