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

Perché nell'O grande la base del logaritmo di solito si omette, come in O(log n)?

  1. ATutti i logaritmi in informatica hanno base 10, quindi è sottintesa
  2. BLogaritmi con basi diverse differiscono solo per un fattore costante
  3. CI logaritmi sono sempre arrotondati a interi
  4. DLa base conta solo per n piccolo
2.Algoritmi e complessitàDifficile

Quale limite è corretto per log(n!)?

  1. AΘ(n log n)
  2. BΘ(n²)
  3. CΘ(log n)
  4. DΘ(n)
3.Strutture datiMedia

Come si inserisce un nuovo elemento in un heap binario?

  1. ALo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap
  2. BLo si inserisce nella posizione ordinata spostando di un posto a destra tutti gli elementi più grandi
  3. CSi ricostruisce da zero l'intero heap
  4. DLo si pone nella radice e lo si fa scendere
4.Strutture datiDifficile

Senza unione per rango né compressione dei cammini, qual è il costo nel caso peggiore di una singola find in una struttura union-find con n elementi?

  1. AO(α(n))
  2. BO(n)
  3. CO(log n)
  4. DO(1)
5.Teoria dei grafiMedia

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

|V| = 11|E| = 20
k =
6.Teoria dei grafiDifficile
ABCDE

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

M = matrice di adiacenzaL = 3
N =

3Soluzioni

1.Algoritmi e complessità

Risposta: B · Logaritmi con basi diverse differiscono solo per un fattore costante

Perché è questa la risposta

Cambiare base moltiplica il logaritmo per una costante, e l'O grande ignora i fattori costanti.

Risposta

B · Logaritmi con basi diverse differiscono solo per un fattore costante
2.Algoritmi e complessità

Risposta: A · Θ(n log n)

Perché è questa la risposta

log(n!) ≤ n log n, e gli n / 2 fattori più grandi danno log(n!) ≥ (n / 2) log(n / 2); per questo l'ordinamento per confronti richiede Ω(n log n).

Risposta

A · Θ(n log n)
3.Strutture dati

Risposta: A · Lo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap

Perché è questa la risposta

Aggiungere alla fine mantiene l'albero completo; gli scambi con il genitore ripristinano l'ordine in O(log n) passi.

Risposta

A · Lo si pone alla fine dell'array e lo si fa risalire finché viola la proprietà di heap
4.Strutture dati

Risposta: B · O(n)

Perché è questa la risposta

Le unioni ingenue possono collegare gli alberi in una lunga catena, quindi find può dover seguire n − 1 puntatori al genitore; le due euristiche la rendono quasi costante.

Risposta

B · O(n)
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

11 − 1 = 10

Lati da togliere

k = 20 − 10 = 10

Risposta

k = 10
6.Teoria dei grafi

Risposta: N = 2

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

Un altro passo

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

Risposta

N = 2

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