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 complessità temporale del quicksort nel caso peggiore?

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

I cammini semplici minimi si possono trovare in tempo polinomiale. Che cosa si sa del trovare il cammino semplice più lungo tra due vertici in un grafo generico?

  1. AÈ NP-difficile
  2. BÈ indecidibile
  3. CÈ sempre risolvibile in O(V + E)
  4. DSi può risolvere con l'algoritmo di Dijkstra con pesi cambiati di segno
3.Strutture datiMedia

Qual è il costo di inserire un elemento al centro di un array di n elementi?

  1. AO(log n), per via della ricerca binaria
  2. BO(n), perché gli elementi successivi devono essere spostati
  3. CO(n²), perché ogni elemento si sposta n volte
  4. DO(1), perché l'indice è noto
4.Strutture datiDifficile

Un nodo AVL è sbilanciato perché il sottoalbero destro del suo figlio sinistro è diventato troppo alto (caso sinistra-destra). Quale correzione si applica?

  1. AUna rotazione a destra sul figlio sinistro, poi una rotazione a sinistra sul nodo
  2. BUna rotazione a sinistra sul figlio sinistro, poi una rotazione a destra sul nodo
  3. CUna singola rotazione a destra sul nodo
  4. DUna singola rotazione a sinistra sul nodo
5.Teoria dei grafiMedia

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

2 × deg 34 × deg 43 × deg 53 × deg 2
L =
6.Teoria dei grafiDifficile
321514151231489ABCDEFG

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

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

3Soluzioni

1.Algoritmi e complessità

Risposta: B · O(n²)

Perché è questa la risposta

Con pivot sistematicamente sfavorevoli (ad es. input già ordinato e primo elemento come pivot) le partizioni sono sbilanciate, dando O(n²). Il caso medio è O(n log n).

Risposta

B · O(n²)
2.Algoritmi e complessità

Risposta: A · È NP-difficile

Perché è questa la risposta

Un cammino semplice più lungo di lunghezza V − 1 è un cammino hamiltoniano, un problema NP-completo; sui grafi orientati aciclici, invece, è risolvibile in tempo lineare.

Risposta

A · È NP-difficile
3.Strutture dati

Risposta: B · O(n), perché gli elementi successivi devono essere spostati

Perché è questa la risposta

Tutti gli elementi dopo il punto di inserimento si spostano di una posizione a destra, il che richiede un tempo proporzionale a n.

Risposta

B · O(n), perché gli elementi successivi devono essere spostati
4.Strutture dati

Risposta: B · Una rotazione a sinistra sul figlio sinistro, poi una rotazione a destra sul nodo

Perché è questa la risposta

La prima rotazione trasforma il caso sinistra-destra in un caso sinistra-sinistra, che viene poi corretto da una rotazione a destra sul nodo sbilanciato.

Risposta

B · Una rotazione a sinistra sul figlio sinistro, poi una rotazione a destra sul nodo
5.Teoria dei grafi

Risposta: L = 21

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 + 43 = 2(L + 12) − 2
L = 21

Risposta

L = 21

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

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: 3
2. B (3): C: 5, D: 18, G: 6
3. C (5): E: 19
4. G (6): D: 14, E: 15
5. D (14)
6. E (15): F: 27
7. F (27)

passo 6

E

Risposta

E

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