Le site de l'Université Paris-Saclay est actuellement en cours de mise à jour suite à sa restauration, après la cyberattaque subie en août. Certaines informations peuvent ne pas être encore actualisées. Nous travaillons à les remettre à jour au plus vite. Dans l'intervalle, nous vous remerçions de votre compréhension.
M2 Algorithmique et Modélisation à l'Interface des Sciences
Ce parcours offre à des étudiants issus d'une licence d'informatique ou de mathématiques appliquées ou d'écoles d'ingénieurs une formation fondamentale de haut niveau en modélisation, notamment stochastique et probabiliste, et en algorithmique sous différentes approches, avec une ouverture vers des applications pour la résolution de problèmes énergétiques, de smart-cities et de problèmes liés à la modélisation moléculaire .
Lieu(x) d'enseignement
VERSAILLES
Compétences
Modéliser un problème.
Concevoir une solution informatique.
Proposer des solutions algorithmiques.
Débouchés de la formation
Cadres en informatique dans les entreprises, métiers de la recherche et du développement dans les universités, organismes de recherche privés et publics, les grandes entreprises et les start-up. Les métiers visés sont : chefs de projets, ingénieurs R & D, chercheurs.
Collaboration(s)
Laboratoire(s) partenaire(s) de la formation
Données et Algorithmes pour une ville intelligente et durable.
Programme
Ce semestre est composée d'un ensemble d'UE qui est le socle commun pour le parcours.
Algorithmique distribuée et algorithmique distribuée probabiliste.
Description des modèles, études d'algorithmes fondamentaux.
Introduction à la tolérance aux pannes dans les systèmes distribués.
Analyse des algorithmes distribués probabilistes.
Problématique des systèmes distribués à grande échelle et applications.
Modélisation de la dynamicité.
Preuves de tolérance à la dynamicité.
Contingentement des fautes et localité.
Analyse opérationnelle et notion de Bottleneck. Réseaux Fermés de Files d’attente et Analyse en Valeur Moyenne. Formule de Little. Propriétés de Markov. Processus de Naissance et Mort. Files Simples Markoviennes à une classe de clients, Formules d’Erlang, PASTA , Files à plusierus classes, notions de discipline de service (PS, LIFO), Réseaux ouverts de Files d’attente. Forme produit. Solution stationnaire à forme produit. Déla moyen de bout en bout. Réseaux à paquet de données et paquets d’energie. Modélisation des batteries et de la production d’energie intermittente.
Prérequis :
Notions de probabilités et de processus stochastiques.
Bibliographie :
- Jain, R., « The art of computer systems performance analysis - techniques for
experimental design, measurement, simulation, and modeling », Wiley professional computing, 1991.
- Bonald T. et Feuillet M., « Performance des réseaux et des systemes informa.
Séances de cours de 3h avec des exercices d'application.
Objectifs pédagogiques visés :
Contenu :
L'objectif de ce cours est de présenter différentes méthodes classiques des problèmes d'optimisation combinatoire : Branch and Bound, Branch and Cut, Programmation Dynamique, Génération de Colonnes, Programmation Par Contraintes. L'application de ces différentes méthodes sera illustrée sur un ensemble de problèmes et d'applications classiques d'optimisation combinatoire.
Prérequis :
Programmation Linéaire, (Méta)Heuristiques.
Bibliographie :
Papadimitriou C. and Steiglitz K., Combinatorial Optimization : algorithms and complexity, 1998
Korte B. and Vygen T., Optimisation Combinatoire, théorie et algorithmes, 2015.
Ce cours présente des notions générales ainsi qu'un ensemble de méthodes d'apprentissage supervisé permettant de faire de la classification automatique de données. On abordera des méthodes simples (méthode des plus proches voisins, perceptron, machines à vecteurs de support, régressions) ainsi que des méthodes modernes (arbres de décision, réseaux de neurones, réseau de convolution, deep learning). Certaines notions d'apprentissage non-supervisé pourront être évoquées (méthode des k-moyennes, clustering).
Théorie algorithmique des jeux et apprentissage par renforcement
Langues d’enseignement :
FR
ECTS :
3
Détail du volume horaire :
Cours :21
Modalités d'organisation et de suivi :
Coordinateur :
Equipe pédagogique :
David Auger, UVSQ. Yann Strozecki, UVSQ.
Déroulement et organisation pratique :
Le cours sera structuré en 7 séances de 3 heures. Des exercices seront donnés durant ces séances.
L’évaluation sera composée pour moitié par une note d’examen et pour l’autre moitié par une évaluation reposant sur la lecture d’un article en lien avec les thèmes du cours, qui fera également l’objet d’un développement de programme.
Objectifs pédagogiques visés :
Contenu :
L’objectif de ce cours est d’une part de connaître les modèles de théorie des jeux permettant de représenter les situations de compétition entre plusieurs agents, et d’autre part de savoir les résoudre. Une partie du cours sera consacrée à l’étude de modèles Markoviens pour lesquels des méthodes d’apprentissage reposant sur des expériences autorisent à s’affranchir de la connaissance préalable du modèle (par ex. algorithme TD(0) et algorithme de q-learning). Une autre partie sera consacrée aux jeux simultanés et au calcul des équilibre de Nash. Dans ce cadre, nous étudierons des algorithmes de résolution exacte nécessitant la connaissance complète du modèle (ex. algorithme de Lemke-Howson) et des algorithmes d’apprentissage en ligne (ex. algorithme fictitious play). Des applications seront ensuite abordées : jeux de routage, problème de mariage stable, problème du partage équitable...
Prérequis :
Bases de la théorie des probabilités et des chaînes de Markov. Bases d’algorithmique.
Bibliographie :
*Algorithmic Game Theory, Noam Nisan et al
* Reinforcement Learning: An Introduction, Sutton and Barto.
Séances de cours magistraux avec propostion d’exercices, de 3h chacune.
Objectifs pédagogiques visés :
Contenu :
Après un rappel des définitions des bases de la théorie des graphes, avec des exemples de résultats théoriques et une justification théorique de problèmes polynomiaux dans les graphes, le cours définiera la thèorie de la NP-complétude. Des problèmes NP-complets classiques dans les graphes (coloration, recherche de sous-graphes, Steiner, …) seront ensuite traitées. Enfin, les concepts d’aproximabilité seront définis et illustrés par des exemples de problèmes de graphes.
Prérequis :
Fondements de l’algorithmique. Algorithmique dans les arbres.
Bibliographie :
A. Bondy, USR Murty. Graph theory. Springer, 2007.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms 3e. The MIT Press, 2009.
Par groupes de 3/4 personnes, le projet devra être développé de bout en bout de la modélisation à une maquette opérationnelle.
Objectifs pédagogiques visés :
Contenu :
Projet
Plusieurs orientations sont possibles pour le projet en relation avec les cours fondamentaux du premier semestre : Telecom, Gestion de l'énergie, Modélisation moléculaire ....
Ce semestre comporte un stage et un ensemble d'UE d'ouverture sur les domaines d'application : ville intelligente, sciences humaines et sociales, chémo-informatique ...
On présente dans ce cours les méthodes d'apprentissage automatique qui sont utilisées pour créer des
intelligences artificielles performantes pour des jeux de stratégies complexes (échecs, go) ou à certains jeux vidéos simples. Ce cours
est basé sur des méthodes d'apprentissage profonds (réseau de neurones) ainsi que d'apprentissage par renforcement (méthodes de bandits, Monte-Carlo Tree Search).
Séances de cours magistraux de 3h chacune avec proposition d’exercices.
Objectifs pédagogiques visés :
Contenu :
Introduction systémique à la problématique de la mobilité urbaine.
Gestion de trafic : algorithmique pour la gestion de flots et pour le routage.
Machine learning pour la gestion de véhicules, en particulier autonomes.
Mobilité urbaine et applications numériques à l’usager.
Techniques de prédiction de la mobilité.
Sûreté de fonctionnement pour les systèmes dédiés à la mobilité.
Prérequis :
Bases de théorie des jeux et apprentissage
Bases d’algorithmique de graphes
Modélisation stochastique.
Bibliographie :
1. P. Berrone, J.E. Ricart Costa, A. Duch T-Figueras. Cities and Mobility & Transportation: Towards the next generation of urban mobility. IESE CITIES IN MOTION: International urban best practices book series (Book 2)
2. M. Rausand, Risk Assessment : Theory, Methods, and Applications, John Wiley & Sons, 2011.
7 cours suivsi d’un exposé sur un article de recherche.
Objectifs pédagogiques visés :
Contenu :
Le cours propose d’étudier comment limiter la consommation énergétique des systèmes de télécommunications et plus généralement du transfert et du traitement de données. On va traiter des aspects algorithmiques et modélisations liés à différentes technologies de transmission de données :
réseaux tout optiques pour éviter les passages électronique/optique : comment gérer l’absence de buffer optique de grande capacité et l’impossibilité du routage « store and forward ». Routage à déflection, routage Eulerien, routage mixte, contrôle d’accès.
Réseaux Hertzien à très basse consommation et très faible bande passante (type LORAWAN) : agréger les données pour limiter la bande passante, agrégation spatiale et temporelle des données.
Compétences:
Modéliser des réseaux
Optimisation de réseaux et de la consommation énergétique
Technologies réseaux innovantes (optique, faible consommation).
Prérequis :
Notions d’évaluation de performance et d’algorithmique du routage.
Fiche de choix de M2 (obligatoire pour les candidats inscrits en M1 à l'Université Paris-Saclay) à télécharger sur https://urlz.fr/i3Lo.
Document justificatif des candidats exilés ayant un statut de réfugié, protection subsidiaire ou protection temporaire en France ou à l’étranger (facultatif mais recommandé, un seul document à fournir) :
- Carte de séjour mention réfugié du pays du premier asile
- OU récépissé mention réfugié du pays du premier asile
- OU document du Haut Commissariat des Nations unies pour les réfugiés reconnaissant le statut de réfugié
- OU récépissé mention réfugié délivré en France
- OU carte de séjour avec mention réfugié délivré en France
- OU document faisant état du statut de bénéficiaire de la protection subsidiaire en France ou à l’étranger.
