PALGdiario2014_2 < Algoritmi2

Tags: view all tags

---+ 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. [[%ATTACHURL%/A.pdf][A.pdf]]
---+++ Settimana 1 - 25 Febbraio

<span>I grafi. [[%ATTACHURL%/PL2.pdf][PL2.pdf]] [[%ATTACHURL%/PL2.pdf][<br />]]</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 1 - 26 Febbraio</span>

ESERCIZI:
   * trovare l'elemento di maggioranza assoluta in O(n).
   * verificare l'esistenza del pozzo universale in O(n).
<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 2 - 3 Marzo</span>

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.

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 2 - 4 Marzo</span>

La visita in profondità (DFS). [[%ATTACHURL%/PL3.pdf][PL3.pdf]]

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 2 - 5 Marzo</span>

Applicazioni della visita in profondità (parte 1). Componenti connesse alberi DFS, ponti [[%ATTACHURL%/PL4.pdf][PL4.pdf]]

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 3 - 10 Marzo</span>

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

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 3 - 11 Marzo</span>

Applicazione della visita in profondità (parte 2) Cicli in grafi diretti. Ordinamenti topologici [[%ATTACHURL%/PL5.pdf][PL5.pdf]]

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 3 - 12 Marzo</span>

Applicazione della visita in profondità (parte 3) Componenti fortemente connesse e l'algoritmo di Kosaraju [[%ATTACHURL%/PL6.pdf][PL6.pdf]] [[%ATTACHURL%/PL5.pdf][<br />]]

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 4 - 17 Marzo</span>

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.

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 4 - 18 Marzo</span>

La visita in ampiezza (BFS). Il diametro di un grafo. [[%ATTACHURL%/PL7.pdf][PL7.pdf]] [[%ATTACHURL%/PL7.pdf][<br />]]

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 4 - 19 Marzo</span>

Grafi pesati. Il problema dei cammini minimi e l'algoritmo di Dijkstra [[%ATTACHURL%/PL8.pdf][PL8.pdf]] [[%ATTACHURL%/PL8.pdf][<br />]]

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 5 - 24 Marzo</span>

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.

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 5 - 25 Marzo</span>

Grafi pesati. Il problema del minimo albero di copertura e l'algoritmo di Kruskal [[%ATTACHURL%/PL9.pdf][PL9.pdf]] [[%ATTACHURL%/PL9.pdf][<br />]]

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

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 5 - 26 Marzo</span>

La tecnica greedy [[%ATTACHURL%/PL10.pdf][PL10.pdf]]

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 6 - 31 Marzo</span>

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

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 6 - 1 Aprile</span>

algoritmi di approsiimazione [[%ATTACHURL%/PL11.pdf][PL11.pdf]]

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 6 - 2 Aprile</span>

feste pasquali

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 7 - 7 Aprile</span>

feste pasquali

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 7 - 8 Aprile</span>

settimana sospensione della didattica

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 7 - 9 Aprile</span>

settimana sospensione della didattica

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 8 - 14 Aprile</span>

settimana sospensione della didattica

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 8 - 15 Aprile</span>

3 esempi di algoritmi d'approssimazione per problemi difficili [[%ATTACHURL%/PL12.pdf][PL12.pdf]]

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 8 - 16 Aprile</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 9 - 21 Aprile</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 9 - 22 Aprile</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 9 - 23 Aprile</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 10 - 28 Aprile</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 10 - 29 Aprile</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 10 - 30 Aprile</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 11 - 5 Maggio</span>

---+++ Settimana 11 - 6 Maggio

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 11 - 7 Maggio</span>

---+++ Settimana 12 - 12 Maggio

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 12 - 13 Maggio</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 12 - 14 Maggio</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 13 - 19 Maggio</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 13 - 20 Maggio</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 13 - 21 Maggio </span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 14 - 26 Maggio </span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 14 - 27 Maggio</span>

<span style="color: #630000; font-size: 17.290001px; font-weight: bold;">Settimana 14 - 28 Maggio</span>

