Curriculum LDD Informatique-Mathématiques

Cours : Mathématiques discrètes

Objectif : L'objectif est de donner aux étudiant.es une culture des mathématiques, surtout discrètes mais pas uniquement, requise pour suivre les cours de L3 et du M1 MPRI. Le cours est composé de deux parties. La première partie (6 séances) se concentre sur la théorie des ensembles ; la seconde partie (8 séances) aborde des notions de combinatoire, structures ordonnées, points fixes, récurrences, monoïdes et probabilités.

Plan détaillé :

  1. Théorie des ensembles (6 séances de cours)
    • Axiomes de ZF, conséquences directes dont existence des entiers naturels
    • Bons ordres, ordinaux, récurrence ordinale, opérations arithmétiques
    • Cardinaux
    • Récurrence bien fondée
    • Axiome du choix et équivalences relativement à ZF
  2. Combinatoire (2 séances de cours)
    • Coefficients binômiaux
    • Comptage d'applications (Twelvefold way)
    • Partition d'un entier
    • Complexe simpliciel, lemme de Sperner
    • Géométrie finie, e.g. théorème de Sylvester-Gallai
    • Lemme de Könnig et applications, e.g. tuiles de Wang
    • Un lemme d'Erdös, théorèmes de Ramsey (fini et infini)
    • Méthode probabiliste
  3. Structures ordonnées et points fixes (2 séances de cours)
    • Notions de base : produits d'ordres, bornes supérieures, etc.
    • Treillis, point fixe de Knaster-Tarski, théorème de (Anne) Davis
    • Points fixes de Kleene, de Bourbaki-Witt, puis variantes
    • Opérateurs de clôture, systèmes de clôtures, lien avec les points fixes.
    • Point fixe de Brouwer
  4. Récurrence structurelle (1 séance de cours)
    • lien avec les points fixes et la récurrence bien fondée ; exemples.
  5. Monoïdes (2 séances)
    • Produit direct, sous-monoïde engendré, morphismes
    • Congruence, monoïde quotient, factorisation
    • Codes, base, plus petite partie génératrice, enveloppe libre
    • Théorème du défaut
  6. Probabilités (2 séances)
    • Tribus, tribus engendrées, boréliennes, tribu produit, hiérarchie des boréliens
    • Mesure de probabilité, extension, produit, inégalité de Bool, continuité
    • Proba conditionnelles, totales, Bayes, double conditionnement, indépendance
    • Application mesurable, variable aléatoire, loi de proba, fonction de répartition, indépendance
    • Espérance, variance, inégalités de Markov et Tchebychev
    • Chaînes de Markov

Références :

  • Théorie des ensembles : Set Theory (Chapitres 1,2,3,5), Thomas Jech, 3rd edition, 2003.
  • Reste du cours : références variées, dont notes de cours