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 log₂ n
  3. CCirca n
  4. DCirca n / 2
2.Algoritmi e complessitàDifficile

Il problema della fermata dimostra che:

  1. AI cicli andrebbero evitati
  2. BOgni programma prima o poi si ferma
  3. CAlcuni programmi girano più velocemente su computer più veloci, quindi la terminazione dipende dall'hardware
  4. DNessun algoritmo può decidere, per ogni programma e ogni input, se il programma si ferma
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 preordine?

  1. A4 5 2 3 1
  2. B4 2 5 1 3
  3. C1 2 3 4 5
  4. D1 2 4 5 3
4.Strutture datiDifficile

Quale coppia di visite determina sempre un unico albero binario con chiavi distinte?

  1. APreordine e ordine simmetrico (inorder)
  2. BPreordine e postordine
  3. CLa sola visita per livelli
  4. DIl solo preordine
5.Teoria dei grafiMedia

Quanti cicli hamiltoniani diversi H ha il grafo completo K7? I cicli che differiscono solo per il vertice iniziale o per il verso contano come lo stesso.

K7
H =
6.Teoria dei grafiDifficile
913101515337ABCDEF

Usa l’algoritmo di Dijkstra per trovare la lunghezza d(E) del cammino minimo da A a E nel grafo pesato.

partenza: Aarrivo: E
d(E) =

3Soluzioni

1.Algoritmi e complessità

Risposta: B · 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

B · Circa log₂ n
2.Algoritmi e complessità

Risposta: D · Nessun algoritmo può decidere, per ogni programma e ogni input, se il programma si ferma

Perché è questa la risposta

Turing dimostrò che il problema della fermata è indecidibile: supporre che esista un decisore porta a una contraddizione con un programma che fa l'opposto.

Risposta

D · Nessun algoritmo può decidere, per ogni programma e ogni input, se il programma si ferma
3.Strutture dati

Risposta: D · 1 2 4 5 3

Perché è questa la risposta

La visita in preordine visita 1, poi il suo sottoalbero sinistro (2, 4, 5), poi 3; le altre opzioni sono la visita in ordine, in postordine e per livelli.

Risposta

D · 1 2 4 5 3
4.Strutture dati

Risposta: A · Preordine e ordine simmetrico (inorder)

Perché è questa la risposta

Il preordine dà la radice, e la sua posizione nella sequenza in ordine separa i sottoalberi sinistro e destro; preordine e postordine sono ambigui quando un nodo ha un solo figlio.

Risposta

A · Preordine e ordine simmetrico (inorder)
5.Teoria dei grafi

Risposta: H = 360

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.

Conta

H = (7 − 1)!/2 = 720/2 = 360

Risposta

H = 360
6.Teoria dei grafi

Risposta: d(E) = 16

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

Ogni riga: il vertice fissato, la sua distanza definitiva e i vertici adiacenti la cui distanza migliora.

A (0): B: 9, C: 13
B (9): D: 24, E: 16
C (13)
E (16): D: 19, F: 19
D (19)
F (19)

Cammino minimo

A → B → E
d(E) = 16

Risposta

d(E) = 16

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