Mathématiques discrètes

📚 Résumé du contenu

Un cours d'introduction aux mathématiques discrètes destiné aux étudiants en mathématiques et en informatique. Il couvre des sujets fondamentaux tels que la logique, les ensembles, les techniques de preuve, les algorithmes, la théorie des nombres, le dénombrement, la théorie des graphes et les automates. Ce cours met l'accent sur le raisonnement mathématique et les compétences en résolution de problèmes nécessaires à une étude avancée en informatique.

Maîtrisez la logique et les structures qui forment la base de l'informatique.

Auteur : Richard Johnsonbaugh

Remerciements : Revueurs incluant Venkata Dinavahi, Matthew Elsey, Christophe Giraud-Carrier, Yevgeniy Kovchegov, Filix Maisch, Tyler McMillen, Christopher Storm, Donald Vestal, et Guanghua Zhao. Soutien de l'équipe Pearson : Deirdre Lynch, Jeff Weidenaar, Lauren Morse, et d'autres.

🎯 Objectifs d'apprentissage

1. Effectuer des opérations sur les ensembles, notamment les différences et les compléments, et vérifier des identités ensemblistes à l’aide de diagrammes de Venn et du Théorème 1.1.22.
2. Construire et évaluer des tables de vérité pour des propositions impliquant la négation, la disjonction et les énoncés conditionnels.
3. Appliquer les règles d’inférence et le raisonnement déductif pour déterminer la validité des arguments logiques.
4. Définir et appliquer les composantes d’un système mathématique, notamment les axiomes, les définitions et les théorèmes.
5. Construire des preuves directes, des preuves par contradiction et des preuves par cas pour des propositions algébriques et ensemblistes.
6. Utiliser le Principe d’Induction Mathématique et l’Induction Forte pour prouver des identités, des propriétés de divisibilité et la correction d’algorithmes.
7. Définir et classer les fonctions (injectives, surjectives, bijectives) et effectuer des opérations telles que la composition et l’inversion.
8. Appliquer la notation des suites, la concaténation des chaînes et les règles récursives pour modéliser des ensembles de données discrets.
9. Analyser les relations binaires selon des propriétés comme la réflexivité, la symétrie et la transitivité à l’aide de diagrammes orientés et de représentations matricielles.
10. Définir un algorithme et vérifier ses sept propriétés fondamentales (Entrée, Sortie, Précision, Déterminisme, Finitude, Correctitude, Généralité).

🔹 Leçon 1 : Fondements de la logique et de la théorie des ensembles

Aperçu : Cette leçon établit les briques fondamentales des mathématiques discrètes, en se concentrant sur la manipulation rigoureuse des ensembles et les structures formelles de la logique. Les étudiants passeront des opérations ensemblistes et des identités à la construction d’arguments logiques, à l’évaluation des propositions conditionnelles et à l’analyse des quantificateurs imbriqués. Ces concepts fournissent le cadre essentiel pour la conception d’algorithmes, la théorie des bases de données et la vérification formelle en informatique et en ingénierie.

Objectifs d’apprentissage :

• Effectuer des opérations sur les ensembles, notamment les différences et les compléments, et vérifier des identités ensemblistes à l’aide de diagrammes de Venn et du Théorème 1.1.22.
• Construire et évaluer des tables de vérité pour des propositions impliquant la négation, la disjonction et les énoncés conditionnels.
• Appliquer les règles d’inférence et le raisonnement déductif pour déterminer la validité des arguments logiques.

🔹 Leçon 2 : Techniques de preuve mathématiques

Aperçu : Cette leçon aborde les méthodologies formelles utilisées pour établir la validité des énoncés mathématiques et la rigueur logique requise en informatique et en mathématiques. Les étudiants passeront des systèmes mathématiques fondamentaux et des preuves directes aux techniques sophistiquées telles que les preuves par résolution, l’induction mathématique (y compris l’induction forte) et l’application des invariants de boucle dans la vérification algorithmique.

Objectifs d’apprentissage :

• Définir et appliquer les composantes d’un système mathématique, notamment les axiomes, les définitions et les théorèmes.
• Construire des preuves directes, des preuves par contradiction et des preuves par cas pour des propositions algébriques et ensemblistes.
• Utiliser le Principe d’Induction Mathématique et l’Induction Forte pour prouver des identités, des propriétés de divisibilité et la correction d’algorithmes.

🔹 Leçon 3 : Fonctions, suites et relations

Aperçu : Cette leçon traite des structures mathématiques fondamentales utilisées pour modéliser des données et des processus en informatique. Elle progresse de la définition des fonctions et de leurs différents types (injectives, surjectives, bijectives) à l’étude des suites, des chaînes et des propriétés formelles des relations binaires. Les étudiants exploreront des applications pratiques telles que les fonctions de hachage, les chiffres de contrôle ISBN, la planification de tâches via les ordres partiels, et la représentation des relations à l’aide de matrices et de bases de données.

