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 esercizi Torna 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(K_n)| = n(n − 1)/2, |E(K_m,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 K_n: (n − 1)!/2
Aggiornamento di Dijkstra: d(v) = min(d(v), d(u) + w(u, v))
Cammini di lunghezza L: (Mᴸ)_ij

Metodo

Scrivi il grado di ogni vertice; la somma dei gradi è il doppio del numero di lati.
Nelle domande su Eulero, verifica che il grafo sia connesso e conta i vertici di grado dispari.
Per gli alberi, usa n − 1 lati e il lemma delle strette di mano.
Per Dijkstra, tieni una tabella delle distanze provvisorie e a ogni passo fissa il vertice non ancora fissato con la distanza minima.
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 di: for i = 1 to n: for j = 1 to i: lavoro O(1)?

AO(n³)
BO(n log n)
CO(n²)
DO(n)

2.Algoritmi e complessitàDifficile

Come si confrontano n! e 2ⁿ per n grande?

An! cresce più velocemente di 2ⁿ
Bn! è O(n²)
C2ⁿ cresce più velocemente di n!
DCrescono allo stesso ritmo

3.Strutture datiMedia

Quanti nodi ha un albero binario perfetto di altezza h, con l'altezza contata in archi?

A2^h+1 − 1
Bh²
C2h + 1
D2^h

4.Strutture datiDifficile

La struttura union-find (insiemi disgiunti) con unione per rango e compressione dei cammini ha un costo ammortizzato per operazione di:

AO(n²)
BEsattamente O(log n)
CO(n)
DO(α(n)), l'inversa della funzione di Ackermann, praticamente costante

5.Teoria dei grafiMedia

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

K₇

H =

6.Teoria dei grafiDifficile

L’algoritmo di Prim costruisce un albero di copertura minimo a partire dal vertice F. Clicca il lato che aggiunge come lato numero 3.

partenza: Fk = 3

1lato AB
2lato AC
3lato BC
4lato BD
5lato DE
6lato DF
7lato EF
8lato BE

3Soluzioni

1.Algoritmi e complessità

Risposta: C · O(n²)

Perché è questa la risposta

Il corpo interno viene eseguito in totale n(n + 1) / 2 volte, che è comunque quadratico.

Risposta

C · O(n²)

2.Algoritmi e complessità

Risposta: A · n! cresce più velocemente di 2ⁿ

Perché è questa la risposta

Per n ≥ 4, n! supera 2ⁿ, e il rapporto cresce senza limite perché ogni fattore aggiuntivo di n! è maggiore di 2.

Risposta

A · n! cresce più velocemente di 2ⁿ

3.Strutture dati

Risposta: A · 2^h+1 − 1

Perché è questa la risposta

La somma 1 + 2 + 4 + ... + 2^h dà 2^h+1 − 1; per esempio, l'altezza 2 dà 7 nodi.

Risposta

A · 2^h+1 − 1

4.Strutture dati

Risposta: D · O(α(n)), l'inversa della funzione di Ackermann, praticamente costante

Perché è questa la risposta

Con entrambe le ottimizzazioni, le operazioni richiedono un tempo ammortizzato O(α(n)); α(n) ≤ 4 per qualsiasi n realistico.

Risposta

D · O(α(n)), l'inversa della funzione di Ackermann, praticamente costante

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; K_n 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: lato BC

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 Prim

1. EF (17)

2. BE (16)

3. BC (1)

4. BD (10)

5. AB (13)

lato numero 3

Risposta

lato BC

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