#Mathématiques discrètes de baseCopier le lien

Les maths discrètes sont la grammaire de nombreux sujets d'informatique : logique pour exprimer des conditions, ensembles et relations pour modéliser, graphes pour raisonner sur des réseaux, arithmétique modulaire pour la cryptographie 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.

Prérequis : aucune base de cours avancé ; savoir lire une table, manipuler des entiers et suivre des scripts Python courts suffit. Un premier contact avec les boucles et les dictionnaires Python aide pour la page graphes.

Objectifs d'apprentissage :

• Reformuler un énoncé en séparant hypothèses et conclusion, puis le prouver (table, contre-exemple, récurrence).
• Manipuler ensembles et relations : opérations, types de fonctions, équivalences et ordres.
• Lire un graphe : degrés, parcours (BFS, DFS), arbres couvrants, ordre topologique.
• Calculer modulo n : inverses, petit théorème de Fermat, théorème des restes chinois.
• Rédiger des preuves courtes et vérifiables : induction, contraposition, principe des tiroirs.

#Plan du moduleCopier le lien

1. Logique : syntaxe, tables de vérité, équivalences usuelles, quantificateurs et schémas de preuve.
2. Ensembles et relations : opérations, fonctions, classes d'équivalence, ordres partiels, fermeture transitive.
3. Graphes : représentations, parcours, plus courts chemins, arbres couvrants, tri topologique.
4. Arithmétique modulaire : congruences, Euclide et Bézout, Fermat, restes chinois.
5. Ressources : cours complet du dépôt, références et pistes d'entraînement.

#Quatre briques pour structurer votre raisonnementCopier le lien

• Logique : manipuler des propositions, combiner (∧, ∨, ¬) et quantifier (∀, ∃). Formuler des pré et post-conditions et des invariants de boucle, c'est déjà faire de la logique.
• Ensembles et relations : décrire des collections et des correspondances. Les bijections et le principe des tiroirs permettent de prouver ou de compter sans tout énumérer.
• 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.
• Arithmétique modulaire : raisonner à reste près sur les anneaux Z/nZ, socle de la cryptographie, de l'analyse de périodicité et du calcul machine sur des tailles bornées.

#Checklist de révision rapideCopier le lien

• Ê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 théorème des restes chinois 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.).

#Mini-atelierCopier le lien

1. Énoncez puis prouvez par récurrence que la somme des n premiers entiers vaut .
2. Modélisez un réseau de villes par un graphe pondéré et expliquez en une phrase pourquoi un arbre couvrant minimal évite les cycles inutiles.
3. Montrez que et ont toujours le même reste modulo 8 pour .