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

Qual è la soluzione della ricorrenza T(n) = T(n − 1) + O(1)?

AO(log n)
BO(2ⁿ)
CO(n²)
DO(n)

2.Algoritmi e complessitàDifficile

Perché l'algoritmo di Dijkstra può dare risultati errati quando alcuni pesi degli archi sono negativi?

AEntra in un ciclo infinito a ogni arco negativo
BFunziona solo sui grafi non orientati
CUn vertice viene considerato definitivo quando è estratto, ma un arco negativo successivo potrebbe ancora dargli un cammino più breve
DI numeri negativi non si possono memorizzare in una coda di priorità

3.Strutture datiMedia

Una visita in ordine (in-order) di un albero binario di ricerca visita le chiavi in:

AOrdine di inserimento
BOrdine sempre decrescente
COrdine per livelli
DOrdine crescente

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)?

AUn array ordinato di tutti gli n valori
BUn max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
CUna coda FIFO degli ultimi k valori
DUn min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli

5.Teoria dei grafiMedia

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

|V| = 6|E| = 8

1Circuito euleriano
2Cammino euleriano, nessun circuito
3nessuna delle due

6.Teoria dei grafiDifficile

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

partenza: Aarrivo: D

d(D) =

3Soluzioni

1.Algoritmi e complessità

Risposta: D · O(n)

Perché è questa la risposta

Ci sono n livelli, ciascuno con lavoro costante, come nella somma ricorsiva di un array.

Risposta

D · O(n)

2.Algoritmi e complessità

Risposta: C · Un vertice viene considerato definitivo quando è estratto, ma un arco negativo successivo potrebbe ancora dargli un cammino più breve

Perché è questa la risposta

Il passo greedy si basa su pesi non negativi perché le distanze estratte siano definitive; quando i pesi possono essere negativi si usa Bellman–Ford.

Risposta

C · Un vertice viene considerato definitivo quando è estratto, ma un arco negativo successivo potrebbe ancora dargli un cammino più breve

3.Strutture dati

Risposta: D · Ordine crescente

Perché è questa la risposta

Visitare il sottoalbero sinistro, poi il nodo e poi il sottoalbero destro restituisce le chiavi del BST in ordine.

Risposta

D · Ordine crescente

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: nessuna delle due

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.

Gradi

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

Vertici dispari

C, D, E, F → 4

nessuna delle due

Risposta

nessuna delle due

6.Teoria dei grafi

Risposta: d(D) = 19

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: 3, C: 10

B (3): G: 11

C (10): E: 24

G (11): D: 19, E: 14

E (14)

D (19): F: 29

F (29)

Cammino minimo

A → B → G → D

d(D) = 19

Risposta

d(D) = 19

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