Les algorithmes distribués sont à la base de systèmes et applications réparties, comme par exemple : l’Internet, l’Internet des objets, le Cloud, Bitcoin, etc. En plus des difficultés liées à la répartition géographique et l’évolution dynamique de leurs composants, ces systèmes réels sont soumis à des défaillances : arrêts de fonctionnement, corruptions de mémoire, comportements de participants malveillants, etc.

Pour garantir le fonctionnement correct de tels systèmes, un enjeu majeur est de savoir gérer la dynamique et les défaillances, qui se multiplient du fait du passage à la grande échelle. Ce module présente une technique majeure pour tolérer un nombre borné de variété de défaillances (définitifs), en les masquant complètement.

Les objectifs de ce modules sont de:

• donner les bases de l'algorithmique distribuée,
• faire comprendre les problèmes qui se posent lors de la conception d'un système réparti robuste et donner des solutions à ces problèmes,
• aborder les notions de preuve d'algorithme réparti et d'analyse de complexité,
• sensibiliser les étudiants à l'aspect lié à la tolérance aux défaillances, et présenter la technique de réplication, suivie du consensus.

• Notions de base en : réseaux, systèmes, algorithmique classique et algorithmique de graphes

L’auto-stabilisation est une technique versatile pour surmonter toute défaillance transitoire dans un système. Le focus de ce module est sur les systèmes répartis tels que l’Internet, les réseaux d’agents mobiles ou de capteurs, et leurs applications telles que l’Internet des objets, le Cloud, Bitcoin, etc. Les défaillances et l'évolution dynamique sont la norme dans des tels systèmes et deviennent plus en plus probables du fait du passage à la grande échelle. Cela concerne par exemple les changements de la topologie de communication, les corruptions de la mémoire volatile de leurs composants, etc. De telles défaillances peuvent mettre le système dans un état arbitraire, à tout moment de l’exécution. Mais, dès que les défaillances et l'évolution dynamique cessent, un algorithme auto-stabilisant ramène le système dans un fonctionnement correct, sans réinitialisation et sans intervention extérieure.

Dans ce module, après avoir introduit les bases de l'algorithmique répartie, nous étudions comment la technique d’auto-stabilisation est utilisée pour rendre robustes les systèmes répartis actuels.

• Notions de base en : réseaux, systèmes, algorithmique classique et algorithmique de graphes

La nature a développé des algorithmes répartis (sans contrôle centralisé), efficaces et peu gourmands en ressources et en énergie. Les réseaux traditionnels s'en sont parfois inspirés. Ce module est consacré à l'étude d'algorithmes liés, d'une façon ou d'une autre, à des phénomènes naturels. Ils reposent sur des modèles répartis se basant sur des processeurs très limités en ressources et en capacités de calcul et de communication.

Par exemple, dans le modèle des protocoles de populations, des agents fixes ou mobiles, anonymes et indistinguables, avec des mémoires limitées, interagissent par paires de manière imprévisible et asynchrone.

Un autre exemple est celui des systèmes répartis micro-biologiques, comme les cultures de bactéries et de virus. Il s'agit d'autres systèmes très limités, dans lesquels sont développés des algorithmes pour effectuer des calculs (circuits micro-biologiques) ou réguler des médicaments auto-administrés.

Un des objectifs du module sera de comprendre comment des problèmes purement informatiques (calcul, synchronisation, coordination, communication) peuvent être résolus dans ce type de modèles avec des ressources limitées.

• Notions de base en : réseaux, systèmes, algorithmique classique et algorithmique de graphes

L'objectif de ce cours est de fournir une base théorique adéquate pour la conception et l'analyse des algorithmes parallèles dans de différents modèles de calcul parallèle. Le cours commence par l'introduction d'une machine parallèle idéale (PRAM), puis se concentre sur la conception de divers algorithmes optimaux et l'analyse de leur complexité dans ce contexte. Ensuite, des architectures parallèles à mémoire distribuée utilisant de différents réseaux de communication sont introduites. Enfin, la parallélisation de nombreux algorithmes fondamentaux bien connus est traitée.

