Les mathématiques discrètes sont l'étude des structures mathématiques qui sont discrètes plutôt que continues. Contrairement aux nombres réels qui varient « en douceur », les mathématiques discrètes traitent d'objets tels que les nombres entiers, les graphes, les mots et les énoncés de logique. Ces objets ont des valeurs distinctes et séparées : on parle d'ensembles dénombrables ou finis plutôt que d'ensembles non dénombrables comme l'ensemble des nombres réels. Les mathématiques discrètes contrastent donc avec les domaines des « mathématiques continues » (calcul différentiel et intégral, analyse réelle, etc.), bien qu'il n'existe pas de frontière rigide et universelle entre les deux.

Le terme mathématiques finies est parfois employé pour désigner les parties des mathématiques discrètes qui se concentrent sur les ensembles finis, notamment lorsqu'il s'agit d'applications pratiques en informatique ou en recherche opérationnelle. Les objets étudiés peuvent toutefois être infinis mais dénombrables (par exemple l'ensemble des mots finis sur un alphabet, l'ensemble des nombres rationnels), contrairement aux ensembles non dénombrables comme les réels.

La recherche en mathématiques discrètes s'est fortement développée à la seconde moitié du XXe siècle, en grande partie grâce à l'avènement des ordinateurs numériques, qui manipulent des informations sous forme binaire et opèrent par étapes discrètes. Les concepts et notations issus des mathématiques discrètes sont essentiels en informatique : algorithmes, structures de données, langages formels, cryptographie, preuve automatique de théorèmes, théorie de la complexité, et plus généralement pour la modélisation et la résolution de problèmes combinatoires. Réciproquement, les implémentations informatiques permettent d'expérimenter et d'appliquer ces idées à grande échelle.

Bien que l'objet d'étude soit discret, les méthodes analytiques issues des mathématiques « continues » sont fréquemment utilisées : fonctions génératrices et analyse asymptotique, méthodes probabilistes, transformées, algèbre linéaire et théorie spectrale, ou encore techniques issues de l'analyse complexe pour étudier des séries formelles. Ces outils donnent des estimations, des approximations et des preuves d'existence utiles dans de nombreux problèmes discrets.

Principales branches et thèmes

  • Combinatoire : dénombrement, permutations, combinaisons, principes d'inclusion-exclusion, bijections, structures énumératives et fonctions génératrices.
  • Théorie des graphes : étude des graphes (arbres, graphes planaires, bipartis, orientés), chemins, cycles, colorations, couplages, flots et algorithmes associés (DFS, BFS, Dijkstra, Bellman–Ford, algorithme de Ford–Fulkerson, etc.).
  • Théorie des nombres (aspect discret) : propriétés des entiers, congruences, primalité, factorisation, arithmétique modulaire — domaines cruciaux en cryptographie.
  • Logique mathématique et théorie de la calculabilité : logique propositionnelle et du premier ordre, automates, langages formels, machines de Turing, décidabilité et complexité de la preuve.
  • Théorie de la complexité : classes de complexité (P, NP, co-NP, NP-complet), réduction, problèmes difficiles et approximation.
  • Théorie des codes et cryptographie : codes correcteurs d'erreurs, codes linéaires, corps finis, algorithmes de chiffrement à clef publique et privée.
  • Probabilités discrètes : processus aléatoires discrets, méthodes probabilistes en combinatoire, modèles de graphes aléatoires.

Méthodes et outils courants

  • Fonctions génératrices et analyse asymptotique pour obtenir des formules exactes ou approximatives de dénombrement.
  • Méthode probabiliste pour prouver l'existence d'objets combinatoires ou estimer des paramètres.
  • Arguments bijectifs et récursifs (relations de récurrence) pour construire et compter des objets.
  • Algorithmes efficaces et structures de données (tas, tables de hachage, arbres équilibrés, files, piles) pour résoudre des problèmes discrets en pratique.
  • Outils algébriques (corps finis, matrices, transformées) et analytiques (spectre d'un graphe, inégalités) pour étudier propriétés structurelles.

Applications en informatique et dans le monde réel

  • Conception d'algorithmes : tri, recherche, routage dans les réseaux, calcul de plus courts chemins, flots maximums, appariement.
  • Cryptographie : sécurité des communications (RSA, ECC) reposant sur des problèmes arithmétiques discrets difficiles comme la factorisation ou le logarithme discret.
  • Théorie des langages et compilation : analyse syntaxique, automates finis et grammars pour la conception de compilateurs et d'analyseurs.
  • Théorie des codes et télécommunications : codes correcteurs d'erreurs pour la transmission fiable (codes de Hamming, Reed–Solomon).
  • Recherche opérationnelle : optimisation discrète, programmation linéaire entière, planification, ordonnancement et logistique.
  • Science des données et réseaux : modélisation de graphes sociaux, fouille de graphes, algorithmes pour données massives (big data).

Exemples simples

  • Combien de mots binaires de longueur n ? Réponse : 2^n (combinatoire de base).
  • Nombre de permutations de n objets : n!.
  • Problème des ponts de Königsberg (Euler) : fondement de la théorie des graphes ; montre l'importance des degrés de sommets pour l'existence d'un parcours eulérien.
  • Plus court chemin dans un graphe pondéré à arêtes positives : algorithme de Dijkstra.

Historique et quelques pionniers

  • Leonhard Euler : considéré comme l'un des fondateurs de la théorie des graphes (ponts de Königsberg).
  • George Boole : fonde l'algèbre booléenne, essentielle à la logique et à l'informatique.
  • Alan Turing et Alonzo Church : contributions majeures à la théorie de la calculabilité et des machines abstraites.
  • Paul Erdős : contributions vastes en combinatoire et théorie des graphes, méthodes probabilistes.

Remarques finales

Les mathématiques discrètes forment un domaine riche, à la fois théorique et appliqué. Elles fournissent le langage et les outils pour modéliser des systèmes numériques, résoudre des problèmes combinatoires complexes et analyser la performance des algorithmes. Même si certaines techniques proviennent des mathématiques continues, l'essentiel de la discipline concerne des objets aux valeurs séparées, bien adaptés aux technologies numériques contemporaines.