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

Perché la programmazione dinamica non dà un vero guadagno di velocità per il merge sort?

ALa programmazione dinamica funziona solo sui problemi su grafi, non sugli array
BIl merge sort non ha una struttura ricorsiva
CI suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
DIl merge sort è già O(n)

2.Algoritmi e complessitàDifficile

Quale di questi problemi di soddisfacibilità è noto per essere risolvibile in tempo polinomiale?

ALa soddisfacibilità dei circuiti
B3-SAT, in cui ogni clausola ha esattamente tre letterali
CSAT generale su formule in forma normale congiuntiva
D2-SAT, in cui ogni clausola ha al massimo due letterali

3.Strutture datiMedia

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

ALe altezze dei sottoalberi sinistro e destro differiscono al massimo di 1
BOgni nodo è colorato di rosso o di nero
CI due sottoalberi di ogni nodo contengono esattamente lo stesso numero di nodi
DTutte le foglie sono esattamente alla stessa profondità

4.Strutture datiDifficile

Qual è il vantaggio principale di una skip list rispetto a una lista concatenata ordinata?

AMemorizza le chiavi senza ordine
BNon usa memoria aggiuntiva
CRicerca attesa in O(log n) grazie a più livelli di puntatori in avanti
DRicerca garantita in O(1) perché ogni nodo memorizza un puntatore a tutti gli altri nodi

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| = 7|E| = 10

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

6.Teoria dei grafiDifficile

Quanti cammini di lunghezza 2 vanno da F a D? Un cammino può ripetere vertici e lati. Chiama il numero N.

M = matrice di adiacenzaL = 2

N =

3Soluzioni

1.Algoritmi e complessità

Risposta: C · I suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare

Perché è questa la risposta

Le metà del merge sort sono disgiunte e ciascuna viene risolta una volta; la PD aiuta solo quando i sottoproblemi si ripetono, come in Fibonacci.

Risposta

C · I suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare

2.Algoritmi e complessità

Risposta: D · 2-SAT, in cui ogni clausola ha al massimo due letterali

Perché è questa la risposta

2-SAT è in P (tempo lineare tramite componenti fortemente connesse), mentre 3-SAT è NP-completo.

Risposta

D · 2-SAT, in cui ogni clausola ha al massimo due letterali

3.Strutture dati

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

A · Le altezze dei sottoalberi sinistro e destro differiscono al massimo di 1

4.Strutture dati

Risposta: C · Ricerca attesa in O(log n) grazie a più livelli di puntatori in avanti

Perché è questa la risposta

I livelli casuali permettono alle ricerche di saltare molti nodi, ottenendo un tempo atteso O(log n) per ricerca, inserimento e cancellazione.

Risposta

C · Ricerca attesa in O(log n) grazie a più livelli di puntatori in avanti

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) = 3, deg(C) = 3, deg(D) = 3, deg(E) = 4, deg(F) = 2, deg(G) = 3

Vertici dispari

B, C, D, G → 4

nessuna delle due

Risposta

nessuna delle due

6.Teoria dei grafi

Risposta: N = 1

Gradi: il grado di un vertice è il numero di lati che vi arrivano. Ogni lato ha due estremi, quindi i gradi sommano al doppio del numero di lati: Σ deg(v) = 2|E| (il lemma delle strette di mano). Il numero di vertici di grado dispari è quindi pari. K_n ha n(n − 1)/2 lati, un grafo k-regolare con n vertici ne ha nk/2, e un albero con n vertici ha n − 1 lati.

Matrice di adiacenza

A: 0 1 1 0 0 0

B: 1 0 1 1 0 0

C: 1 1 0 0 0 0

D: 0 1 0 0 1 1

E: 0 0 0 1 0 1

F: 0 0 0 1 1 0

Vicini comuni

(M²)_FD = 0·0 + 0·1 + 0·0 + 1·0 + 1·1 + 0·1 = 1

Risposta

N = 1

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