Objectifs d’apprentissage :

• Définir et classifier les fonctions (injectives, surjectives, bijectives) et effectuer des opérations telles que la composition et l’inversion.
• Appliquer la notation des suites, la concaténation des chaînes et les règles récursives pour modéliser des ensembles de données discrets.
• Analyser les relations binaires selon des propriétés telles que la réflexivité, la symétrie et la transitivité à l’aide de diagrammes orientés et de représentations matricielles.

🔹 Leçon 4 : Analyse des algorithmes et complexité

Aperçu : Cette leçon traite de la définition fondamentale et des propriétés des algorithmes, de leur mise en œuvre dans les recherches et les tri (spécifiquement la recherche de texte et le tri par insertion), et des cadres mathématiques rigoureux utilisés pour analyser leur efficacité. Les étudiants exploreront les notations asymptotiques, les taux de croissance des fonctions, et les mécanismes de résolution récursive de problèmes, y compris des stratégies diviser-pour-régner comme le pavage de plateau et les séquences basées sur Fibonacci.

Objectifs d’apprentissage :

• Définir un algorithme et vérifier ses sept propriétés fondamentales (Entrée, Sortie, Précision, Déterminisme, Finitude, Correctitude, Généralité).
• Appliquer les notations Big-O, Omega et Theta pour exprimer la complexité temporelle et spatiale des algorithmes.
• Analyser les scénarios au meilleur cas, au pire cas et en moyenne à l’aide de techniques telles que la division par deux itérée et l’ordre polynomial.

🔹 Leçon 5 : Introduction à la théorie des nombres et à la cryptographie

Aperçu : Cette leçon explore les principes fondamentaux de la théorie des nombres, allant des propriétés de base des diviseurs et des nombres premiers aux algorithmes complexes qui sous-tendent les communications sécurisées modernes. Les étudiants maîtriseront les mécanismes mathématiques des plus grands communs diviseurs (PGCD), des conversions de base et de l’exponentiation modulaire afin de comprendre et d’implémenter le système cryptographique à clé publique RSA.

Objectifs d’apprentissage :

• Définir et appliquer les concepts de divisibilité, de primalité et du Théorème Fondamental de l’Arithmétique.
• Effectuer des conversions efficaces entre les systèmes numériques décimal, binaire et hexadécimal.
• Exécuter l’Algorithme d’Euclide et sa forme étendue pour trouver les PGCD et les combinaisons linéaires (sa + tb).

🔹 Leçon 6 : Méthodes de dénombrement et probabilité discrète

Aperçu : Cette leçon explore les techniques fondamentales pour compter des structures finies et leur application à la probabilité discrète. Les étudiants passeront des principes de base de l’addition et de la multiplication aux concepts avancés tels que les nombres de Catalan, les nombres de Stirling et le Théorème Binomial. La leçon se termine par le Principe des Tiroirs et ses différentes formes, offrant un cadre rigoureux pour prouver l’existence de configurations spécifiques dans les systèmes discrets.

Objectifs d’apprentissage :

• Appliquer les Principes d’Addition, de Multiplication et d’Inclusion-Exclusion pour résoudre des problèmes de dénombrement complexes.
• Différencier et calculer les permutations et les combinaisons, y compris les cas avec objets identiques et répétitions.
• Utiliser des algorithmes génératifs pour les permutations et les combinaisons dans l’ordre lexicographique.

🔹 Leçon 7 : Relations de récurrence

Aperçu : Cette leçon explore la théorie et les applications des relations de récurrence en mathématiques et en informatique. Les étudiants apprendront à résoudre ces relations à l’aide de l’itération et des équations caractéristiques, tant pour les formes homogènes que non homogènes. En outre, la leçon démontre comment les relations de récurrence sont des outils essentiels pour analyser la complexité temporelle des algorithmes récursifs tels que le tri par sélection, la recherche binaire et le tri fusion.

Objectifs d’apprentissage :

• Résoudre les relations de récurrence à l’aide de la méthode d’itération et des équations caractéristiques (pour des racines distinctes et égales).
• Modéliser et résoudre des problèmes mathématiques classiques, notamment la Tour de Hanoï, la Suite de Fibonacci (Ratio d’Or) et les dérangements.
• Analyser la complexité temporelle au pire cas des algorithmes récursifs à l’aide des relations de récurrence.

🔹 Leçon 8 : Théorie des graphes et algorithmes du plus court chemin

