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
teacher profile teaching materials
Review of algorithm theory and computational complexity: complexity classes, the class of NP, NP-complete, NP-hard problems. Problems of decision, search, enumeration and optimization; problems of nonlinear programming, convex programming, linear programming and integer linear programming; combinatorial optimization problems. Recalls on the elements of combinatorics.
Optimization problems on graphs: visit of graphs, verification of fundamental properties, connection, presence of cycles, strongly connected components, topological ordering of a graph. Minimum spanning tree (Prim and Kruskal algorithms). Paths of minimum cost (Dijkstra and Bellman-Ford algorithms, dynamic programming technique, Floyd-Warshall algorithm, computation of the transitive closure of a graph). Networks and calculation of the maximum flow on a network, maximum flow / minimum cut theorem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, preflow algorithms, "push-relabel" algorithms.
Partitioning problems of graphs, trees and paths into connected components, objective functions and algorithmic techniques.
Stable marriage problem, generalizations and applications of the problem, Gale and Shapley algorithm.
Huffman codes.
Programming laboratory for the implementation of algorithms in Python language and with the help of Mathematica software.
Lecture notes and other teaching material in Italian provided by the teacher and made available on the course website (http://www.mat.uniroma3.it/users/liverani/IN440) and on the Microsoft Teams platform
Fruizione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 LIVERANI MARCO
Programme
Notes on graph theory: graph, directed graph, tree, free and rooted tree, connection, strong connection, acyclicality; isomorphisms between graphs, planarity, Kuratowski's theorem, Euler's formula; coloring of graphs, Eulerian paths, Hamiltonian circuits.Review of algorithm theory and computational complexity: complexity classes, the class of NP, NP-complete, NP-hard problems. Problems of decision, search, enumeration and optimization; problems of nonlinear programming, convex programming, linear programming and integer linear programming; combinatorial optimization problems. Recalls on the elements of combinatorics.
Optimization problems on graphs: visit of graphs, verification of fundamental properties, connection, presence of cycles, strongly connected components, topological ordering of a graph. Minimum spanning tree (Prim and Kruskal algorithms). Paths of minimum cost (Dijkstra and Bellman-Ford algorithms, dynamic programming technique, Floyd-Warshall algorithm, computation of the transitive closure of a graph). Networks and calculation of the maximum flow on a network, maximum flow / minimum cut theorem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, preflow algorithms, "push-relabel" algorithms.
Partitioning problems of graphs, trees and paths into connected components, objective functions and algorithmic techniques.
Stable marriage problem, generalizations and applications of the problem, Gale and Shapley algorithm.
Huffman codes.
Programming laboratory for the implementation of algorithms in Python language and with the help of Mathematica software.
Core Documentation
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to algorithms"Lecture notes and other teaching material in Italian provided by the teacher and made available on the course website (http://www.mat.uniroma3.it/users/liverani/IN440) and on the Microsoft Teams platform
Type of delivery of the course
The course takes place face to face in the traditional way in the classroom and in the computer lab. Lessons will be recorded and made available on the Teams platform, but attendance in person is recommended.Attendance
Attendance of the lessons of the course is strongly recommended, but it is not compulsory.Type of evaluation
The oral exam, in which some of the algorithms covered in the course will be discussed, is preceded by the presentation and discussion of a written thesis, on a topic assigned by the teacher, in which it is required, among other things, to implement the algorithms present in the material provided by the teacher for the preparation of the thesis itself. teacher profile teaching materials
Review of algorithm theory and computational complexity: complexity classes, the class of NP, NP-complete, NP-hard problems. Problems of decision, search, enumeration and optimization; problems of nonlinear programming, convex programming, linear programming and integer linear programming; combinatorial optimization problems. Recalls on the elements of combinatorics.
Optimization problems on graphs: visit of graphs, verification of fundamental properties, connection, presence of cycles, strongly connected components, topological ordering of a graph. Minimum spanning tree (Prim and Kruskal algorithms). Paths of minimum cost (Dijkstra and Bellman-Ford algorithms, dynamic programming technique, Floyd-Warshall algorithm, computation of the transitive closure of a graph). Networks and calculation of the maximum flow on a network, maximum flow / minimum cut theorem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, preflow algorithms, "push-relabel" algorithms.
Partitioning problems of graphs, trees and paths into connected components, objective functions and algorithmic techniques.
Stable marriage problem, generalizations and applications of the problem, Gale and Shapley algorithm.
Huffman codes.
Programming laboratory for the implementation of algorithms in Python language and with the help of Mathematica software.
Lecture notes and other teaching material in Italian provided by the teacher and made available on the course website (http://www.mat.uniroma3.it/users/liverani/IN440) and on the Microsoft Teams platform
Fruizione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 LIVERANI MARCO
Programme
Notes on graph theory: graph, directed graph, tree, free and rooted tree, connection, strong connection, acyclicality; isomorphisms between graphs, planarity, Kuratowski's theorem, Euler's formula; coloring of graphs, Eulerian paths, Hamiltonian circuits.Review of algorithm theory and computational complexity: complexity classes, the class of NP, NP-complete, NP-hard problems. Problems of decision, search, enumeration and optimization; problems of nonlinear programming, convex programming, linear programming and integer linear programming; combinatorial optimization problems. Recalls on the elements of combinatorics.
Optimization problems on graphs: visit of graphs, verification of fundamental properties, connection, presence of cycles, strongly connected components, topological ordering of a graph. Minimum spanning tree (Prim and Kruskal algorithms). Paths of minimum cost (Dijkstra and Bellman-Ford algorithms, dynamic programming technique, Floyd-Warshall algorithm, computation of the transitive closure of a graph). Networks and calculation of the maximum flow on a network, maximum flow / minimum cut theorem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, preflow algorithms, "push-relabel" algorithms.
Partitioning problems of graphs, trees and paths into connected components, objective functions and algorithmic techniques.
Stable marriage problem, generalizations and applications of the problem, Gale and Shapley algorithm.
Huffman codes.
Programming laboratory for the implementation of algorithms in Python language and with the help of Mathematica software.
Core Documentation
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to algorithms"Lecture notes and other teaching material in Italian provided by the teacher and made available on the course website (http://www.mat.uniroma3.it/users/liverani/IN440) and on the Microsoft Teams platform
Type of delivery of the course
The course takes place face to face in the traditional way in the classroom and in the computer lab. Lessons will be recorded and made available on the Teams platform, but attendance in person is recommended.Attendance
Attendance of the lessons of the course is strongly recommended, but it is not compulsory.Type of evaluation
The oral exam, in which some of the algorithms covered in the course will be discussed, is preceded by the presentation and discussion of a written thesis, on a topic assigned by the teacher, in which it is required, among other things, to implement the algorithms present in the material provided by the teacher for the preparation of the thesis itself.