ALGORITHM DESIGN

Obiettivi formativi

L'obiettivo del corso è quello di introdurre i concetti fondamentali della progettazione di algoritmi per problemi polinomiali e problemi computazionali difficili. Il corso presenterà i concetti di base di progettazione di algoritmi per problemi di flusso nelle reti e problemi di matching. Tecniche generali come greedy e programmazione e dinamica saranno applicate a problemi di cammino minimo, spanning tree, knapsack. Algoritmi di approssimazione saranno presentati per problemi computazionali difficili come TSP, vertex cover set cover, sat, scheduling. Particolare enfasi sarà data ai metodi basati sulla programmazione lineare e gli algoritmi randomizzati. Infine , il corso introdurrà i principali problemi computazionali in teoria dei giochi.

Canale 1
STEFANO LEONARDI Scheda docente

Programmi - Frequenza - Esami

Programma
1 Lecture Overview of Algorithm Analysis Kleinberg and Tardos, Ch. 2.1 - 2.4 2 Lecture Stable Matching Kleinberg and Tardos, Ch. 1.1, 1.2 3 Lecture Network Flow: Ford and Fulkerson, Capacity Scaling, Shortest Augmenting Paths Kleinberg and Tardos, Ch. 7.1, 7.2, 7.3 4 Lecture Perfect Matching, Circulations, Improved algorithm for bipartite matching (Ascending Price Matching, Hopcroft-Karp) Kleinberg and Tardos, Ch. 1.1, 7.5, 7.7 5 Lecture Greedy Algorithms 6 Lecture Dynamic Programming Kleinberg and Tardos, Ch. 4.1, 4.4, 6.1, 6.2, 6.4, 6.4, 6.8 slides 7 Lecture Basics of complexity and NP-completeness 8 Lecture 8 Basics of approximation algorithms Reference [4], Chapters 1 and 3 slides 9 Lecture Basics of approximation algorithms Reference [4], Chapters 2.1, 8.1, 8.2 slides 10 Lecture Linear Programming based approximation algorithms Reference [4], Chapters 12 11 Lecture Basics of Randomized Algorithms Reference [5], Chapter 5 12 Lecture Introduction to Game Theory and Equilibria Computation Lecture Notes 13 Lecture Computing Equilibria in Zero-Sum Games and Efficiency of Equilibria Lecture Notes 14 Lecture Selfish Routing and Price of Anarchy See Lecture Notes of Lecture 14 and Exercises, Section 2
Prerequisiti
Un corso di base in algoritmi e programmazione
Testi di riferimento
[1] J. Kleinberg and E. Tardos, Algorithm Design. Addison Wesley, Pearson Education, 2005. Additional material on the book can be found here: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/
Frequenza
In person a
Modalità di esame
There are two possibilities for passing the exam: 1) The first and most advised one is to submit the two Homeworks before deadline. The homeworks will be discussed during the exam. 2) The second one is to answer two questions on the topics of the first homework (Fundamental design methods and Poly-time algorithms) and three questions on the topics of the second homework (Approximation of hard problems and Computational game theory) during in the written exam. The student that either fails or does not submit the only first/second homework will answer only two/three questions in the written exam.
Modalità di erogazione
Lezioni ed Esercitazioni
  • Codice insegnamento1044417
  • Anno accademico2025/2026
  • CorsoEngineering in Computer Science and Artificial Intelligence - Ingegneria Informatica e Intelligenza Artificiale
  • CurriculumCurriculum unico
  • Anno1º anno
  • Semestre2º semestre
  • SSDING-INF/05
  • CFU6