Séminaires 2018/2019

Jeudi 10h-12h

Jeudi 11 Octobre : Araujo Alexandre, Kevin Osanlou - Salle P301

Jeudi 8 Novembre : Carion Nicolas ; Céline Beji - Salle P301

Jeudi 6 Décembre : Antoine Kerbérénès, George Butler - Salle  P301

Jeudi 17 Janvier : Timothée Sohm-Quéron, Eric Benhamou - Salle C108

Jeudi 14 Février : Louis Dublois, Marcel Haddad - Salle C108

Jeudi 14 Mars : Mehdi Acheli, Zakariae Aloulen - Salle C108

Jeudi 11 Avril : Ons Nefla, Antoine Richard - Salle C108

Jeudi 9 Mai : Raja Trabelsi, Boris Doux - Salle C108

Jeudi 6 Juin : Ahlam MOUACI, Hossein Khani - Salle C108


Dates des Cours ED d’Informatiques 2018-2019 


Cours 1 : Ridha Mahjoub

Octobre : 4 (Salle A709), 11 (D102), 18 (à venir), November :  8, 15, 22(Salle D102)

Cours 2 : Vangelis Paschos

November : 29 (Salle D102), Décembre : 6, 13, 20  (Salle D102), Janvier : 10, 17

Cours 3 :Fabio Furini

Janvier 24 , 31 (P301), Février : 7 (C131), 14 (A701), 21 (A303), Mars : 14 (A308)

Cours 4 :Ararat Harutyunyan

Mars : 21 (B203), 28 (A711), Avril : 4 (A711), 11 (P301), 18 (C108), Mai 9 (A707)

Cours 5 : Sana Mrabet

Mai : 16(A711), 23(C108), Juin : 6(A711), 13(A711), 20 (A707), 27 (C131)


COURS 1 (Octobre - Novembre)

Titre : Exact and Approximation Algorithms for Network Design

Intervenants: Ridha Mahjoub

Volume horaire : 18h, 3 fois 6h, les Jeudi après midi 14h-17h.

Dates: Octobre : 4, 11, 18, November : 8, 15, 22


Description: Network design problems arise in many domains, transport, telecommunications, computer science etc. For the past few decades, combinatorial optimization techniques have shown to be powerful tools for formulating, analysing and solving optimization problems arising from practical decision situations. In particular, many network design problems have been formulated as combinatorial optimization models. A big amount of research has also been done for designing algorithmic approaches for these models.  The aim of this course is to discuss efficient exact and approximation algorithms for some variants of networks design problems. Connectivity and trees are very important concepts in network design. Indeed, one of the main problems is to design a network satisfying some connectivity requirements. Another important problem is to determine an optimal tree, a tree connecting some special nodes, called terminals. We will particularly discuss these two problems. Exact and approximation algorithms, based on linear and integer programming and iterative methods, will be presented. Iterative methods, which consist in iteratively rounding fractional linear programming solutions, are one of the main tools for designing approximation algorithms for combinatorial optimization problems. Applications of these techniques to other problems will also be studied. A multi-commodity flow in a network is a set of flows between some pairs of origin-destinations. A large class of network design problems can be seen as multi-commodity flow problems. In this course, we will also discuss the relation between the two classes of problems. 


COURS 2 (Novembre – Décembre - Janvier)

Titre: Approximation Polynomiale et Super-polynomiale des problèmes NP-difficiles


Intervenants: Vangelis Paschos


Volume horaire : 18h, 3 fois 6h, les Jeudi après midi 14h-17h.

Dates: November : 29, Décembre : 6, 13, 20, Janvier : 10, 17 (B302)



-- Notions d'approximation des problèmes NP-difficiles

-- Approximation polynomiale:

** Problématique

** Types de résultats (positifs, négatifs, conditionnels)

** Méthodes algorithmiques pour l'approximation polynomiale

-- Approximation Super-polynomiale

** Pourquoi l'Approximation Super-polynomiale

** Méthodes algorithmiques

** Sparcification



M. R. Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman 1979.

C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice Halln, 1981.

V. Th. Paschos, Complexité et approximation polynomiale Hermès, 2004.


COURS 3 (Janvier-Février-Mars)

Titre: Column Generation

 Intervenants : Fabio Furini

Volume horaire : 18h, 3 fois 6h, les Jeudi après midi 14h-17h.

Dates : Janvier 24, 31, Février : 7, 14, 21, Mars : 14

