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

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

  1. AO(1)
  2. BO(n²)
  3. CO(n)
  4. DO(log n)
2.Algoritmi e complessitàDifficile

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

  1. AX è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale
  2. BX si riduce a un problema in P, e X è in NP
  3. CX è in P, e X si riduce a SAT
  4. DX non ha un algoritmo polinomiale, e X è decidibile
3.Strutture datiMedia

Quanto dura la ricerca di una parola di lunghezza L in un trie con alfabeto fisso?

  1. AO(L × n)
  2. BO(L), indipendentemente da quante parole sono memorizzate
  3. CO(n), dove n è il numero di parole
  4. DO(log n), dove n è il numero di parole
4.Strutture datiDifficile

Qual è il tempo di esecuzione della visita in ampiezza (BFS) su un grafo con V vertici memorizzato come matrice di adiacenza?

  1. AO(V + E)
  2. BO(V)
  3. CO(E log V)
  4. DO(V²)
5.Teoria dei grafiMedia

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

K7
H =
6.Teoria dei grafiDifficile
ABCDEF

Quanti cammini chiusi di lunghezza 2 partono e terminano in F? Un cammino può ripetere vertici e lati. Chiama il numero N.

M = matrice di adiacenzaL = 2
N =

3Soluzioni

1.Algoritmi e complessità

Risposta: C · O(n)

Perché è questa la risposta

La ricorsione arriva a n chiamate di profondità prima di qualsiasi ritorno, e ogni chiamata richiede un record di attivazione (stack frame), quindi usa O(n) spazio.

Risposta

C · O(n)
2.Algoritmi e complessità

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

A · X è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale
3.Strutture dati

Risposta: B · O(L), indipendentemente da quante parole sono memorizzate

Perché è questa la risposta

Ogni carattere seleziona un figlio, quindi una ricerca richiede L passi qualunque sia il numero di parole contenute nel trie.

Risposta

B · O(L), indipendentemente da quante parole sono memorizzate
4.Strutture dati

Risposta: D · O(V²)

Perché è questa la risposta

Ognuno dei V vertici scorre una riga di V elementi, per un totale di O(V²); con le liste di adiacenza la BFS è O(V + E).

Risposta

D · O(V²)
5.Teoria dei grafi

Risposta: H = 360

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 = (7 − 1)!/2 = 720/2 = 360

Risposta

H = 360
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. Kn 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 1 0
C: 1 1 0 0 1 0
D: 0 1 0 0 0 1
E: 0 1 1 0 0 0
F: 0 0 0 1 0 0

Vicini comuni

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

Risposta

N = 1

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