Compléments de cours en analyse, algèbre, probabilités et géométrie.

Compléments de cours en complexité, algorithmique, programmation et théorie des graphes

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.

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.

Géométrie différentielle discrète. Extension de la courbure à des objets discrets comme les surfaces polyédrales ou les graphes. Le flot sous contrainte permet la déformation d'images 3D tout en préservant des motifs géométriques. Programme: Théorie des surfaces discrètes, topologie, courbure de Gauss, théorème de Gauss Bonnet. Opérateurs et calcul différentiel discret. Courbure moyenne discrète sur les surfaces triangulées. Paramétrage par ligne de courbure, quadrangulation et application à l'architecture. Isopérimétrie discrète. On étend le problème isopérimétrique classique (quels ensembles ont une aire maximale parmi ceux de périmètre fixé) à des graphes. On présente les théorèmes Brunn-Minkowski et Loomis-Whitney, l’entropie, les théorèmes de Harper et l’analyse booléenne sur l’hypercube, le théorème de Cheeger reliant le trou spectral aux propriétés d’expansion d’un graphe et on donne des constructions algébriques et probabilistes de familles de graphes expanseurs.

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.

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.

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.