Télécom ParisTech

Filière Mathématique, Informatique théorique et Recherche opérationnelle (MITRO)

Cette filière s'adresse aux étudiants cherchant une formation approfondie à l'interface entre informatique et mathématiques ou aux étudiants inscrits dans d’autres filières voulant asseoir leur formation par des compléments théoriques. Elle est particulièrement recommandée à ceux qui désirent poursuivre en doctorat en informatique.

La filière forme de futurs ingénieurs qui souhaitent être suffisamment outillés pour analyser et résoudre des problèmes mathématiques et algorithmiques difficiles par des approches variées (Cours d’optimisation combinatoire MITRO205, d’algorithmique avancée MITRO208, de théorie des jeux MITRO206), en comprendre les limites (Cours de complexité MITRO203) et pour maitriser les tenants et aboutissants de la programmation et de leurs langages (Cours de calculabilité MITRO201, de logique MITRO202, d’automates MITRO204, de calcul distribué MITRO207).

La troisième année de la filière se fait exclusivement au sein des masters  AFP (ex-MPRI), FIIL et RO de la thématique « Informatique fondamentale et applications » de l’université Paris-Saclay ou dans des formations équivalentes à l’étranger.

Zoom : cours de 2e année

MITRO programmation de 2e année (192 h) 1er semestre

2e semestre

Période 1 Période 2 Période 3 Période 4
Créneau B1 MITRO201 Logique MITRO204 Automates et transducteurs MITRO205 Optimisation combinatoire et analyse combinatoire MITRO207
Calcul réparti par topologie combinatoire
Créneau B2 MITRO202 Calculabilité MITRO203 Complexité MITRO206
Théorie des jeux
MITRO208
Advanced algorithms

Détails :

Premier semestre, période 1

  • MITRO 201 Logique (Jean Leneutre) (24 heures)
    Ce cours propose une introduction à la logique mathématique et ses liens avec l’informatique. L’objectif est de décrire aussi bien la sémantique que la théorie des preuves de différentes logiques.  Le cours commencera par présenter la logique classique propositionnelle et du premier  ordre : sémantique, systèmes de déduction (système de Hilbert, déduction naturelle, calcul des séquents LK), théorèmes d’adéquation et de complétude, théorème de compacité, théorème d’élimination des coupures. Il décrira ensuite la logique intuitionniste :calcul des séquents LJ. Traduction de la logique classique vers la logique intuitionniste. Enfin,  une introduction à la logique linéaire sera proposée : sémantique des phases et sémantique des espaces cohérents, calcul des séquents et réseaux de preuves.
  • MITRO 202 Calculabilité (Patrick Bellot) (24 heures)
    Cette partie met l’accent sur la calculabilité indépendamment des problèmes de complexité. Une donnée est effectivement calculable ou non, indépendamment des conditions en temps ou en mémoire. Nous passerons en revue les différentes théories de la calculabilité ainsi que le
    principal résultat qui est la thèse de Church. Nous verrons en particulier la théorie des combinateurs et le lambda-calcul.
    Nous verrons quelques théorèmes d’impossibilité qui en découlent. Nous montrerons comment la théorie de types résout les paradoxes, la
    correspondance de Curry-Howard et la réalisabilité.

Premier semestre, période 2

  • MITRO 203 Complexité (Olivier Hudry) (24 heures)
    Ce cours propose une introduction à la théorie de la complexité des problèmes d’optimisation combinatoire (théorie de la NP-complétude). L’objectif est de donner un sens et des éléments de réponse à la question suivante : dans quelle mesure peut-on dire qu’un problème est intrinsèquement difficile à résoudre d’un point de vue algorithmique ? Les concepts abordés sont les suivants : machines de Turing (déterministes ou non déterministes), problèmes de décision, liens entre problèmes d’optimisation et problèmes de décision, classes P et NP, transformations polynomiales, transformations de Turing, problèmes polynomiaux, NP-complets, NP-difficiles, hiérarchie polynomiale.
  • MITRO 204 Automates et transducteurs (Jacques Sakarovitch) (24 heures)
    Les automates finis sont le modèle le plus simple de machines qui calculent, le premier dans toute hiérarchie des machines de Turing plus ou moins contraintes. Cette simplicité en fait un objet robuste, susceptible de nombreuses définitions équivalentes, relevant de la théorie de la complexité, de l’algèbre non-commutative et de la logique. Les automates finis, enrichis par les notions de multiplicité et de sortie, constituent alors un modèle assez puissant pour exprimer des propriétés non triviales et sont utilisés comme outil dans des domaines aussi variés que le traitement des langues naturelles, la vérification de systèmes et des protocoles, etc. Les problèmes rencontrés dans chacun de ces domaines relèvent souvent de la théorie des automates et ne se heurtent pas immédiatement au mur de l’indécidabilité: il y a de l’espace pour des résultats profonds. Ainsi, cette théorie est-elle un chapitre de base de l’informatique théorique. L’objectif de ce cours est essentiellement la description et l’étude des relations entre mots réalisées par des automates finis, en général appelés transducteurs. On commence dans les premières leçons à étudier les automates finis sur des monoïdes généraux et avec multiplicité dans N, uniquement dans la mesure où cela sert cet objectif.