Description: Course Description: Integer Programming (IP) is a very powerful tool for modeling combinatorial optimization problems arising in many branches of engineering, industry, production planning, resource allocation and many others. The first part of the course covers the modeling aspects of the field, providing the tools for constructing effective mathematical models, i.e., models that can be solved in practice. The second part is devoted to the algorithmic aspects: basic algorithms are reviewed and more sophisticated ones, useful for those models characterized by a large number of variables and/or constraints, are presented in detail. Finally, the third part of the course discusses real-world applications Finance, Data Science and Production Management.

Course Objectives:  At the completion of this course, students will be able to: i) Starting a from a case-study develop a IP formulation of a real-world optimization problem;  ii) Implement and solve IP models using state-of-the-art commercial solvers; iii) Implementation of a branch-and-price algorithm.


Text (a): ''Integer Programming'', Author(s): Laurence A. Wolsey;  ISBN-13: 978-0471283669

Text (b): ''Column Generation'', Author(s): Guy Desaulniers, Jacques Desrosiers, Marius M. Solomon;  ISBN-13: 978-1441937995


COURS 4 (Mars - Avril - Mai)

Title: Probabilistic Methods

Intervenants: Ararat HARUTYUNYAN

Volume horaire : 18h, 3 fois 6h, les Jeudi après midi 14h-17h.

Dates : Mars : 21, 28, Avril : 4, 11, 18, Mai 9.  

Description: A graduate course for the students of LAMSADE/CEREMADE. One of the powerful tools in Discrete Mathematics is the use of probability theory to prove deterministic results.

Often to prove the existence of a structure, one can define a probability space on a general set of objects and show that an object chosen uniformly at random from this space has the desired structure with positive probability. 

Pre-requisites: General mathematical maturity. A preliminary knowledge of probability theory would certainly be helpful, but is not required.


-  the basic method, basic examples from graph theory and combinatorial number theory

-  linearity of expectation, the first moment method

-  Ramsey theory and combinatorial geometry

-  Random graphs

-  Existence of graphs with counter-intuitive properties

-  The Lovasz Local Lemma and its applications

-  Correlation and the second moment method: Chebyshev and Janson inequalities

-  Concentration: the Azuma, Talagrand and McDiarmid inequalities

-  A few randomized algorithms


N. Alon, J. Spencer, The probabilistic method

Janson, Luczak, Ruczinski, Random graphs.

Motwani, Raghavan, Randomized algorithms.


COURS 5 (Décembre, Février et Avril)

Title: Evolutionary Algorithms for Optimization and Machine Learning

Intervenants: Sana Ben Hamida

Volume horaire : 18h, 3 fois 6h, les Jeudi après midi 14h-17h.

Dates: Mai : 16, 23, Juin : 6, 13, 20, 27


Description: The Evolutionary Algorithms are metaheuristics that use the metaphor of the Darwinian or Lamarckian evolution theories to find efficient solutions for hard optimization problems or machine learning.

This course introduces the generic evolutionary algorithm as well as the basic operators that compose it. It describes how to solve continuous optimization problems, with and without constraints, using evolutionary algorithms. The first part of the course is extended with an introduction to the multi-objective optimization and summarizes a variety of approaches for its application. The second part of the course deals with combinatorial optimization. It provides a set of variation operators to deal with order-based problems and an example of application to the Traveling Salesman Problem. Finally, the last part of the course describes different approaches of Genetic Programming (GP) able to evolve computer programs in the context of machine learning. It details how computer programs are encoded and evolved with GP. It also presents some efficient variants of GP such as Linear GP or Cartesian GP and some solution to scale up GP to learn from very large date sets.  Some examples of application are presented with some guidelines for the use of GP to solve a symbolic regression problem and a data classification problem.


• Main reference: Alain PETROWSKI and Sana BEN HAMIDA, “EVOLUTIONARY ALGORITHMS”, ISTE, Wiley, 2017.

• Other references:

• Poli Langdon ,“A Field Guide to Genetic Programming” by, McPhee. 2008.

•  Alex A Freitas, “Data Mining and Knowledge Discovery with Evolutionary Algorithms”, Springer-Verlag, 2012.


Vous pouvez aussi suivre les cours offerts par les formations doctorales PSL http://collegedoctoral.univ-psl.fr/vie-doctorale-et-valorisation-de-la-these/catalogue-de-formation/.