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à.
Lez05OrdinamentoTopologico.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ì): -euristiche ed algoritmi di approssimazione. Rapporto di approssimazione per problemi di minimizzazione e per problemi di massimizzazione. Il problema della copertura tramite vertici un algoritmo di approssimazione che non ha rapporto di approssimazione limitato ma Ω(log n) ed un algoritmo di approssimazione di tempo O(n+m) con rapporto d'approssimazione limitato da 2.
Lez12Approssimazione.pdf
4 Aprile 2024 (Giovedì): (
Esercitazione 5) (
1) Passeggiata che percorre tutti gli archi di un grafo non orientato 2 volte, 1 volta in ciascuna direzione; (
2) Calcolare la distanza tra due nodi in un albero rappresentato come vettore dei padri. Altezza di un albero rappresentato come vettore dei padri; (
3) qualche ragionamento su Alberi minimi di supporto [nelle slide qualche esercizio supplettivo con soluzione]
Testi & Soluzioni.
Settimana 07 - 8 Aprile
8 Aprile 2024 (Lunedì): Esempi di algoritmi di approssimazione: un euristica di tempo O(n+m) e rapporto limitato da 2 per il problema del massimo taglio. L'euristica Next-Fit di tempo O(n) e rapporto limitato da 2 per il problema dell'inscatolamento. L'euristica First-fit decreasing di tempo O(nlog n) e rapporto limitato da 3/2 +1/k^* per l'inscatolamento.
approssimazione1.pdf
10 Aprile 2024 (Mercoledì): Il problema della selezione: dato un vettore A di interi distinti ed un intero k, con 1<=k<=len(A), vogliamo trovare l'elemento di rango k (vale a dire l'elemento che si troverebbe al k-mo posto nel vettore A ordinato). Algoritmo banale di tempo O(nlog n). Algoritmo basato sulla tecnica del divide et impera randomizzato con tempo medio O(n) e caso pessimo O(n^2). Algoritmo ottimo che richiede Θ(n).
Lez14DivideEtImpera1.pdf
11 Aprile 2024 (Giovedì): (
Esercitazione 6) Una celebre perla di progettazione di algoritmi in salsa grafo-greedy, per rinfrancare lo spirito tra un esonero e l'altro.
Il problema dei
Matrimoni Stabili.
Settimana 08 - 15 Aprile
15 Aprile 2024 (Lunedì): discussione degli esercizi della prova per la verifica delle conoscenze.
- esercizio1: progettare un algoritmo sublinearebasato sulla tecnica del divide et impera che, date la costante a e l'intero n, restituisce il valore a^n (e' possibile utilizzare solo gli operatori +, -, *).
- esercizio 2: data una stringa binaria lunga n progettare algoritmi basati sulla tecnica del divite et impera che abbia complessità Θ(n).
Lez15DivideEtImpera2.pdf
17 Aprile 2024 (Mercoledì): -Indorduzione alla programmazione dinamica. Esempio 1: numeri di fibonacci e overlapping di sottoproblemi. Progettare un algoritmo Θ(n) basato sulla tecnica della programmazione dinamica prima top-down con memoizzazione e poi bottom up infine ottenere un algoritmo che utilizza spazio di lavoro Θ(n). Esempio 2: dato una lista di file con le loro dimensioni e un hard disk di capacità C determinare il massimo spazio dell'hard disk che e' possibile occupare. Progettar eun algoritmo basato sulla programmazione dinamic adi tempo Θ(nC). Algoritmi pseudopolinomiali.
Lez16ProgrammazioneD1.pdf
18 Aprile 2024 (Giovedì): (
Esercitazione 7) (
1) Trovare il massimo insieme indipendente di nodi in un albero; algoritmo e dimostrazione di correttezza della strategia greedy; (
2) Ricerca binaria su vettore di un numero di elementi non noto (Esercizio
5.10).
Sfida: Dare un algoritmo divide-et-impera per trovare il segmento più lungo in un vettore di spessore < C (Esercizio
5.6).
Settimana 09 - 22 Aprile
22 Aprile 2024 (Lunedì):esercizi sulla programmazione dinamica
Lez17PD2a.pdf
24 Aprile 2024 (Mercoledì): -Ricerca della sottosequenza crescente più lunga in tempo O(n^2) ed altri esercizi di programmazione dinamica risolvibili con tabelle monodimensionali.
Lez17PD2b.pdf
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ì):