• Algorithmique et programmation de base
• Connaissance de base de l'architecture des ordinateurs

La notion d’agents mobiles a été proposée dans les années '90 pour faciliter plusieurs tâches fondamentales dans un réseau, telles que la tolérance aux pannes, la gestion du réseau et l’acquisition de données. Les agents mobiles servent de modèle naturel pour des systèmes logiciels à mobilité intrinsèque (code mobile, propagation de logiciel malveillant, robots d’indexation) et, à ce titre, ils ont trouvé des applications comme paradigme de conception de logiciel. Une deuxième perspective est fournie par la possibilité de modéliser des robots qui se déplacent dans un domaine continu, avec des applications typiques dans les domaines de l’intelligence artificielle, de la robotique, ou du contrôle.

La communauté des algorithmes distribués a montré un fort intérêt tant pour les agents logiciels que pour les robots, avec le développement d'une riche littérature et d'un domaine de recherche actif. Après présentation des deux grandes catégories de modèles de robots (Look-Compute-Move) et d'agents logiciels, nous aborderons les problèmes algorithmiques fondamentaux du domaine, tels que la formation de motifs par des groupes de robots, le rassemblement, le rendez-vous, l'exploration, et la détection de nœuds dangereux dans un réseau. Le thème unifiant du cours est la conception des algorithmes qui permettront aux agents de collaborer entre eux et de résoudre ces problèmes, malgré leurs capacités de communication limitées, leur connaissance limitée du domaine dans lequel ils évoluent, et, dans certains cas, l'asynchronisme du système ou la présence de fautes.

• notions de base en: réseaux, systèmes, algorithmique classique et algorithmique de graphes;
• des notions de base en algorithmique répartie et parallèle seront un plus

L'objectif du cours est d'approfondir les connaissances en conception et programmation dans un langage orienté objet en étudiant les structures de données abstraites et le langage C++.

Le cours portera entre autres sur les points suivants:

• Dérivation multiple, généricité (patrons de classes), gestion mémoire.
• Bibliothèque standard de classes génériques (stl) : listes, files, tables de hachages, vecteurs, etc.

La partie pratique, sous forme de projet encadré, permet aux étudiants de concevoir un logiciel où sont mises à contribution les connaissances acquises dans les autres modules : théorie des graphes, intelligence artificielle et infographie principalement.

• Algorithmique et programmation de base en licence

Ce module vise a fournir une maîtrise avancée du langage C++ et des techniques de développement logiciel associées. L'accent sera mis sur la version moderne du langage (C++14/17) et ses implications sur les techniques de génie logiciel usuelles: méta-programmation, programmation fonctionnelle, modèle objet avancé.

• Algorithmique et programmation de base en C++ ou C

• Algorithmique et programmation de base en C/C++
• Connaissance de base de l'architecture des ordinateurs
• [M1 QDCS] Algorithmique parallèle (recommandé)

Ce cours a pour but d’acquérir des compétences pour développer des programmes parallèles rapides capables d’exploiter les architectures parallèles pour résoudre des problèmes réels à grande échelle. Nous nous intéressons d’abord à la programmation parallèle sur une machine multi-cœurs en utilisant la bibliothèque OpenMP et discutons de la parallélisation des boucles, de l'ordonnancement et des techniques de parallélisation basée sur les tâches, ainsi que des opérations atomiques, des conditions de concurrence et du partage erroné. Nous étudions ensuite la parallélisation au sein d’un seul cœur en utilisant des techniques de vectorisation et un parallélisme au niveau des instructions. Enfin, nous discutons des problèmes de performances liés à la hiérarchie de la mémoire et des moyens de l'améliorer.

• Connaissances de bases en algorithmique, en programmation (C/C++) et en architecture des ordinateurs
• [M1 QDCS] Algorithmique parallèle (recommandé)
• [M1 ANO] Programmation MPI (recommandé)

• Connaissances de bases en algorithmique, en programmation (C/C++) et en architecture des ordinateurs.
• [M2 QDCS] Calcul haute performance
• [M1 ANO] Programmation MPI (recommandé)
• [M1 QDCS] Algorithmique parallèle (recommandé)

