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ì):

Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf 2020SoluzioneGiugnoA.pdf r1 manage 678.6 K 2022-05-26 - 17:25 AngeloMonti  
PDFpdf 2020SoluzioneMarzoStraordinario.pdf r1 manage 1440.3 K 2022-05-26 - 17:25 AngeloMonti  
PDFpdf 2020giugnoA.pdf r1 manage 84.4 K 2022-05-26 - 13:07 AngeloMonti  
PDFpdf 2020marzoStraordinario.pdf r1 manage 76.0 K 2022-05-26 - 13:07 AngeloMonti  
PDFpdf EserciziPD.pdf r1 manage 1232.1 K 2022-05-09 - 10:29 AngeloMonti  
PDFpdf EsercizioEsonero.pdf r1 manage 114.6 K 2022-05-09 - 10:29 AngeloMonti  
PDFpdf Lez02Grafi1.pdf r5 r4 r3 r2 r1 manage 1073.5 K 2024-02-29 - 18:27 AngeloMonti  
PDFpdf Lez02Grafi1b.pdf r2 r1 manage 925.4 K 2022-02-28 - 18:22 AngeloMonti  
PDFpdf Lez03Grafi2.pdf r2 r1 manage 1601.3 K 2024-03-04 - 18:21 AngeloMonti  
PDFpdf Lez03grafi2.pdf r2 r1 manage 1331.2 K 2022-02-28 - 18:46 AngeloMonti  
PDFpdf Lez03grafi2PDF.pdf r2 r1 manage 1092.7 K 2021-03-04 - 18:23 AngeloMonti  
PDFpdf Lez04Grafi3.pdf r4 r3 r2 r1 manage 2276.8 K 2024-03-06 - 15:45 AngeloMonti  
PDFpdf Lez04Grafi3PDF.pdf r2 r1 manage 1392.9 K 2021-03-08 - 21:20 AngeloMonti  
PDFpdf Lez05Grafi4.pdf r3 r2 r1 manage 1020.8 K 2024-03-06 - 15:46 AngeloMonti  
PDFpdf Lez05Grafi4PDF.pdf r1 manage 871.6 K 2021-03-08 - 21:23 AngeloMonti  
PDFpdf Lez06Grafi5.pdf r2 r1 manage 670.1 K 2023-06-20 - 10:35 AngeloMonti  
PDFpdf Lez06GrafiCicli.pdf r1 manage 1118.7 K 2024-03-11 - 18:30 AngeloMonti  
PDFpdf Lez06grafi5.pdf r1 manage 511.1 K 2022-03-08 - 13:47 AngeloMonti  
PDFpdf Lez06grafi5PDF.pdf r1 manage 1198.8 K 2021-03-10 - 09:23 AngeloMonti  
PDFpdf Lez07grafi6BFS.pdf r1 manage 999.0 K 2023-03-13 - 17:29 AngeloMonti  
PDFpdf Lez07grafi6bPDF.pdf r1 manage 959.1 K 2021-03-15 - 18:04 AngeloMonti  
PDFpdf Lez07grafiPonti.pdf r1 manage 804.3 K 2024-03-11 - 18:26 AngeloMonti  
PDFpdf Lez08grafi7.pdf r3 r2 r1 manage 2083.2 K 2022-03-21 - 14:00 AngeloMonti  
PDFpdf Lez08grafi7GrafiPesati.pdf r1 manage 2054.6 K 2023-03-14 - 16:38 AngeloMonti  
PDFpdf Lez08grafi7PDF.pdf r1 manage 2230.8 K 2021-03-15 - 17:43 AngeloMonti  
PDFpdf Lez08grafiBFS.pdf r2 r1 manage 1849.8 K 2024-03-13 - 15:36 AngeloMonti  
PDFpdf Lez09SpanningTree.pdf r2 r1 manage 2484.8 K 2023-03-21 - 16:43 AngeloMonti  
PDFpdf Lez09SpanningTreePDF.pdf r1 manage 2439.9 K 2021-03-21 - 10:45 AngeloMonti  
PDFpdf Lez09grafi8GrafiPesati.pdf r1 manage 2054.6 K 2023-03-14 - 16:34 AngeloMonti  
PDFpdf Lez09grafiPesati.pdf r1 manage 2768.6 K 2024-03-18 - 18:31 AngeloMonti  
PDFpdf Lez10SpanningTree.pdf r1 manage 2103.1 K 2024-03-20 - 17:39 AngeloMonti  
PDFpdf Lez10aUnionFind.pdf r1 manage 954.9 K 2024-03-20 - 17:37 AngeloMonti  
PDFpdf Lez10greedy.pdf r2 r1 manage 2643.7 K 2023-03-21 - 16:23 AngeloMonti  
PDFpdf Lez10greedyPDF.pdf r1 manage 2803.1 K 2021-03-23 - 07:59 AngeloMonti  
PDFpdf Lez11.pdf r1 manage 1583.9 K 2022-04-07 - 07:34 AngeloMonti  
PDFpdf Lez11Approssimazione.pdf r1 manage 1660.3 K 2023-03-27 - 16:59 AngeloMonti  
PDFpdf Lez11ApprossimazionePDF.pdf r1 manage 1603.2 K 2021-03-29 - 11:57 AngeloMonti  
PDFpdf Lez11greedy.pdf r1 manage 2945.5 K 2024-03-25 - 22:35 AngeloMonti  
PDFpdf Lez12Esercizi1.pdf r1 manage 605.7 K 2022-04-09 - 08:30 AngeloMonti  
PDFpdf Lez12EserciziPDF.pdf r1 manage 2240.3 K 2021-04-08 - 16:35 AngeloMonti  
PDFpdf Lez13.pdf r1 manage 3069.1 K 2022-04-07 - 07:38 AngeloMonti  
PDFpdf Lez13DivideEtImpera1.pdf r1 manage 3303.5 K 2023-04-17 - 16:45 AngeloMonti  
PDFpdf Lez13DivideEtImpera1PDF.pdf r2 r1 manage 3153.1 K 2021-04-18 - 07:39 AngeloMonti  
PDFpdf Lez14DivideEtImpera2.pdf r1 manage 2452.6 K 2023-04-03 - 13:40 AngeloMonti  
PDFpdf Lez14DivideEtImpera2PDF.pdf r1 manage 2246.8 K 2021-04-13 - 12:30 AngeloMonti  
PDFpdf Lez15.pdf r1 manage 3845.9 K 2022-04-09 - 10:11 AngeloMonti  
PDFpdf Lez15DivideEtImpera3PDF.pdf r1 manage 3961.4 K 2021-04-18 - 08:50 AngeloMonti  
PDFpdf Lez16.pdf r2 r1 manage 3110.5 K 2023-04-17 - 16:46 AngeloMonti  
PDFpdf Lez16PD1PDF.pdf r1 manage 3771.0 K 2021-04-22 - 14:03 AngeloMonti  
PDFpdf Lez17.pdf r2 r1 manage 2104.3 K 2022-05-01 - 08:06 AngeloMonti  
PDFpdf Lez17PD2.pdf r1 manage 4661.2 K 2023-04-18 - 15:28 AngeloMonti  
PDFpdf Lez17PD2PDF.pdf r1 manage 2147.4 K 2021-04-26 - 17:10 AngeloMonti  
PDFpdf Lez18PD3.pdf r1 manage 2630.9 K 2023-04-20 - 13:46 AngeloMonti  
PDFpdf Lez18PD3rPDF.pdf r1 manage 2389.3 K 2021-04-29 - 17:18 AngeloMonti  
PDFpdf Lez18a.pdf r1 manage 2350.8 K 2022-05-03 - 06:38 AngeloMonti  
PDFpdf Lez18b.pdf r1 manage 1470.1 K 2022-05-09 - 10:24 AngeloMonti  
PDFpdf Lez19.pdf r1 manage 4637.2 K 2022-04-30 - 12:26 AngeloMonti  
PDFpdf Lez19PD4PDF.pdf r1 manage 4683.9 K 2021-05-03 - 07:49 AngeloMonti  
PDFpdf Lez20BT1PDF.pdf r1 manage 4077.4 K 2021-05-12 - 08:17 AngeloMonti  
PDFpdf Lez21BT2.pdf r1 manage 2753.2 K 2023-05-09 - 15:19 AngeloMonti  
PDFpdf Lez21BT2PDF.pdf r1 manage 3038.5 K 2021-05-12 - 08:13 AngeloMonti  
PDFpdf Lez22BT3.pdf r1 manage 4139.2 K 2023-05-09 - 15:20 AngeloMonti  
PDFpdf Lez22BT3PDF.pdf r1 manage 4063.0 K 2021-05-16 - 10:39 AngeloMonti  
PDFpdf Lez23web3EsercitazionePDF.pdf r1 manage 1049.6 K 2021-05-20 - 17:00 AngeloMonti  
PDFpdf Lez24Esercizi2PDF.pdf r1 manage 1801.3 K 2021-05-24 - 17:31 AngeloMonti  
PDFpdf Lez24TracceEsercizi2PDF.pdf r1 manage 313.4 K 2021-05-21 - 10:23 AngeloMonti  
PDFpdf Lez2IgrafiPDF.pdf r1 manage 1332.6 K 2021-03-01 - 13:31 AngeloMonti  
PDFpdf Lez9SpanningTree.pdf r1 manage 2417.1 K 2023-03-20 - 18:01 AngeloMonti  
PDFpdf ProvaFebbraio2022.pdf r1 manage 88.2 K 2022-05-23 - 08:29 AngeloMonti  
PDFpdf ProvaGiugno2021.pdf r1 manage 70.6 K 2022-05-23 - 08:29 AngeloMonti  
PDFpdf ProvaLuglio2020.pdf r1 manage 72.8 K 2022-05-23 - 08:29 AngeloMonti  
PDFpdf TracceEserciziGreedyPDF.pdf r1 manage 1023.8 K 2021-03-29 - 12:02 AngeloMonti  
PDFpdf esercizioPDF.pdf r1 manage 228.9 K 2021-04-08 - 16:35 AngeloMonti  
PDFpdf intermedia2017.pdf r1 manage 143.7 K 2018-04-19 - 07:15 AngeloMonti  
PDFpdf lez01Introduzione22.pdf r2 r1 manage 568.6 K 2022-02-22 - 10:16 AngeloMonti  
PDFpdf lez01Introduzione23.pdf r1 manage 528.4 K 2023-02-20 - 13:11 AngeloMonti  
PDFpdf lez01Introduzione24.pdf r1 manage 532.7 K 2024-02-26 - 18:35 AngeloMonti  
PDFpdf lez01IntroduzionePDF.pdf r1 manage 592.1 K 2021-02-22 - 20:06 AngeloMonti  
PDFpdf lez14Tracce.pdf r1 manage 540.2 K 2019-05-02 - 15:24 AngeloMonti esercizi
PDFpdf lez15tracce.pdf r1 manage 384.4 K 2019-05-07 - 15:27 AngeloMonti  
PDFpdf lez19tracce.pdf r1 manage 927.0 K 2019-05-21 - 15:59 AngeloMonti  
PDFpdf lez20BT1.pdf r1 manage 4031.4 K 2023-05-08 - 17:16 AngeloMonti  

This topic: Algoritmi2 > WebHome > PALGdiario2014_2
Topic revision: r349 - 2024-03-28 - IvanoSalvo
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback