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

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

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

Un problema è NP-completo se:

  1. AÈ al di fuori di NP ma più difficile di tutti i problemi NP, come il problema della fermata
  2. BÈ risolvibile in tempo polinomiale
  3. CÈ impossibile da risolvere
  4. DAppartiene a NP e ogni problema NP si riduce a esso in tempo polinomiale
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 + 1 e 2i + 2
  2. Bi + 1 e i + 2
  3. Ci/2 e i/2 + 1
  4. D2i e 2i + 1
4.Strutture datiDifficile

Quale affermazione sull'heapsort è corretta?

  1. AOrdina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
  2. BRichiede un albero binario di ricerca come memoria aggiuntiva, quindi usa O(n) memoria extra
  3. CÈ stabile e richiede O(n) memoria aggiuntiva
  4. DRichiede tempo O(n) su qualsiasi input
5.Teoria dei grafiMedia

Un albero ha 3 vertici di grado 3, 3 vertici di grado 4, 4 vertici di grado 2, e tutti gli altri suoi vertici sono foglie (grado 1). Quante foglie L ha?

3 × deg 33 × deg 44 × deg 2
L =
6.Teoria dei grafiDifficile
13410187152ABCDE

Trova il peso totale W di un albero di copertura minimo del grafo pesato.

|V| = 5|E| = 7
W =

3Soluzioni

1.Algoritmi e complessità

Risposta: C · O(n log n + k log n)

Perché è questa la risposta

L'ordinamento costa O(n log n) e ogni query O(log n); questo batte k scansioni lineari (O(nk)) quando k è grande.

Risposta

C · O(n log n + k log n)
2.Algoritmi e complessità

Risposta: D · Appartiene a NP e ogni problema NP si riduce a esso in tempo polinomiale

Perché è questa la risposta

I problemi NP-completi sono i più difficili in NP; un algoritmo polinomiale per uno di essi ne darebbe uno per tutto NP.

Risposta

D · Appartiene a NP e ogni problema NP si riduce a esso in tempo polinomiale
3.Strutture dati

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

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

Risposta: A · Ordina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile

Perché è questa la risposta

L'heapsort costruisce un max-heap ed estrae il massimo n volte all'interno dello stesso array; gli scambi a lunga distanza possono riordinare chiavi uguali.

Risposta

A · Ordina sul posto in tempo O(n log n) nel caso peggiore ma non è stabile
5.Teoria dei grafi

Risposta: L = 11

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.

Lemma delle strette di mano per un albero

L + 29 = 2(L + 10) − 2
L = 11

Risposta

L = 11

Scorciatoia: L = 2 + Σ (d − 2) sui vertici di grado d ≥ 3.

6.Teoria dei grafi

Risposta: W = 28

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.

Algoritmo di Kruskal

BE (2): prendi
AC (4): prendi
CE (7): prendi
BC (10): salta, chiude un ciclo
AB (13): salta, chiude un ciclo
DE (15): prendi

Peso totale

W = 2 + 4 + 7 + 15 = 28

Risposta

W = 28

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