---+ 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
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
Copyright © 2008-2026 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback