UE 4M068 - Combinatoire et Optimisation - année 2016 - retour
cours les mardis de 10h45 à 12h45 et les mercredis de 08h30 à 10h30 de la semaine du 11/01/2016 à la semaine du 28/03/2016
travaux dirigés les mardis de 17h00 à 20h00 et les mercredis de 13h45 à 16h45 de la semaine du 18/01/2016 à la semaine du 04/04/2016
partiel le mercredi 09 mars de 13h45 à 16h45
examen 1ière session le mardi 10 mai de 13h30 à 16h30
examen 2ième session le vendredi 10 juin de 13h30 à 16h30
Optimisation linéaire, semaines des 21 et 28 mars 2016
Programmes linéaires : faisable, infaisable, borné, non borné, solution admissible, solution optimale, optimum - Programmes linéaires équivalents, variables d'écarts - Programme linéaire dual
d'un programme linéaire - Autres formulations du Lemme de Farkas - Théorème de dualité pour la programmation linéaire - Transversals, transversals fractionnaires, couplages, couplages fractionnaires
d'un hypergraphe - Théorème de König - Conditions des écarts complémentaires du primal et du dual - Description polyèdrale de l'ensemble des arbres couvrants d'un graphe simple connexe -
Algorithme du simplexe -
Matroides, semaines des 7 et 14 mars 2016
Axiomatique des indépendants (Hassler Whitney, 1935)
- axiomatique des rangs - matroides vectoriels, graphiques, transversals et de couplage - matroide dual - algorithme glouton - Théorème de Rado-Hall -
Graphes, forêts, arbres et arbres couvrants, semaines des 22 et 29 février 2016
Terminologie relative aux graphes - Forêts et arbres - Nombre d'arbres sur un ensemble donné (Formule de Cayley) - Graphes plans - Graphes planaires - Relation d'Euler pour les graphes plans -
Triangulation du plan ou de la sphère - Non planarité de K5 et K33 - Lemme des croisements - Deux applications du lemme des croisements - Arbres couvrants d'un graphe - Matrice d'adjacence et matrice
laplacienne d'un graphe - Nombre d'arbres couvrants d'un graphe : énoncé du théorème de Kirchhoff - Matrice d'incidence d'un graphe orienté - Formule de Binet-Cauchy - Matrice totalement unimodulaire -
Preuve du théorème de Kirchhoff - Arbre couvrant de valuation minimale - Algorithme glouton -
Treillis des faces d'un polytope, semaines du 25 janvier et des 1, 8 et 15 février 2016
Terminologie relative aux ensembles partiellement ordonnés - Cônes, cônes finiment engendrés, cônes polyèdriques - Théorème de Minkowsky-Weyl pour les cônes - Langage de la géométrie affine -
Convexes, convexes finiment engendrés, convexes polyèdriques, polytopes - Théorème de Minkowsky-Weyl pour les convexes - Lemme de Farkas via un théorème de séparation - Lemme de Farkas via la procédure
de Fourier-Motzkin - Partie linéaire et cône de récession d'un polyèdre non vide - Treillis des faces d'un polyèdre - Etoiles d'un polyèdre en un sommet - Polarité - Produit de deux polytopes - Simplexes et cocubes standards - Polytopes simples et simpliciaux - Polytopes cycliques - f-vecteurs et h-vecteurs - Bonnes orientations acycliques du graphe d'un polytope - Relations de Dehn-Sommerville -
Théorème de la borne supérieure -
Arbres binaires de recherche, semaine du 18 et 25 janvier 2016
Définition des arbres binaires de recherche - chemin de recherche d'une clé, insertion d'une clé, suppression d'une clé - arbre binaire de recherche aléatoire -
profondeur d'un arbre binaire de recherche aléatoire -
dynamisation des arbres binaires de recherche aléatoires - algorithmes de tri - borne inférieure -
Arbres binaires, semaines des 11 et 18 janvier 2016
Définition des arbres binaires - arbre vide, noeuds internes/externes, racine, sous-arbres, sous-arbre gauche,
sous-arbre droit, chemin de recherche d'un sous-arbre - taille, profondeur d'un noeud, hauteur -
nombre d'arbres binaires de taille donnée - nombres de Catalan - génération aléatoire d'un arbre binaire de taille donnée -
rotations dans les arbres binaires - arbres binaires et triangulations des polygones convexes - rotations et flips -
associaèdre ou polytope de Stasheff -
construction de Loday -
Présentation du cours, semaine du 11 janvier 2016