Acquire skills on key solution techniques for combinatorial optimization problems; improve the skills on graph theory; acquire advanced technical skills for designing, analyzing and implementing algorithms aimed to solve optimization problems on graphs, trees and flow networks.
Curriculum
scheda docente
materiale didattico
2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.
Mutuazione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 R BONIFACI VINCENZO
Programma
1. Optimization and combinatorial optimization problems. Enumeration of solutions.2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.
Testi Adottati
Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.Modalità Frequenza
Class participation is advised but not compulsory.Modalità Valutazione
The oral exam consists of an in-depth examination at the blackboard.
scheda docente
materiale didattico
2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.
Mutuazione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 R BONIFACI VINCENZO
Programma
1. Optimization and combinatorial optimization problems. Enumeration of solutions.2. Basics of algorithm analysis. Computational tractability. Asymptotic order of growth.
3. Graphs. Graph connectivity and graph traversal. Graph bipartiteness. Connectivity in directed graphs. Directed acyclic graphs and topological ordering.
4. Greedy algorithms. Interval scheduling. Optimal caching. Shortest paths in a graph. Minimum spanning trees.
5. Divide and conquer. Mergesort. Counting inversions. Closest pair of points.
6. Dynamic programming. Weighted interval scheduling. Principles of dynamic programming. Subset sums and knapsacks. All-pairs shortest paths. Shortest paths and distance vector protocols.
7. Network flow. Maximum flow and the Ford-Fulkerson algorithm. Maximum flows and minimum cuts in a network. Augmenting paths. Bipartite matching. Disjoint paths in directed and undirected graphs.
8. Computational intractability. Polynomial-time reductions. Reductions via "gadgets". Efficient certification and the definition of NP. NP-complete problems. Covering, packing, partitioning, sequencing, and numerical problems. Other examples.
Testi Adottati
Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.Modalità Frequenza
Class participation is advised but not compulsory.Modalità Valutazione
The oral exam consists of an in-depth examination at the blackboard.