PALGprogramma2014 < Algoritmi2

---+ Progettazione di Algoritmi a.a. 2025-2026

<!--
<H2>Obiettivi</H2>
<DIV style="margin-left:5%; margin-right:10%">
<DIV ALIGN="justify">
<p>
Introdurre idee e tecniche che aiutano la progettazione e l'implementazione 
di software efficiente ed elegante. In particolare, tali idee e tecniche sono sfruttate in 
quelle parti di importanti sistemi software (sistemi operativi, compilatori/interpreti, 
DBMS, ecc.) che devono fornire elevate prestazioni. Enfasi è posta nella definizione 
e nella dimostrazione rigorosa delle proprietà dei concetti presentati (algoritmi e 
strutture dati). Il corso si sviluppa in base alle principali tecniche 
algoritmiche (Greedy, Divide et Impera, Programmazione Dinamica e Backtracking) che sono 
esemplificate tramite numerosi esempi.
</p>
</DIV>
</DIV>
-->
---++ Programma
<div style="margin-left: 5%; margin-right: 10%;"> <div align="justify">

Il programma dettagliato del corso lezione per lezione lo trovate qui: [[%ATTACHURL%/Syllabus.pdf][Syllabus.pdf]]

Gli appunti saranno pubblicati durante lo svolgimento del corso alla fine di ogni lezione.

Qui i seguito trovate un programma di massima con le indicazioni di testi su cui gli argomenti sono trattati. 

---+++ *Grafi*

Rappresentazione tramite matrici di adiacenza e liste di adiacenza. Visite in ampiezza (BFS)
e in profondità (DFS). Alberi di visita e classificazione degli archi di una visita.
Componenti connesse e fortemente connesse, Ordinamento topologico.
Distanze in un grafo.

[Appunti del corso. Testo 1: Cap. 3, 4. Testo 3: Cap. 18. Testo 5: Cap. 11. Testo 6: Cap.7]

---+++ *Greedy*

Descrizione della tecnica e schema generale per dimostrare la correttezza di un algoritmo
Greedy. Algoritmi per Selezione Attività. Cammini minimi in grafi pesati:
algoritmo di Dijkstra. Minimo albero di copertura: algoritmo di di
Kruskal, strutture dati per insiemi disgiunti. Algoritmi di approssimazione e
quantificazione dell'errore. Il problema del ricoprimento tramite nodi (Vertex Cover).

[Appunti del corso. Testo 1: Cap. 4, 5. Testo 3: Cap. 15, 17, 19, 20, 33. Testo 4: Cap. 4, 11]

---+++ *Divide et Impera*

Descrizione della tecnica. Algoritmo per la ricerca
della coppia di punti più vicini. Il problema della selezione.

[Appunti del corso. Testo 1: Cap. 2. Testo 4: Cap. 5. Testo 5: Cap. 5, 10. Testo 6: Cap. 3]

---+++ *Programmazione Dinamica*

Descrizione della tecnica e confronto con Divide et Impera. Ricerca esaustiva e memoizzazione.
Dal calcolo del valore ottimo al trovare una soluzione ottima. Il problema dello Zaino
(Knapsack). Cammino più lungo in grafi aciclici (Longest Path in DAG). Pianificazione Attività (CPM).
Algoritmi di Bellman-Ford e di Floyd-Warshall.

[Appunti del corso. Testo 1: Cap. 6. Testo 2: Cap. 5. Testo 3: Cap. 14. Testo 4: Cap. 6. Testo 5: Cap. 10. Testo 6: Cap. 6]

---+++ *Backtracking*

Descrizione della tecnica. Enumerazione di strutture semplici: sottoinsiemi,
sequenze, permutazioni. Esplorazione dello spazio di ricerca, ovvero generazione delle
possibili soluzioni di un problema: 3-colorazione, ciclo Hamiltoniano.
Euristiche di taglio per problemi di ottimizzazione: Zaino.

[Appunti del corso. Test 1: Cap. 9. Testo 2: Cap. 7]

</div>
---+++ 

</div>

---++ Testi consigliati

<span style="background-color: transparent;">1) S. Dasgupta, C. Papadimitriou, U. Vazirani </span> _Algorithms_ <span style="background-color: transparent;">. Disponibile anche [[http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf][online]].</span>

2) E. Horowitz, S. Sahni _Fundamentals of Computer Algorithms_ Computer Science Press.

3) T.H. Cormen, C.E. Leiserson, R.L. Rivest, e altri. _Introduzione agli algoritmi e strutture dati_ MacGraw -Hill 2023

4) J. Kleimberg, E. Tardos Algorithm Design Addison Wesley, 2005

5) C. Demetrescu, I. Finocchi, G.F. Italiano <i>Algoritmi e Strutture di Dati. </i>MacGraw-Hill 2025

6) P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi _Strutture di dati e algoritmi._ Pearson 2012
<div style="margin-left: 5%; margin-right: 10%;"> </div>
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
pdf	Syllabus.pdf	r1	manage	45.4 K	2026-02-17 - 08:36	AngeloMonti
This topic: Algoritmi2 > WebHome > PALGprogramma2014
Topic revision: r15 - 2026-02-17 - AngeloMonti