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).

Settimana 2 - 3 Marzo

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) slides

• 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 approssimazione 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

la tecnica dle divide et impera:

il problema della selezione PL13.pdf

il problema della coppia di punti più vicini PL14.pdf

Settimana 9 - 21 Aprile

ESERCITAZIONE 6: Un problema di Teoria dei Giochi in salsa Greedy: Il problema dei Matrimoni Stabili. slides

Settimana 9 - 22 Aprile

programmazione dinamica: overlapping di sottoproblemi, memoizzazione, apporccio top-down e approccio bottom up. PL15.pdf

Settimana 9 - 23 Aprile

esercizi di programmazione dinamica: progettare una procedura che:

1) dato n restituisca in O(n) il numero di stringhe ternarie lunghe n che non contengono come simboli adiacenti 000,010 e 020

2) dato n restituisca in O(n) il numero di stringhe ternarie lunghe n che non contengono come simboli adiacenti 12 e 22

3) dato n calcoli quanti modi ci sono di piastrellare un corridoio di dimensione 2 x n con mattonelle di dimensione 1 x 2 che possono essere sitemate in orizzontale o verticale.

4) data una matrice n per n con celle contenenti interi vogliamo sapere qual'e' il valore massimo che si puo' ottenere con cammino che parta dalla cella in alto a sinistra e arriv aalla cella in basso a destra. Ad ogni passo del cammino ci si puo' spostare sulla cella alla destra o sulla cella in basso. Il costo del cammino è dato dalla somma dei valori dellle celle toccate. Progettare una procedura che risolva il problema in tempo O(n^2)

5) data una matrice binaria n per n vogliamo sapere se esiste un cammino che parta dalla cella in alto a sinistra e arrivi alla cella in basso a destra toccando solo caselle contenenti il valore 0. Ad ogni passo del cammino ci si puo' spostare sulla cella alla destra o sulla cella in basso. Progettare una procedura che risolva il problema in tempo O(n^2).

Settimana 10 - 28 Aprile

. Programmazione dinamica e tabelle di due dimensioni

ESEMPI:

• il problema dello zaino
• la più lunga sottosequenza comune

PL16.pdf

Settimana 10 - 29 Aprile

ESERCITAZIONE 7:

• Programmazione Dinamica: il problema della minima supersequenza codice Python commentato:.
• Divide et Impera (e non solo): il problema del più lungo segmento di spessore minore di C codice Python commentato.

Settimana 10 - 30 Aprile

. Programmazione dinamica e cammini minimi

Algoritmo di Bellman-Ford per il calcolo delle distanz eda sorgent ein grafi con pesi anche negativi in tempo O(nm)

Algoritmo di Floyd e Warshall per il calcolo delle distanz etra ogni coppia di nodi in un grafo in tempo O(n^3)

. PL17.pdf

Settimana 11 - 5 Maggio

ESERCITAZIONE 8:

• Divide et Impera (anomalo): primo valore negativo di una funzione decrescente: Primo Negativo.
• Programmazione Dinamica: il problema della massima sottosequenza palindroma: codice Python commentato:.
• Divide et Impera (e non solo): il problema del sottosegmento di somma massima: segmento di Somma Masima

Settimana 11 - 6 Maggio

. ESERCIZI di programmazione dinamica:

il problema del sottosegmento di somma massima in O(n)

il problema della sottosequenza crescente di lunghezza massima in O(n^2)

il conteggio del numero di alberi binari distinti con n nodi in O(n^2). I numeri di catalano

approccio bottom up al problema della massima sottosequenza palindroma come esempio di tabella da riempire per diagonali

Settimana 11 - 7 Maggio

La tecnica del backtracking PL18.pdf

stampare stringhe binarie lunghe n in tempo O(n2^n).

Stampare stringhe lunghe n con vincoli in tempo O(nS(n)) dove S(n) è il numero di stringhe da stampare

Esercizio:
1) dato n generare tutte le stringhe ternarie su alfabeto {a,b,c} dove il numero delle a supera il numero delle b che a sua volta supera il numero delle c. L'algoritmo deve avere complessità O(nS(n)) dove S(n) è il numero delle stringhe da stampare.

Settimana 12 - 12 Maggio

ESERCITAZIONE 9:

• Bactracking 1: il problema di generare stringhe palindrome: codice Python commentato.
• Bactracking 2: il problema delle stringhe di 0,1 bilanciate: codice Python commentato:.
• Bactracking 3: il problema delle n regine: codice commentato

Settimana 12 - 13 Maggio

stampare matrici binarie di dimensioni n per n in tempo O(2^(n^2)).

Stampare matrici n per n con vincoli in tempo O(nS(n)) dove S(n) è il numero di matrici da stampare

Settimana 12 - 14 Maggio

.

Settimana 13 - 19 Maggio

.

Settimana 13 - 20 Maggio

. stampare le permutazioni dei primi n interi in tempo O(n n!).

Stampare le permutazioni dei primi n interi con vincoli in tempo O(nS(n)) dove S(n) è il numero di permutazioni da stampare.

PL19.pdf

Backtraking come tecnica per problemi decisionali e problemi di ottimizzazione.

Esempi :

• decidere se un grafo è hamiltoniano o meno,
• risolvere il problema dello zaino

Settimana 13 - 21 Maggio

. simulazione di prova d'esame con somministrazione di prova d'esame del gennaio 2025 gennaio.pdf

Settimana 14 - 26 Maggio

.

Settimana 14 - 27 Maggio

.

Settimana 14 - 28 Maggio