Progettazione di Algoritmi a.a. 2025-2026

Diario delle lezioni e delle esercitazioni

NOTA: le lezioni NON verranno registrate, ma trovate qui il dettaglio degli argomenti svolti ed il link al pdf delle slides utilizzate.

Settimana 1 - 24 Febbraio

Presentazione del corso. A.pdf

Settimana 1 - 25 Febbraio

I grafi. PL2.pdf

Settimana 1 - 26 Febbraio

ESERCIZI:

• trovare l'elemento di maggioranza assoluta in O(n).
• verificare l'esistenza del pozzo universale in O(n).

ESERCITAZIONE 1: alcune dimostrazioni di piccole proprietà sui grafi semplici non orientati (vedi slide prof. PL2c.pdf)

• la somma dei gradi dei nodi è pari. C'è un numero pari di nodi di grado dispari;
• se tutti i nodi hanno grado almeno 2 in G, allora c'è almeno un ciclo in G;
• in un grafo G con almeno 2 nodi, ci sono sempre almeno due nodi con lo stesso grado;
• almeno uno tra G e G complementato è connesso.

Settimana 2 - 4 Marzo

La visita in profondità (DFS). PL3.pdf

Settimana 2 - 5 Marzo

Applicazioni della visita in profondità (parte 1). Componenti connesse alberi DFS, ponti PL4.pdf

Settimana 3 - 10 Marzo

ESERCITAZIONE 2: alcune piccole applicazioni della DFS (e visite, vedi PL3.pdf)

• in un grafo ci sono sempre 2 nodi che possono essere rimossi lasciando il grafo connesso: dimostrazione e algoritmo;
• verificare se G è un albero (o G è aciclico) in tempo O(n);
• algoritmo per trovare (se esiste) una tripartizione bilanciata di un albero in O(n).

Settimana 3 - 11 Marzo

Applicazione della visita in profondità (parte 2) Cicli in grafi diretti. Ordinamenti topologici PL5.pdf

Settimana 3 - 12 Marzo

Applicazione della visita in profondità (parte 3) Componenti fortemente connesse e l'algoritmo di Kosaraju PL6.pdf

Settimana 4 - 17 Marzo

ESERCITAZIONE 3: DAG e ordinamenti topologici (vedi PL5.pdf) e SCC (vedi PL6.pdf)

• in un DAG c'è sempre un nodo senza archi entranti (uscenti);
• dato un grafo parzialmente ordinato (aciclico) orientare gli archi rimanenti per farlo rimanere un DAG.
• orientare gli archi di un grafo non orientato per ottenere un DAG
• verificare se G è un albero (o G è aciclico) in tempo O(n);
• grafo condensato e sua costruzione;
• trovare un insieme minimale di nodi da cui è possibile raggiungere tutti gli altri;
• trovare il minimo numero di archi necessario per rendere un grafo fortemente connesso.

Settimana 4 - 18 Marzo

La visita in ampiezza (BFS). Il diametro di un grafo. PL7.pdf

Settimana 4 - 19 Marzo

Grafi pesati. Il problema dei cammini minimi e l'algoritmo di Dijkstra PL8.pdf

Settimana 5 - 24 Marzo

ESERCITAZIONE 4: BFS e distanze (vedi PL7.pdf) e cammini minimi con Dijkstra (vedi PL8.pdf)

• nodi equidistanti da due nodi dati;
• distanza tra due insiemi di nodi: algoritmo ignorante (O(n^2(n+m)), semi-ignorante (O(n(n+m)), furbo (O(n+m)) e super-furbo (usando un algoritmo per la distanza di due nodi);
• cammino superminimo. Perché non è possibile trasformare un problema con pesi negativi in un problema con pesi positivi sommando il modulo del più piccolo peso negativo.

Settimana 5 - 25 Marzo

Grafi pesati. Il problema del minimo albero di copertura e l'algoritmo di Kruskal PL9.pdf

P.S. nel gruppo google del corso trovate l'indirizzo alla classroom per le lezioni del vostro tutor (quindi andate ed iscrivetevi per accedere)

Settimana 5 - 26 Marzo

La tecnica greedy PL10.pdf

Settimana 6 - 31 Marzo

ESERCITAZIONE 5: Il problema del minimo albero ricoprente (vedi PL9.pdf).

• discussione del problema della rete idrica di costo minimo e sua modellazione come problema di minimo albero di supporto;
• discussione della complessità del problema su grafi densi con algoritmi alternativi (stile Prim, aggiungendo la connessione minima alla parte già connessa o modificando un albero arbitrario scegliendo via via archi di costo minore mantenendolo un albero).

Settimana 6 - 1 Aprile

algoritmi di approsiimazione PL11.pdf

Settimana 6 - 2 Aprile

feste pasquali

Settimana 7 - 7 Aprile

feste pasquali

Settimana 7 - 8 Aprile

settimana sospensione della didattica

Settimana 7 - 9 Aprile

settimana sospensione della didattica

Settimana 8 - 14 Aprile

settimana sospensione della didattica

Settimana 8 - 15 Aprile

3 esempi di algoritmi d'approssimazione per problemi difficili PL12.pdf

Settimana 8 - 16 Aprile

Settimana 9 - 21 Aprile

Settimana 9 - 22 Aprile

Settimana 9 - 23 Aprile

Settimana 10 - 28 Aprile

Settimana 10 - 29 Aprile

Settimana 10 - 30 Aprile

Settimana 11 - 5 Maggio

Settimana 11 - 6 Maggio

Settimana 11 - 7 Maggio

Settimana 12 - 12 Maggio

Settimana 12 - 13 Maggio

Settimana 12 - 14 Maggio

Settimana 13 - 19 Maggio

Settimana 13 - 20 Maggio

Settimana 13 - 21 Maggio

Settimana 14 - 26 Maggio

Settimana 14 - 27 Maggio

Settimana 14 - 28 Maggio