Aperçu : Cette leçon explore les principes fondamentaux de la théorie des graphes, allant des définitions de base des graphes simples et pondérés aux solutions algorithmiques complexes pour les chemins les plus courts et l’identification des cycles. Les étudiants examineront des propriétés structurelles telles que la planéité, la connexité et l’isomorphisme tout en appliquant ces concepts à des problèmes classiques comme le problème des ponts de Königsberg, le Problème du Voyageur de Commerce (TSP) et le puzzle Instant Insanity.

Objectifs d’apprentissage :

• Définir et distinguer les types de graphes, notamment les graphes simples, pondérés, complets, bipartis et les n-cubes.
• Analyser la connectivité des graphes pour identifier les cycles d’Euler, les cycles hamiltoniens et déterminer les plus courts chemins à l’aide de l’algorithme de Dijkstra.
• Appliquer les représentations matricielles (adjacence et incidence) et les invariants graphiques pour vérifier les isomorphismes et la planéité.

🔹 Leçon 9 : Arbres et algorithmes de recherche

Aperçu : Cette leçon traite des propriétés fondamentales, des caractérisations et des applications des arbres en informatique et en mathématiques. Les étudiants exploreront les arbres enracinés et binaires, les algorithmes d’arbres couvrants (BFS/DFS), les techniques d’optimisation telles que l’algorithme de Prim pour les arbres couvrants minimaux, ainsi que des cadres décisionnels incluant le backtracking, les tri par tournoi et les arbres de jeu avec la procédure minimax.

Objectifs d’apprentissage :

• Définir et identifier les arbres enracinés, leurs niveaux, leur hauteur et leurs structures hiérarchiques dans les systèmes du monde réel.
• Caractériser les arbres selon la connectivité, l’acyclicité et les rapports entre arêtes et sommets.
• Mettre en œuvre et tracer les algorithmes pour les arbres couvrants (BFS, DFS), les arbres couvrants minimaux (Prim) et la construction des arbres binaires de recherche.

🔹 Leçon 10 : Modèles de réseaux et optimisation des flux

Aperçu : Cette leçon traite de la modélisation mathématique des réseaux de transport, en se concentrant sur la manière dont les ressources (flux) circulent à travers un graphe orienté depuis une source vers un puits. Elle détaille les règles de conservation du flux, les étapes algorithmiques pour maximiser le débit, la relation entre les coupes de réseau et la capacité de flux, et l’application de ces principes pour résoudre des problèmes d’appariement dans les graphes bipartis.

Objectifs d’apprentissage :

• Définir et vérifier les propriétés d’un réseau de transport et d’une affectation de flux valide.
• Exécuter l’Algorithme du Flux Maximal (Algorithme 10.2.4) pour trouver le débit optimal.
• Appliquer le Théorème du Flux Maximal - Coupe Minimale pour prouver l’optimalité du flux à l’aide de partitions de réseau.

🔹 Leçon 11 : Algèbre booléenne et circuits logiques

Aperçu : Cette leçon explore les fondements mathématiques de la logique numérique, en se concentrant sur la manière dont l’algèbre booléenne fournit un langage formel pour concevoir et simplifier les circuits combinatoires. Les étudiants apprendront à traduire entre les portes logiques, les circuits à commutation et les expressions booléennes, aboutissant à l’application de ces outils pour synthétiser des fonctions complexes et construire des composants arithmétiques essentiels tels que les additionneurs et la logique en complément à deux.

Objectifs d’apprentissage :

• Concevoir et analyser des circuits combinatoires en utilisant des portes logiques standard (ET, OU, NON) et des configurations de commutation.
• Appliquer les lois de l’algèbre booléenne et le Théorème Dual pour prouver l’équivalence des circuits et simplifier les expressions.
• Synthétiser des fonctions booléennes à partir de tables de vérité en Forme Normale Disjonctive (FND) et Forme Normale Conjonctive (FNC).

🔹 Leçon 12 : Automates, grammaires et langages formels

Aperçu : Cette leçon explore les fondements mathématiques du calcul, en commençant par les circuits séquentiels et les machines à états finis qui modélisent la mémoire interne via des délais d’un temps unitaire. Elle couvre la définition formelle et la classification des grammaires à structure de phrase (Types 1, 2 et 3), l’application de la Forme Normale de Backus (BNF), et l’utilisation spécialisée des grammaires de Lindenmayer pour la génération de fractales. Enfin, elle établit la relation critique entre les automates à états finis déterministes et non déterministes et les langages formels qu’ils acceptent.

Objectifs d’apprentissage :

• Analyser et concevoir des machines à états finis (MEF) et des automates (AFD/AFN) à l’aide de diagrammes de transition et de fonctions d’état.
• Classer les grammaires dans la hiérarchie de Chomsky et dériver des chaînes à l’aide de règles de production et de la notation BNF.
• Modéliser des structures auto-similaires telles que la neige de von Koch à l’aide de grammaires de Lindenmayer et de règles de remplacement simultanées.