lez01Introduzione23.pdf
Progettazione di Algoritmi a.a. 2023-2024
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 - 26 Febbraio
26 Febbraio 2024 (Lunedì): Presentazione del corso. Richiami di concetti fondamentali appresi ad introduzione agli algoritmi. Algoritmi efficienti, complessità polinomiale, superpolinomiale: esponenziale, superesponenziale e subesponenziale. ESERCIZIO: Progettare un algoritmo che verifichi se in un array di n interi esiste o meno un intero che compare in maggioranza assoluta. L'algoritmo deve avere complessità O(n).
lez01Introduzione24.pdf
28 Febbraio 2024 (mercoledì): I grafi, vertici e archi, grafi diretti e non diretti, relazione tra il numero n di nodi e il numero m di archi. Grafi sparsi e grafi densi. Esempi di grafi sparsi: alberi e grafi planari. Rappresentazione di grafi tramite matrice di adiacenza e trazmite liste di adiacenza. ESERCIZIO: Dimostrare che in ogni grafo di almeno due nodi sono presenti almeno due nodi con lo stesso numero di vicini.
Lez02Grafi1.pdf
29 Febbraio 2024 (Giovedì): -Visita in profondità (DFS) in tempo O(n^2), rappresentazione di grafi tramite liste di adiacenza e visita in profondità in O(n+m). ESERCIZIO risolvere il problema del pozzo universale in tempo O(n) avendo il grafo direttao rappresentato tramite matrice di adiacenza.
Lez03Grafi2.pdf
Settimana 02 - 4 Marzo
4 Marzo 2024 (Lunedì):-Albero DFS e sua costruzione mediante visita. Ottenere il cammino dalla radice dell'albero DFS ad un nodo raggiungibile in tempo O(n). Colorazione di grafi, bicolorazione in tempo O(n+m). ESERCIZIO1: si consideri la bicolorazione degli archi di grafi completi di n nodi. Qual'è il minimo n per cui il grafo colorato contiene necessariamente un ciclo di tre noto monocromatico? ESERCIZIO2: sia G1 un grafo e G2 il suo grafo complementare, dimostrare o confutare che almeno uno dei due grafi è connesso.
Lez04Grafi3.pdf
6 Marzo 2024 (mercoledì): Algoritmi per la ricerca delle componenti connesse in O(n+m) e algoritmo per la ricerca delle componenti fortemente connesse. Ordinamento topologico. Condizioni necessaria perche' esista un sort topologico, Algoritmo "delle sorgenti" per la ricerca di un sort topologico, correttezza e complessità.
Lez05Grafi4.pdf
7 Marzo 2024 (Giovedì): (
Esercitazione 1) Alcune piccole proprietà dei grafi: (
1) In un grafo, ci sono sempre due nodi con lo stesso grado; (
2) almeno uno tra G e il suo complementare è connesso; (
3) in un grafo c'è sempre un nodo che può essere rimosso, lasciando il grafo rimanente connesso. Algoritmo per orientare gli archi di un grafo non orientato (o parzialmente orientato) per ottenere un DAG.
Soluzioni.
Settimana 03 - 11 Marzo
11 Marzo 2024 (Lunedì): Algoritmo basato sulla visita DFS per la ricerca di un sort topologico, correttezza e complessità
Ricerca di cicli in grafi non diretti in tempo O(n) e in grafi diretti in tempo O(n+m) . Archi all'indietro, in avanti e di attraversamento durante le visite DFS in grafi diretti.
Lez06GrafiCicli.pdf
Il problema di determinare i ponti: algoritmo per determinare se l'arco
(a,b) è un ponte, algoritmo esaustivo che verifica tutti gli archi di complessita' O(m^2), algoritmo che verifica i soli archi dell'albero DFS di complessità O(nm). Algoritmo con un'unica visita DFS di complessita' O(m)
Lez07grafiPonti.pdf.
13 Marzo 2024 (Mercoledì): Visita di grafi in ampiezza (BFS) e sua Implementazione in O(n+m). Generazione dell'albero BFS e prova che produce cammini minimi. Vettore delle distanze.
Lez08grafiBFS.pdf
14 Marzo 2024 (Giovedì): (
Esercitazione 2) (
1) Ordinamenti topologici e alberi (
2) Diametro di un grafo e di un albero (
3) Nodi principali in un grafo.
Testi & Soluzioni.
Settimana 04 - 18 Marzo
18 Marzo 2024 (Lunedì): -Grafi pesasi e loro rappresentazione. Algoritmo di Dijkstra per la ricerca di cammini minimi in grafi pesati con pesi positivi. Correttezza e implementazioni:
a) implementazione di costo O(n^2) ottima per grafi densi
b) implementazione di costo O((n + m) log n) tramite heap di complessità adatta a grafi sparsi.
Lez09grafiPesati.pdf
20 Marzo 2024 (Mercoledì): Struttura dati Union e Find. Due implementazioni: 1) Union in O(n) e Find in O(1). 2) Union in O(1) e Find in O(log n). -
Lez10aUnionFind.pdf
L'algoritmo di Kruskal,per la ricerca dell'albero di copertura di costo minimo, prova di correttezza implementazione in O(mlog n).
Lez10SpanningTree.pdf
21 Marzo 2024 (Giovedì): (
Esercitazione 3) (
1) Capire le componenti Fortemente Connesse: come cambiano aggiungendo un arco. (
2) Quand'è che BFS e DFS radicate nello stesso nodo, danno come risultato lo stesso albero di visita. (
3) Algoritmo per trovare la distanza tra due insiemi di nodi.
(
4) Variazioni su Dijkstra: trovare il cammino superminimo e problemi correlati.
Testi & Soluzioni.
Settimana 05 - 25 Marzo
25 Marzo 2024 (Lunedì): Introduzione alla tecnica greedy. Il problema della selezione di attività algoritmo, prova di correttezza e sua implementazione in O(nlog n). Il problema dell'assegnazione di attività, algoritmo, prova di correttezza e sua implementazione in O(nlog n).
ESERCIZIO: dati due vettori di interi di 2n elementi ciascuno bisogna selezionare n elementi dal primo ed n elementi dal secondo in modo che non ci siano due elementi selezionati con la stessa coordinata e che la somma risulti massima. Progettare un algoritmo che risolva il problema in O(nlog n) e dimostrarne la correttezza.
ESERCIZIO: date le dimensioni di n file ed un disco rigido di capacità C bisogna selezionare un sottoinsieme di massima cardinalità degli n file che possono trovare spazio su disco rigido. Progettare un algoritmo che risolva il problema in tempo O(nlog n) e provarne la correttezza.
Lez11greedy.pdf
27 Marzo 2024 (Mercoledì): (
Esercitazione 4) (
1) Trovare il nodo in cui radicare la visita di un albero in modo che l'orientamento indotto dalla visita minimizzi il numero di archi da rovesciare rispetto a un ordinamento arbitrario; (
2) Algoritmo per determinare se un grafo sia semi-connesso
Testi & Soluzioni.
28 Marzo 2024 (Giovedì): VACANZE DI PASQUA
Settimana 06 - 1 Aprile
1 Aprile 2024 (Lunedì): VACANZE DI PASQUA
3 Aprile 2024 (Mercoledì): -
4 Aprile 2024 (Giovedì): (
Esercitazione 5)
Settimana 07 - 8 Aprile
8 Aprile 2024 (Lunedì): -
10 Aprile 2024 (Mercoledì): -
11 Aprile 2024 (Giovedì):
Settimana 08 - 15 Aprile
15 Aprile 2024 (Lunedì):
17 Aprile 2024 (Mercoledì): -
18 Aprile 2024 (Giovedì):
Settimana 09 - 22 Aprile
*
22 Aprile 2024 (Lunedì):
24 Aprile 2024 (Mercoledì): -
25 Aprile 2024 (Giovedì): festa della liberazione
Settimana 10 - 29 Aprile
29 Aprile 2024 (Lunedì):
1 Maggio 2024 (Mercoledì): - festa dei lavoratori
2 Maggio 2024 (Giovedì):
Settimana 11 - 6 Maggio
6 Maggio 2024 (Lunedì):
8 Maggio 2024 (Mercoledì): -
9 Maggio 2024 (Giovedì):
Settimana 12 - 13 Maggio
13 Maggio 2023 (Lunedì):
15 Maggio 2024 (Mercoledì): -
16 Maggio 2023 (Giovedì):
Settimana 13 - 20 Maggio
*20 Maggio 2024 (Lunedì):*
22 Maggio 2024 (Mercoledì): -
23 Maggio 2024 (Giovedì):
Settimana 14 - 27 Maggio
27 Maggio 2024 (Lunedì):
29 Maggio 2024 (Mercoledì): -
30 Maggio 2024 (Giovedì):