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 soluzione della ricorrenza T(n) = T(n/2) + O(1)?

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

Qual è la complessità temporale di: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lavoro O(1)?

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n √n)
3.Strutture datiMedia

Una tabella hash di dimensione 7 usa h(k) = k mod 7 e la scansione lineare. Dopo aver inserito 10, dove viene memorizzato 17?

  1. AAll'indice 6
  2. BAll'indice 4
  3. CAll'indice 0
  4. DAll'indice 3
4.Strutture datiDifficile

Nell'algoritmo di Kruskal per l'albero ricoprente minimo, a che cosa serve la struttura union-find?

  1. AA memorizzare la distanza corrente di ogni vertice dalla sorgente durante la visita
  2. BA ordinare gli archi per peso
  3. CA verificare se i due estremi di un arco sono già collegati
  4. DA scegliere il vertice di partenza
5.Teoria dei grafiMedia

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

|V| = 20|E| = 25
k =
6.Teoria dei grafiDifficile
12513148119ABCDEF

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: A · O(log n)

Perché è questa la risposta

Il problema si dimezza a ogni passo con lavoro costante per passo, quindi ci sono circa log₂ n passi.

Risposta

A · O(log n)
2.Algoritmi e complessità

Risposta: B · O(n log n)

Perché è questa la risposta

Il totale è n / 1 + n / 2 + ... + n / n = n × Hn, e il numero armonico Hn è Θ(log n).

Risposta

B · O(n log n)
3.Strutture dati

Risposta: B · All'indice 4

Perché è questa la risposta

10 mod 7 = 3 e 17 mod 7 = 3; l'indice 3 è occupato, quindi la scansione lineare prova la posizione successiva, l'indice 4.

Risposta

B · All'indice 4
4.Strutture dati

Risposta: C · A verificare se i due estremi di un arco sono già collegati

Perché è questa la risposta

Find indica se entrambi gli estremi sono nella stessa componente; in caso contrario l'arco viene aggiunto e union fonde le componenti.

Risposta

C · A verificare se i due estremi di un arco sono già collegati
5.Teoria dei grafi

Risposta: k = 6

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

20 − 1 = 19

Lati da togliere

k = 25 − 19 = 6

Risposta

k = 6
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: 12, C: 5
2. C (5): E: 8
3. E (8): D: 22, F: 19
4. B (12): D: 13
5. D (13)
6. F (19)

passo 5

D

Risposta

D

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