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) = 2T(n − 1) + O(1)?

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

Quale di questi problemi di soddisfacibilità è noto per essere risolvibile in tempo polinomiale?

  1. A2-SAT, in cui ogni clausola ha al massimo due letterali
  2. B3-SAT, in cui ogni clausola ha esattamente tre letterali
  3. CLa soddisfacibilità dei circuiti
  4. DSAT generale su formule in forma normale congiuntiva
3.Strutture datiMedia

In un min-heap binario memorizzato in un array (indici a partire da 0), i figli del nodo all'indice i si trovano a:

  1. A2i e 2i + 1
  2. Bi/2 e i/2 + 1
  3. C2i + 1 e 2i + 2
  4. Di + 1 e i + 2
4.Strutture datiDifficile

Le chiavi 5, 3, 8, 1 vengono inserite in quest'ordine in un min-heap binario vuoto basato su array. Qual è l'array finale?

  1. A[1, 5, 8, 3]
  2. B[1, 3, 8, 5]
  3. C[1, 3, 5, 8]
  4. D[3, 1, 8, 5]
5.Teoria dei grafiMedia

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

K8
H =
6.Teoria dei grafiDifficile
1116841110915ABCDEF

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

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

3Soluzioni

1.Algoritmi e complessità

Risposta: A · O(2ⁿ)

Perché è questa la risposta

Il numero di chiamate raddoppia a ogni livello e ci sono n livelli, quindi il totale è circa 2ⁿ, come nella Torre di Hanoi.

Risposta

A · O(2ⁿ)
2.Algoritmi e complessità

Risposta: A · 2-SAT, in cui ogni clausola ha al massimo due letterali

Perché è questa la risposta

2-SAT è in P (tempo lineare tramite componenti fortemente connesse), mentre 3-SAT è NP-completo.

Risposta

A · 2-SAT, in cui ogni clausola ha al massimo due letterali
3.Strutture dati

Risposta: C · 2i + 1 e 2i + 2

Perché è questa la risposta

Negli array con indici da 0, il figlio sinistro è a 2i + 1, il figlio destro a 2i + 2 e il genitore a ⌊(i − 1)/2⌋.

Risposta

C · 2i + 1 e 2i + 2
4.Strutture dati

Risposta: B · [1, 3, 8, 5]

Perché è questa la risposta

Dopo 5, 3, 8 l'array è [3, 5, 8]; 1 va all'indice 3, si scambia con il genitore 5 e poi con 3, dando [1, 3, 8, 5].

Risposta

B · [1, 3, 8, 5]
5.Teoria dei grafi

Risposta: H = 2520

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 = (8 − 1)!/2 = 5040/2 = 2520

Risposta

H = 2520
6.Teoria dei grafi

Risposta: E

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: 11, C: 1
2. C (1): B: 7, E: 5
3. E (5): D: 16, F: 14
4. B (7): D: 15
5. F (14)
6. D (15)

passo 3

E

Risposta

E

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