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

Quanti livelli ha la ricorsione del merge sort per un array di n elementi?

  1. ACirca n
  2. BCirca √n
  3. CCirca log₂ n
  4. DCirca n / 2
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é funziona solo per W = 0
  2. BPerché l'algoritmo è randomizzato e il suo tempo di esecuzione varia a ogni input
  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 albero binario ha radice 1 con figlio sinistro 2 e figlio destro 3; il nodo 2 ha figli 4 (sinistro) e 5 (destro). Qual è la visita in postordine?

  1. A1 2 4 5 3
  2. B4 5 2 3 1
  3. C5 4 3 2 1
  4. D4 2 5 1 3
4.Strutture datiDifficile

Quale garanzia danno le regole degli alberi rosso-neri sull'altezza di un albero con n chiavi?

  1. AL'altezza è al massimo n / 2
  2. BL'altezza è al massimo log2 n + 1
  3. CL'altezza è al massimo 2 log2(n + 1)
  4. DL'altezza è esattamente log2 n
5.Teoria dei grafiMedia

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

3 × deg 34 × deg 42 × deg 54 × deg 2
L =
6.Teoria dei grafiDifficile
148451328134ABCDEF

L’algoritmo di Dijkstra parte da A. Clicca il vertice che viene fissato (reso permanente) al passo 5; A stesso è il passo 1.

partenza: Apasso 5
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F

3Soluzioni

1.Algoritmi e complessità

Risposta: C · Circa log₂ n

Perché è questa la risposta

Dimezzare da n fino a 1 richiede circa log₂ n livelli, e ogni livello svolge O(n) lavoro di fusione, da cui O(n log n).

Risposta

C · Circa 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: B · 4 5 2 3 1

Perché è questa la risposta

La visita in postordine elabora 4 e 5 prima di 2, poi 3 e infine la radice 1.

Risposta

B · 4 5 2 3 1
4.Strutture dati

Risposta: C · L'altezza è al massimo 2 log2(n + 1)

Perché è questa la risposta

Ogni cammino ha lo stesso numero di nodi neri e i nodi rossi non possono essere adiacenti, quindi il cammino più lungo è al massimo il doppio del più corto, il che dà un'altezza O(log n).

Risposta

C · L'altezza è al massimo 2 log2(n + 1)
5.Teoria dei grafi

Risposta: L = 19

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 + 43 = 2(L + 13) − 2
L = 19

Risposta

L = 19

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

6.Teoria dei grafi

Risposta: D

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

1. A (0): B: 14, C: 8
2. C (8): B: 12, E: 21
3. B (12): D: 17, E: 16
4. E (16): F: 29
5. D (17): F: 25
6. F (25)

passo 5

D

Risposta

D

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