Le cours présente des concepts fondamentaux de la théorie de l’ordre et des graphes. Ces concepts sont à la base de méthodes d’organisation, de reconstruction, d’extraction et de traitement de données. Ces méthodes sont utilisées en Economie, Sciences Sociales, Informatique, Recherche Opérationnelle ou Biologie.
1. Une introduction à l’ordre (les théorèmes de Erdös-Szekeres, de Dilworth, Sperner, Szpilrajn, Tarski).
2. Les objets de base. Pré-ordres, ordres, partitions, arbres ; relations d’incidence. Comparaison et proximité (métrique, métrique sur les arbres, arbres phylogéniques). Treillis complets ; fermeture, pré-fermeture, engendrement, partie libre, famille de Moore, fermeture algebrique, matroïdes, antimatroïdes.
3. Fonctions boolénnes (le ou, le et, le non, le implique, par les tableaux; le treillis des propositions, complétude).
4. Correspondance de Galois et treillis de Galois; exemples : complété de MacNeille et treillis des sections initiales. Relations Ferrers. Ordres et graphes d’intervalles. Introduction l’analyse formelle des concepts, analyse de questionnaires. Dépendances, implications, échelle de Guttman, base canonique d’un treillis de Galois (Guigues - Duquenne).
5. Représentation d’un ensemble ordonné dans un produit de chaînes, dimension au sens de Dushnik-Miller. Extensions linéaires et sections initiales. Dualité entre ensembles ordonnés et treillis des sections initiales.
6. Graphes; chemins, connexité, cycles eulériens et hamiltoniens, nombre chromatique. Graphes et matrices.
7. Mots sur un alphabet fini; mots bien parenthésés, énumération de motifs, codes,
comparaison de séquences. Brève introduction aux automates finis et aux langages reconnaissables.
8. Ordres et choix : agrégation des préférences (des choix individuels au choix collectif), paradoxe de Condorcet, le théorème de McGarvey, la règle de Borda, le théor`eme de Arrow. Analyse de scrutins.
9. Eléments de géométrie combinatoire. Equivalences et carrés latins. Plans d’expériences.