<div style="margin-left: 5%; margin-right: 5%;"> <div align="justify" style="margin-left: 5%; margin-right: 10%;">

[[%PUBURL%/Algoritmi2/PALGesercizi2014/esercizi.html][ESERCIZI preparatori all'esame]]
</div> </div>

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
pdf	A.pdf	r1	manage	5932.9 K	2026-02-24 - 12:53	AngeloMonti
pdf	EserciziPD.pdf	r1	manage	1232.1 K	2022-05-09 - 10:29	AngeloMonti
pdf	Lez18PD3a.pdf	r1	manage	2799.0 K	2024-04-30 - 07:02	AngeloMonti
pdf	Lez18PD3b.pdf	r1	manage	2078.6 K	2024-05-02 - 17:25	AngeloMonti
pdf	Lez19.pdf	r1	manage	4637.2 K	2022-04-30 - 12:26	AngeloMonti
pdf	Lez20A2BT2.pdf	r1	manage	3264.0 K	2025-05-14 - 15:35	AngeloMonti
pdf	Lez20BT1.pdf	r1	manage	3052.1 K	2024-05-06 - 21:41	AngeloMonti
pdf	Lez21A2BT3_.pdf	r1	manage	6198.7 K	2025-05-19 - 15:39	AngeloMonti
pdf	Lez22BT3_.pdf	r2 r1	manage	5450.9 K	2024-05-15 - 06:58	AngeloMonti
pdf	PL10.pdf	r1	manage	191.6 K	2026-03-24 - 07:12	AngeloMonti
pdf	PL11.pdf	r1	manage	279.7 K	2026-03-26 - 12:20	AngeloMonti
pdf	PL12.pdf	r1	manage	233.9 K	2026-04-08 - 07:45	AngeloMonti
pdf	PL2.pdf	r1	manage	279.3 K	2026-03-13 - 07:09	AngeloMonti
pdf	PL3.pdf	r1	manage	290.4 K	2026-02-25 - 08:02	AngeloMonti
pdf	PL4.pdf	r2 r1	manage	355.9 K	2026-03-06 - 10:20	AngeloMonti
pdf	PL5.pdf	r4 r3 r2 r1	manage	380.3 K	2026-03-13 - 06:23	AngeloMonti
pdf	PL6.pdf	r2 r1	manage	260.6 K	2026-03-13 - 07:22	AngeloMonti
pdf	PL7.pdf	r1	manage	400.6 K	2026-03-18 - 08:07	AngeloMonti
pdf	PL8.pdf	r1	manage	357.7 K	2026-03-19 - 10:40	AngeloMonti
pdf	PL9.pdf	r1	manage	344.1 K	2026-03-19 - 12:08	AngeloMonti
pdf	SecondoEsonero24Soluzione.pdf	r1	manage	155.2 K	2025-05-16 - 15:13	AngeloMonti
pdf	SoluzioniSecondoEsonero.pdf	r1	manage	912.0 K	2025-05-16 - 15:18	AngeloMonti
pdf	TRACCEesercizi.pdf	r1	manage	1102.7 K	2025-03-29 - 09:29	AngeloMonti
pdf	TracceEserciziGreedyPDF.pdf	r1	manage	1023.8 K	2021-03-29 - 12:02	AngeloMonti
pdf	intermedia2017.pdf	r1	manage	143.7 K	2018-04-19 - 07:15	AngeloMonti
pdf	lez14Tracce.pdf	r1	manage	540.2 K	2019-05-02 - 15:24	AngeloMonti	esercizi
pdf	lez15tracce.pdf	r1	manage	384.4 K	2019-05-07 - 15:27	AngeloMonti
pdf	lez19tracce.pdf	r1	manage	927.0 K	2019-05-21 - 15:59	AngeloMonti
pdf	lez20BT1.pdf	r1	manage	4031.4 K	2023-05-08 - 17:16	AngeloMonti