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

Che cosa misura l'analisi ammortizzata?

  1. AIl costo atteso su input casuali
  2. BIl costo medio per operazione su una sequenza di operazioni nel caso peggiore
  3. CIl costo della singola operazione più costosa in un punto qualsiasi della sequenza
  4. DIl costo di un algoritmo sull'input migliore
2.Algoritmi e complessitàDifficile

Quale affermazione su P e NP è corretta?

  1. AOgni problema in P appartiene anche a NP
  2. BÈ stato dimostrato che P ≠ NP
  3. CLe soluzioni dei problemi NP non possono essere verificate rapidamente
  4. DNP significa «non polinomiale»
3.Strutture datiMedia

Come si trova la chiave minima in un albero binario di ricerca?

  1. ASi seguono i figli destri dalla radice finché non c'è più un figlio destro
  2. BSi visitano tutte le foglie e le si confronta
  3. CSi seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
  4. DSi guarda solo la radice
4.Strutture datiDifficile

Inserendo una chiave in un albero AVL il sottoalbero sinistro di un nodo diventa troppo alto, e la nuova chiave è finita nel sottoalbero sinistro del suo figlio sinistro (caso sinistra-sinistra). Quale correzione si applica?

  1. ALa ricolorazione del nodo e del figlio
  2. BUna singola rotazione a destra sul nodo sbilanciato
  3. CUna rotazione a sinistra sul figlio, poi una rotazione a destra sul nodo
  4. DUna singola rotazione a sinistra sul nodo sbilanciato
5.Teoria dei grafiMedia

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

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

Quanti cammini di lunghezza 3 vanno da A a 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 · Il costo medio per operazione su una sequenza di operazioni nel caso peggiore

Perché è questa la risposta

L'analisi ammortizzata distribuisce il costo di rare operazioni costose su molte operazioni economiche, dando una media garantita per qualsiasi sequenza.

Risposta

B · Il costo medio per operazione su una sequenza di operazioni nel caso peggiore
2.Algoritmi e complessità

Risposta: A · Ogni problema in P appartiene anche a NP

Perché è questa la risposta

P ⊆ NP: se puoi risolvere un problema rapidamente, puoi verificarne rapidamente una soluzione. Se P = NP è ancora una questione aperta.

Risposta

A · Ogni problema in P appartiene anche a NP
3.Strutture dati

Risposta: C · Si seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro

Perché è questa la risposta

Il nodo più a sinistra non ha chiavi minori nell'albero, quindi è il minimo; il costo è proporzionale all'altezza.

Risposta

C · Si seguono i figli sinistri dalla radice finché non c'è più un figlio sinistro
4.Strutture dati

Risposta: B · Una singola rotazione a destra sul nodo sbilanciato

Perché è questa la risposta

Nel caso sinistra-sinistra una rotazione a destra solleva il figlio sinistro e ripristina il bilanciamento; i casi a zig-zag richiedono una doppia rotazione.

Risposta

B · Una singola rotazione a destra sul nodo sbilanciato
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

11 − 1 = 10

Lati da togliere

k = 16 − 10 = 6

Risposta

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

Un altro passo

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

Risposta

N = 2

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