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

La visita in ampiezza (BFS) su un grafo non pesato trova:

AI cammini minimi in grafi che contengono archi con peso negativo
BL'albero ricoprente minimo
CI cammini minimi in numero di archi dal nodo di partenza
DUn ordinamento topologico in tutti i grafi

2.Algoritmi e complessitàDifficile

2²ⁿ è in O(2ⁿ)?

ANo, perché 2²ⁿ = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce senza limite
BSì, perché i fattori costanti nell'esponente si ignorano sempre nell'O grande
CSì, perché sono entrambi esponenziali
DNo, perché 2²ⁿ cresce più lentamente di 2ⁿ

3.Strutture datiMedia

Un buffer circolare (ring buffer) è comunemente usato per implementare:

AUna coda di dimensione fissa
BUn albero binario di ricerca
CUna funzione hash
DUna visita di un grafo

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 max-heap di dimensione k, di cui si sostituisce la radice quando arriva un valore più piccolo
BUna coda FIFO degli ultimi k valori
CUn array ordinato di tutti gli n valori
DUn min-heap che contiene tutti gli n valori, da cui alla fine si estraggono i k più piccoli

5.Teoria dei grafiMedia

Un albero ha 2 vertici di grado 4, 2 vertici di grado 5, 4 vertici di grado 2, e tutti gli altri suoi vertici sono foglie (grado 1). Quante foglie L ha?

2 × deg 42 × deg 54 × deg 2

L =

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

C · I cammini minimi in numero di archi dal nodo di partenza

2.Algoritmi e complessità

Risposta: A · No, perché 2²ⁿ = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce senza limite

Perché è questa la risposta

Una costante sommata all'esponente dà un fattore costante, ma una costante che moltiplica l'esponente cambia la base e il tasso di crescita.

Risposta

A · No, perché 2²ⁿ = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce senza limite

3.Strutture dati

Risposta: A · Una coda di dimensione fissa

Perché è questa la risposta

Un buffer circolare usa indici di testa e di coda che ripartono dall'inizio, garantendo enqueue e dequeue in O(1) con memoria fissa.

Risposta

A · Una coda di dimensione fissa

4.Strutture dati

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

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

5.Teoria dei grafi

Risposta: L = 12

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.

Lemma delle strette di mano per un albero

L + 26 = 2(L + 8) − 2

L = 12

Risposta

L = 12

Scorciatoia: L = 2 + Σ (d − 2) sui vertici di grado d ≥ 3.

6.Teoria dei grafi

Risposta: d(C) = 10

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: 9, C: 15

B (9): C: 10, G: 19

C (10): E: 14, G: 15

E (14): D: 25, F: 22

G (15): D: 24

F (22)

D (24)

Cammino minimo

A → B → C

d(C) = 10

Risposta

d(C) = 10

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