Aller au contenu principal
Valrose.tech

Mathématiques discrètes de base · L1 · Section 6/6

Ressources et cours complet

Progression

Points d’expérience : —XPSérie de jours consécutifs : —· —Progression du module : — / —compris

#Ressources et cours complet

Pourquoi ces liens : donner une base formelle solide aux raisonnements et modèles de l'informatique. Comment s'en servir : lire un module, faire les exercices, puis vérifier les solutions et formaliser vos preuves.

#Cours du dépôt

#Références

  • Rosen, Mathématiques discrètes : la référence pédagogique, avec des exercices progressifs corrigés.
  • Graham, Knuth, Patashnik, Concrete Mathematics : récurrences, sommes et manipulations symboliques.
  • Pages « Logique propositionnelle », « Graphe (mathématiques) » et « Arithmétique modulaire » pour des révisions illustrées en dix minutes.
  • Les TD et annales de votre université : formats et attendus de rédaction y sont les plus fidèles.

#Exercices conseillés

  • Logique : prouver les lois de De Morgan par table de vérité, puis par équivalences ; donner un contre-exemple à ¬(p → q) ≡ p → ¬q.
  • Ensembles : établir |A ∪ B| = |A| + |B| − |A ∩ B| en découpant l'union en trois zones disjointes, puis en déduire |A △ B|.
  • Relations : montrer que « avoir le même reste modulo 3 » est une équivalence, décrire ses classes, puis la fermeture transitive de « < » sur 4.
  • Graphes : refaire Kruskal et Prim sur le même graphe à 5 sommets, vérifier le même poids total, puis justifier l'absence de cycle à chaque ajout.
  • Modulaire : résoudre x ≡ 3 (mod 5) et x ≡ 1 (mod 7). Indication : chercher x = 3 + 5k et ajuster k ; le résultat est x ≡ 8 (mod 35).

#Bonnes pratiques de rédaction

  • Annoncer la méthode avant de calculer : récurrence, contraposition, propriété de coupe, invariant.
  • Justifier chaque égalité par la propriété mobilisée : De Morgan, compatibilité des congruences, lemme des degrés.
  • Vérifier tout résultat de dénombrement sur un petit cas concret où l'on peut tout lister.
  • Conseil : gardez un carnet d'égalités et d'implications usuelles (De Morgan, contraposée, Bézout) et de schémas de preuve réutilisables.