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) = 2T(n/2) + O(1)?

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

2.Algoritmi e complessitàDifficile

Quali due cose bisogna dimostrare per provare che un problema decisionale X è NP-completo?

AX si riduce a un problema in P, e X è in NP
BX non ha un algoritmo polinomiale, e X è decidibile
CX è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale
DX è in P, e X si riduce a SAT

3.Strutture datiMedia

Le chiavi 50, 30, 70, 20, 40 vengono inserite in quest'ordine in un albero binario di ricerca vuoto. Qual è il figlio sinistro di 30?

4.Strutture datiDifficile

Quali sono i costi in tempo e in spazio aggiuntivo dell'inversione sul posto di una lista concatenata semplice?

ATempo O(1) e spazio aggiuntivo O(1)
BTempo O(n) e spazio aggiuntivo O(1)
CTempo O(n log n) e spazio aggiuntivo O(1)
DTempo O(n) e spazio aggiuntivo O(n)

5.Teoria dei grafiMedia

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

K₆

H =

6.Teoria dei grafiDifficile

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

partenza: Aarrivo: F

d(F) =

3Soluzioni

1.Algoritmi e complessità

Risposta: B · O(n)

Perché è questa la risposta

Per il teorema dell'esperto (master theorem) n^{log₂ 2} = n domina il lavoro costante, quindi T(n) = Θ(n), come quando si trova il massimo dividendo a metà.

Risposta

B · O(n)

2.Algoritmi e complessità

Risposta: C · X è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale

Perché è questa la risposta

L'appartenenza a NP mostra che X non è più difficile di NP; la riduzione da un problema NP-completo noto mostra che X è almeno difficile quanto tutto NP.

Risposta

C · X è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale

3.Strutture dati

Risposta: D · 20

Perché è questa la risposta

20 è minore di 50 e minore di 30, quindi diventa il figlio sinistro di 30; 40 diventa il suo figlio destro.

Risposta

D · 20

4.Strutture dati

Risposta: B · Tempo O(n) e spazio aggiuntivo O(1)

Perché è questa la risposta

Mantenendo tre puntatori (precedente, corrente, successivo) si può invertire ogni collegamento in un solo passaggio senza allocare nuovi nodi.

Risposta

B · Tempo O(n) e spazio aggiuntivo O(1)

5.Teoria dei grafi

Risposta: H = 60

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.

Conta

H = (6 − 1)!/2 = 120/2 = 60

Risposta

H = 60

6.Teoria dei grafi

Risposta: d(F) = 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.

Dijkstra passo per passo

Ogni riga: il vertice fissato, la sua distanza definitiva e i vertici adiacenti la cui distanza migliora.

A (0): B: 13

B (13): C: 16, G: 25

C (16): E: 25

E (25): D: 40, F: 38

G (25): D: 26

D (26)

F (38)

Cammino minimo

A → B → C → E → F

d(F) = 38

Risposta

d(F) = 38

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