Ce module s'intéresse à la gestion efficace des ressources des systèmes parallèles (calcul, mémoire, réseau, etc.) utilisées pour le calcul scientifique et le traitement de données massives à travers des systèmes d'exécution et d'autres composants logiciels.

Les thèmes suivants seront étudiés pendant le cours : les notions de base d'ordonnancement, la gestion de ressources de calcul partagées, l'équilibrage de charge dynamique et le "work-stealing", l'ordonnancement dans les systèmes de calcul hétérogènes, l'ordonnancement des graphes de tâches et les workflows scientifiques, la gestion de ressources dans les systèmes de Big Data.

• Notions de base en systèmes, en programmation parallèle et en algorithmique classique
• Notions de base en architecture et algorithmique parallèle seront un plus
• [M2 QDCS] Calcul haute performance
• [M1 QDCS] Algorithmique parallèle (recommandé)
• [M1 ANO] Programmation MPI (recommandé)

L'objectif de ce cours est de comprendre le fonctionnement des algorithmes quantiques, d'analyser leurs forces et leurs limites. Dans un premier temps, nous introduirons les concepts derrière le calcul quantique et nous étudierons le modèle de calcul standard: les familles de circuits et le modèle du co-processeur quantique. Nous discuterons de la structure des algorithmes quantiques et du modèle de programmation qui en découle. Nous étudierons ensuite quelques algorithmes classiques : Grover, Shor, etc. Dans un dernier temps, nous ouvrirons la discussion sur les applications présenties à moyen terme pour le calcul quantique, en particulier dans le cadre du machine learning.

• Connaissances de bases en algorithmique/programmation et en architecture des ordinateurs

Modèles de calculs quantiques avancés, tels que le langage graphique dit ZX calcul: formalisme; universalité; complétude; vérification; optimisation; codes surfaciques.

Codes correcteurs d’erreurs quantiques:

• Rappels sur les codes correcteurs d'erreurs classiques, code de Hamming, notion de matrices génératrices et de parité. Codes LDPC et décodage itératif.
• Rappel sur les opérateurs de Pauli, notion de codes quantiques stabilisateurs, codes CSS, exemple des codes de Shor et de Steane, codes MDS quantiques.
• Interprétation homologique des codes CSS, exemple du code torique de Kitaev, codes LDPC quantiques, décodage, construction de Tillich-Zémor.
• On terminera le cours sur les résultats récents sur la construction de familles de codes LDPC quantiques de distance minimale quasi-linéaire.

• [M1 QDCS] Initiation à l’algorithmique et à la programmation quantique
• [M1 MPRI] Fondaments de l'information quantique

Dans ce cours nous introduisons les outils d'algèbre linéaire nécessaires à la compréhension de l'état de l'art de la simulation de processeurs quantiques via un système HPC classique. Nous rappelons d'abord les enjeux du calcul quantique par rapport au calcul haute performance ainsi que les principaux concepts du modèle de calcul basé sur des circuits quantiques. Nous étudierons ensuite deux méthodes de simulation complémentaires, toutes deux basées sur la manipulation de tenseurs. Nous étendrons ces techniques à la simulation approchée de calcul quantique avec quantification de l'erreur commise. Enfin nous présenterons une approche à base d'algèbre linéaire de la représentation du groupe de Clifford ainsi que son application à la simulation.

• Notions de calcul matriciel
• Connaissances de bases en programmation Python

• postulats, non-clonage, non-distinguabilité ;
• matrices de densité et opérations quantiques ;
• notations de Dirac et de Coecke ;
• protocoles de superdense-coding, téléportation, QRAC, partage de clé BB84... ;
• non-signalling vs localité, inégalités de Bell, aléas certifié ;
• théorèmes de décomposition des états et opérateurs ;
• théorème fondamental des codes correcteurs ;
• simulation quantique hamiltonienne ;
• simulation quantique digitale par marches quantiques et automates cellulaires quantiques.

