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

Qual è la complessità temporale del calcolo dell'n-esimo numero di Fibonacci con una tabella bottom-up?

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

Perché qualsiasi ricerca basata su confronti in un array ordinato richiede Ω(log n) confronti nel caso peggiore?

  1. AOgni confronto richiede un tempo logaritmico
  2. BLa ricerca binaria è l'unico algoritmo possibile e richiede log₂ n confronti
  3. CUn albero di decisione con n esiti possibili deve avere profondità almeno log₂ n
  4. DOgni elemento deve essere confrontato almeno una volta
3.Strutture datiMedia

In un min-heap binario memorizzato in un array (indici a partire da 0), i figli del nodo all'indice i si trovano a:

  1. Ai + 1 e i + 2
  2. Bi/2 e i/2 + 1
  3. C2i + 1 e 2i + 2
  4. D2i e 2i + 1
4.Strutture datiDifficile

In una tabella hash con indirizzamento aperto, perché la cancellazione avviene spesso con un marcatore «lapide» (tombstone)?

  1. ALe lapidi velocizzano l'hashing
  2. BRende la tabella ordinata
  3. CSvuotare la posizione potrebbe interrompere la sequenza di scansione di altre chiavi
  4. DLe chiavi cancellate devono essere conservate per sempre per motivi di sicurezza, quindi le posizioni non si possono mai riutilizzare
5.Teoria dei grafiMedia

Un grafo connesso ha 8 vertici e 17 lati. Quanti lati k vanno tolti per ottenere un albero di copertura?

|V| = 8|E| = 17
k =
6.Teoria dei grafiDifficile
ABCDEF

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

M = matrice di adiacenzaL = 3
N =

3Soluzioni

1.Algoritmi e complessità

Risposta: C · O(n)

Perché è questa la risposta

Riempire la tabella da 0 a n richiede un'addizione per voce, quindi il lavoro è lineare anziché esponenziale.

Risposta

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

Risposta: C · Un albero di decisione con n esiti possibili deve avere profondità almeno log₂ n

Perché è questa la risposta

Ogni confronto al massimo dimezza l'insieme delle possibilità rimanenti, quindi distinguere n posizioni richiede almeno log₂ n confronti.

Risposta

C · Un albero di decisione con n esiti possibili deve avere profondità almeno log₂ n
3.Strutture dati

Risposta: C · 2i + 1 e 2i + 2

Perché è questa la risposta

Negli array con indici da 0, il figlio sinistro è a 2i + 1, il figlio destro a 2i + 2 e il genitore a ⌊(i − 1)/2⌋.

Risposta

C · 2i + 1 e 2i + 2
4.Strutture dati

Risposta: C · Svuotare la posizione potrebbe interrompere la sequenza di scansione di altre chiavi

Perché è questa la risposta

Se una posizione cancellata diventasse vuota, le ricerche successive potrebbero fermarsi in anticipo e non trovare chiavi collocate più avanti nella catena di scansione.

Risposta

C · Svuotare la posizione potrebbe interrompere la sequenza di scansione di altre chiavi
5.Teoria dei grafi

Risposta: k = 10

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.

Lati di un albero di copertura

8 − 1 = 7

Lati da togliere

k = 17 − 7 = 10

Risposta

k = 10
6.Teoria dei grafi

Risposta: N = 4

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 1
F: 0 0 0 1 1 0

Un altro passo

(M³)CC = 1·1 + 2·1 + 3·0 + 1·0 + 1·1 + 1·0 = 4

Risposta

N = 4

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