Deuxième semestre, période 3

  • MITRO 205 Optimisation combinatoire et analyse combinatoire (Olivier Hudry) (24 heures)
    L’une porte sur des méthodes d’optimisation combinatoire générales permettant de résoudre des problèmes difficiles (plus précisément, NP-difficiles). On décrit en particulier les méthodes arborescentes par séparation et évaluation, la programmation dynamique, la relaxation lagrangienne, certaines métaheuristiques. On y aborde aussi des problèmes classiques en recherche opérationnelle, comme le problème du voyageur de commerce, le problème du sac à dos ou encore le problème de la coloration de graphes. Des travaux pratiques en C ou en Java viennent compléter la présentation théorique de ces méthodes.
    L’autre, issue des mathématiques discrètes, est consacrée à l’analyse combinatoire, autrement dit à l’art du dénombrement ou encore à l’art de compter. On y définit les séries génératrices ordinaires ou exponentielles, le nombre de combinaisons avec ou sans répétitions, le principe d’inclusion-exclusion (théorème de Poincaré), les dérangements, le dénombrement de partitions (nombres de Stirling), etc.
  • MITRO 206 Théorie des jeux (David Madore) (24 heures)
    Ce cours présente des aspects variés de la théorie des jeux et de ses applications. Une partie sera consacrée à la théorie probabiliste des jeux définis par des matrices de gains (jeux à somme nulle ou non, optimisation et équilibres de Nash). Une autre se penchera sur la théorie combinatoire des jeux à information complète (théorie de Sprague-Grundy pour les jeux impartiaux, et théorie de Conway des jeux partiaux, introduction aux nimbres et nombres surréels). Une troisième partie sera consacrée aux applications de la théorie des jeux aux réseaux de télécommunications. Si le temps le permet, des applications à la logique pourront aussi être évoquées.

Deuxième semestre, période 4

  • MITRO 207 Calcul réparti par topologie combinatoire (Petr Kuznetsov) (24 heures)
    Le principal objectif de ce cours est d'apprendre les techniques d'analyse des algorithmes distribués pour les systèmes réels combinant parallélisme avec des retards imprévisibles, tels que les multi-noyaux, réseaux sans fil, les systèmes distribués, et des protocoles Internet. Un accent particulier sera mis sur les méthodes de calcul mathématique fondées sur la topologie combinatoire.
  • MITRO 208 Algorithmique avancée (Bertrand Meyer) (24 heures)
    Ce cours commence par quelques révisions sur quelques structures mathématiques discrètes (relations, ordres, treillis, matroïdes) utiles en optimisation combinatoire. Dans une seconde partie, il s’intéresse à l’approximation de problème NP-difficile avec garantie de performance. Enfin, dans une dernière partie, il s’intéresse à l’apport de l’aléa en algorithmique.

Options de 3e année

Choix entre les formations suivantes :

Option interne QRScrypt

120 heures de cours et 120 heures de Projet Innovation Master PRIM. Cours de Master 2.

Master 2 en partenariat

  • FIIL, Fondements de l’informatique  et Ingénierie du Logiciel de l'Université Paris-Saclay, mention informatique
  • RO, Recherche Opérationnelle de l'Université Paris-Saclay, mention informatique
  • AFP, Algorithmics and Foundations of Programming, (parcours principalement en anglais)
    (anciennement MPRI, Master Parisien de recherche en informatique)

Formation équivalente à l'étranger 

Il est aussi possible de choisir un cursus transverse (option entrepreneuriat) ou un des cursus alternatifs.