• Tous les rappels nécessaires seront faits. Assurez-vous toutefois d'aimer l'algèbre linéaire: vecteurs, matrices, produit interne, norme.

Ce module se propose de décrire les avancées les plus récentes en matière de calculs distribué, parallèle et quantique. Son contenu précis est donc à même d'évoluer au cours du temps.

Le module est particulièrement recommandé aux étudiants qui veulent se tenir au courant des évolutions algorithmiques actuelles et envisagent de poursuivre leurs études avec un doctorat.

• Notions de base en réseaux, systèmes, algorithmique classique et algorithmique de graphes
• Notions de base en algorithmique repartie et parallèle sera un plus

Présenter les problèmes d’optimisation où les décisions sont prises en présence d’incertitude. Il s’agit de problèmes où l’ensemble ou un sous-ensemble des paramètres est représenté par des variables aléatoires qui suivent des lois de probabilités connues à l’avance. Le cours est basé sur les fondements théoriques de l’optimisation stochastique, les différentes modélisations de l’aléa et du risque et les méthodes de résolution associées. L’interaction sera optimisation stochastique et jeux stochastiques sera aussi abordée. Des exemples d’applications issues de problèmes industriels seront donnés pour illustrer les différentes parties du cours. Ce module couvrira les thèmes suivants :

• Modélisation de problèmes d’optimisation avec incertitude.
• Problèmes stochastiques linéaires à deux niveaux avec recours.
• Problèmes stochastiques linéaires multi-niveaux avec recours.
• Méthodes d’échantillonnage et approximations.
• Introduction aux problèmes stochastiques avec des contraintes en probabilité.
• Interactions entre théorie des jeux stochastiques et optimisation stochastique.

• Programmation linéaire
• Bases en probabilités

Une grande variété de problèmes d’optimisation sont de nature discrète et peuvent être formulés et résolus à l'aide de méthodes d’optimisation combinatoire, tels que la planification du personnel de bord, la planification de la production d'électricité, les télécommunications, les problèmes de coupes, pour ne citer que quelques exemples. Les problèmes d'optimisation combinatoire sont ceux dans lesquels des techniques mathématiques sont appliquées pour trouver des solutions optimales au sein d'un ensemble fini de solutions possibles. L'ensemble de solutions possibles est généralement défini par un ensemble de contraintes, et cet ensemble est trop volumineux pour une recherche exhaustive. Les problèmes du sac-à-dos et du voyageur du commerce sont des exemples bien connus de l’optimisation combinatoire. A la fin de ce module, l’étudiant doit être capable de :

• analyser et modéliser un problème d'optimisation combinatoire sous la forme d'un programme linéaire ou d'un graphe,
• appliquer différentes méthodes de relaxation pour la résolution de problèmes d’optimisation combinatoire afin d’obtenir des bornes de bonne qualité,
• formaliser et résoudre un problème d'optimisation dynamique,
• maitriser les bases de la complexité et des problèmes de réduction,
• utiliser les méthodes de résolution exacte de séparation et d’évaluation connues sous le nom de Branch & Bound,
• maitriser les algorithmes de plans coupants.

• Programmation linéaire
• Bases en algorithmique et algèbre matriciel

Au cours des 10 dernières années, un grand nombre de liens importants entre l’optimisation, la théorie des jeux et la théorie de l’apprentissage ont été découverts. Ce cours explorera ces liens, discutera de quelques sujets fondamentaux dans chaque domaine et de la façon dont les idées de chaque domaine peuvent éclairer les autres. Ce module couvrira les thèmes suivants :

• Minimisation des regrets, exemple d’algorithmes de bandit.
• Jeux à somme nulle. Équilibres de Nash, le théorème minimax.
• Equilibres de Nash dans les jeux bimatriciels.
• Jeux avec plusieurs joueurs.
• Equilibre de Nash et conditions d’optimalité.
• Sous-modularité avec des liens avec la théorie des jeux et l'apprentissage.

• [M1 QDCS] Modélisation et optimisation des systèmes discrets
• Aucun prérequis nécessaire en apprentissage ou en théorie des jeux