Optimisation discrète : Les résultats min-max en optimisation combinatoire fournissent des énoncés mathématiques élégants, sont souvent corrélés à l’existence d’algorithmes efficaces et illustrent particulièrement bien la puissance de la dualité en optimisation. Le cours s’appuiera sur des exemples tirés du monde industriel. Plan du cours : graphes bipartis. Chaînes et antichaînes dans les posets. Graphes triangulés. Graphes parfaits. Fonction theta de Lovász. Optimisation continue : aspects théoriques et algorithmiques de l'optimisation, essentiellement convexe, en dimension finie. Programme : Programmation linéaire, algorithme du simplexe, matrices totalement unimodulaires. Fonctions convexes. Programmation semi-définie positive, programmation convexe. Conditions de Karush-Kuhn-Tucker. Dualité faible et forte, Lemme de Farkas. Optimisation 1-D, méthodes de descente. Recherche de solutions parcimonieuses. Méthode LASSO.

Langue de l'enseignement

ANGLAIS / ENGLISH

Algorithmes probabilistes. L’objectif de ce cours est d’étudier les algorithmes probabilistes, qui utilisent l’aléa lors de leurs exécutions. Au programme : algorithmes Las Vegas et Monte Carlo, notions sur les classes de complexité randomisées, bornes inférieures : principe MinMax de Yao, problèmes probabilistes utiles en algorithmique : collecteur de coupons, paradoxe des anniversaires, analyse du tri rapide, de la sélection rapide, problème des mariages stables, structures de données probabilistes : hachage, skip lists, treaps, comptage, algorithmes sur les graphes. Le cours de combinatoire abordera les notions suivantes objets classiques : permutations, arbres, partitions, parking, suites classiques : factorielles, Catalan, Schroder, méthodes classiques : bijections, action de groupes, récurrence, series génératrices. Le cours sera principalement composé d'exemples de toutes difficultés.

Langue de l'enseignement

ANGLAIS / ENGLISH

Langue de l'enseignement

ANGLAIS / ENGLISH

Apprentissage automatique. OBJECTIFS: comprendre les algorithmes principaux de l’intelligence artificielle : apprentissage automatique et profond. Introduction à l’optimisation et les algorithmes d’approximation stochastiques pour l’apprentissage. Construction de méthodes de prédiction sur des données non structurées comme du texte. PROGRAMME: Introduction à l’apprentissage statistique : risque théorique et empirique, équilibre Biais-Variance, sur-apprentissage ; méthodes d’agrégation : forêts aléatoires; méthodes ensemblistes (bagging et boosting) ; méthodes à noyau et algorithmes de machine à vecteurs de support ; Convexification, techniques de régularisation et pénalisation (Lasso, Ridge, elastic net) ; algorithmes d’apprentissage profond : rétroaction, réseaux de convolution et récurrent, régularisation par dropout ; Prédiction avec des données de texte non structurées :  sac de mots, word2vec; Introduction à l’apprentissage par renforcement.

Langue de l'enseignement

ANGLAIS / ENGLISH

L'objectif du cours est de présenter la théorie des grands graphes denses, dans ses aspects analytique, probabiliste et combinatoire. Plan indicatif : introduction et rappels sur les graphes finis ; définition d'un graphon, graphon comme générateur de graphes aléatoires denses ; propriétés de l'espace des graphons, distance de coupe ; convergence de grands graphes vers un graphon ; graphes échantillonnés ; inégalités de concentration et convergence ; application : inégalités combinatoires classiques ; application : épidémie sur un graphon, graphons biaisés par la taille ; application : fonction de degré, modèle exponentiel.

Langue de l'enseignement

ANGLAIS / ENGLISH

Opérades en combinatoire : informellement, une opérade est un espace d’opérations ayant une sortie et plusieurs entrées qui peuvent être composées. On présente quelques objets de combinatoire algébrique : classes et algèbres combinatoires. On introduit les opérades (non-symétriques) et on étudie des outils permettant d’établir des présentations par générateurs et des relations d’opérades, la dualité de Koszul et des généralisations : opérades colorées, opérades, et pros. On explique aussi comment la théorie des opérades offre un outil pour obtenir des résultats énumératifs. Combinatoire algebrique : étude des fonctions symétriques classiques et théorie des representations, fonctions symétriques non commutatives (NCSF), définition des algèbres de Hopf, l’algèbre duale de NCSF, fonctions quasi-symétriques, généralisations modernes de ces algèbres et utilisation de ces propriétés algébriques (matrices de transition, expressions dans diverses bases, morphismes d’algèbres de Hopf) pour résoudre des questions combinatoires classiques.

Langue de l'enseignement

ANGLAIS / ENGLISH