PERIODO: MAY - JUNE

Il corso sarà tenuto dal Prof. J. C. Billaut dell'Università di Tours.



Graphs is a structure amounting to a set of objects, in which some pairs of objects are in some sense “related”. The objects are called vertices, the related pairs of vertices are represented by arcs. A graph is a mathematical abstraction for representing a problem, and the study of the graphs rely to the graph theory, one specific tool of discrete mathematics.
Among the problems often studied in graph theory are the network flow problems. After an introduction to the graph theory, the Minty’s painting lemma will be introduced and demonstrated. This lemma is at the heart of several flow research algorithms: for solving the maximum flow problem, the feasible flow problem, and the min-cost flow problem.

Dynamic programming is an optimization method for solving complex optimization problems, based on the decomposition of the main problem into a collection of simpler subproblems, and linking the solutions together by a recursive formula. This method finds applications in mathematics, management science, economics, computer science, bioinformatics, etc.
After the introduction of basic notions of the theory of complexity, this method will be applied to basic scheduling problems, leading to polynomial time, pseudo-polynomial time or exponential time algorithms.


Timetable

Wednesday May 24 9-13 Classroom C
Friday May 26 9-13 Classroom C
Monday May 29 9-13 Classroom C
Wednesday May 31 9-13 Classroom C
Thursday June 1 14-18 Classroom C