#Mathématiques discrètes de base
Les maths discrètes sont la grammaire de nombreux sujets d’info : logique pour exprimer des conditions, ensembles et relations pour modéliser, graphes pour raisonner sur des réseaux, arithmétique modulaire pour la crypto et les cycles. L’objectif n’est pas d’aligner des symboles, mais de disposer d’un outil rapide pour convaincre, détecter des impossibilités et dimensionner des algorithmes.
#Trois briques pour structurer votre raisonnement
- Logique : manipuler des propositions, combiner (∧, ∨, ¬) et quantifier (∀, ∃). Formuler des pré/post‑conditions et des invariants, c’est déjà faire de la logique.
- Ensembles / relations : décrire des collections et des correspondances. Les bijections et le principe des tiroirs permettent de prouver ou de compter sans calculer.
- Graphes : représenter des dépendances (réseaux, ordonnancement, parcours). Chemins, cycles et arbres couvrants résument de nombreux problèmes réels (routage, câblage, compilation).
Enfin, l’arithmétique modulaire raisonne « à reste près » sur des anneaux Z/nZ : base de la cryptographie, de l’analyse de périodicité et des algorithmes arithmétiques.
#Checklist de révision rapide
- Être capable de reformuler un énoncé en distinguant hypothèses et conclusion (logique).
- Savoir associer une propriété relationnelle à un schéma (réflexive, symétrique, transitive).
- Reconnaître un graphe qui cache un arbre couvrant, une chaîne ou un cycle simple.
- Calculer un inverse modulaire ou appliquer le CRT sur de petits modules sans hésitation.
- Justifier chaque égalité en citant l’identité utilisée (propriétés de ≡, somme des degrés, etc.).
Plan d’entraînement conseillé
- Réviser les définitions (logique, relations, graphes) en rédigeant une mini-fiche A5.
- Résoudre deux exercices par brique : logique (tables de vérité / preuves), graphes (parcours ou MST) et modulaire (inverses / systèmes de congruences).
- Sélectionner une question d’examen passée et en écrire la solution détaillée (sans calculatrice) en moins de 15 minutes.
#Mini‑atelier
- Énoncez puis prouvez par récurrence que la somme des n premiers entiers vaut n(n+1)/2.
- Modélisez un réseau de villes par un graphe et expliquez en une phrase pourquoi un arbre couvrant minimal évite les cycles inutiles.
- Montrez que $2^n$ et $10^n$ ont toujours le même reste modulo 8 pour $n \ge 1$.