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