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

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

  1. AΩ(n)
  2. BΩ(n log n)
  3. CΩ(log n)
  4. DΩ(n²)
2.Algoritmi e complessitàDifficile

Il problema dello zaino 0/1 risolto con la programmazione dinamica richiede tempo O(nW). Perché si dice pseudo-polinomiale?

  1. APerché l'algoritmo è randomizzato e il suo tempo di esecuzione varia a ogni input
  2. BPerché funziona solo per W = 0
  3. CPerché n è sempre piccolo
  4. DW è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W
3.Strutture datiMedia

Un nodo di un albero binario di ricerca ha un sottoalbero destro. Dove si trova il suo successore in ordine?

  1. ANel nodo più a destra del suo sottoalbero sinistro
  2. BNel suo figlio destro, sempre
  3. CNel nodo più a sinistra del suo sottoalbero destro
  4. DNel suo genitore, sempre
4.Strutture datiDifficile

Perché i database usano spesso B+-alberi anziché semplici B-alberi per gli indici?

  1. AI B+-alberi memorizzano i dati solo nella radice
  2. BI B+-alberi non devono essere bilanciati
  3. CTutti i record stanno in foglie collegate, il che rende efficienti le scansioni per intervallo
  4. DI B+-alberi usano nodi interni binari, il che riduce le letture da disco
5.Teoria dei grafiMedia

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

2 × deg 34 × deg 2
L =
6.Teoria dei grafiDifficile
ABCDEF

Quanti cammini di lunghezza 3 vanno da C a B? Un cammino può ripetere vertici e lati. Chiama il numero N.

M = matrice di adiacenzaL = 3
N =

3Soluzioni

1.Algoritmi e complessità

Risposta: B · Ω(n log n)

Perché è questa la risposta

Qualsiasi ordinamento per confronti richiede almeno log₂(n!) ≈ n log n confronti nel caso peggiore. Il counting sort lo batte perché non effettua confronti.

Risposta

B · Ω(n log n)
2.Algoritmi e complessità

Risposta: D · W è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W

Perché è questa la risposta

Il tempo di esecuzione è polinomiale nel valore di W ma esponenziale nella sua lunghezza (log W bit); lo zaino 0/1 è NP-completo.

Risposta

D · W è un numero, quindi il tempo è esponenziale nel numero di bit usati per scrivere W
3.Strutture dati

Risposta: C · Nel nodo più a sinistra del suo sottoalbero destro

Perché è questa la risposta

Tutte le chiavi maggiori vicine al nodo si trovano nel suo sottoalbero destro, e la più piccola di queste è il nodo più a sinistra di quel sottoalbero.

Risposta

C · Nel nodo più a sinistra del suo sottoalbero destro
4.Strutture dati

Risposta: C · Tutti i record stanno in foglie collegate, il che rende efficienti le scansioni per intervallo

Perché è questa la risposta

In un B+-albero i nodi interni servono solo a guidare la ricerca e le foglie sono collegate in ordine di chiave, quindi un'interrogazione su intervallo trova la prima chiave e poi scorre lungo le foglie.

Risposta

C · Tutti i record stanno in foglie collegate, il che rende efficienti le scansioni per intervallo
5.Teoria dei grafi

Risposta: L = 4

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.

Lemma delle strette di mano per un albero

L + 14 = 2(L + 6) − 2
L = 4

Risposta

L = 4

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

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

Un altro passo

(M³)CB = 0·1 + 2·0 + 2·0 + 1·1 + 0·1 + 1·0 = 1

Risposta

N = 1

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