Cours de mathématiques discrètes

Leçon 1 • Notation et symboles mathématiques

Couvre les symboles standards, les quantificateurs et la notation de sommation utilisés en mathématiques discrètes. Développe la lecture et l'écriture d'énoncés mathématiques formels.

Leçon 2 • Introduction à la logique et aux propositions

Définit les propositions, les connecteurs logiques et les valeurs de vérité. Relie le raisonnement logique à la rédaction de démonstrations et à l'analyse d'algorithmes.

Leçon 3 • Ensembles et opérations ensemblistes

Introduit les ensembles, l'appartenance et les opérations telles que l'union, l'intersection et le complémentaire. Fournit le langage fondamental pour tous les sujets suivants.

Leçon 1 • Nombres premiers et factorisation

Examine la distribution des nombres premiers, les tests de primalité et la factorisation unique. Soutient la compréhension du chiffrement RSA et des algorithmes de théorie des nombres.

Leçon 2 • Arithmétique modulaire

Introduit les congruences, les opérations modulaires et les classes de résidus. Fournit le fondement arithmétique pour les applications cryptographiques et de hachage.

Leçon 3 • Divisibilité et propriétés des entiers

Définit la divisibilité, les facteurs et les multiples pour les entiers. Établit les propriétés utilisées dans le calcul du PGCD et l'arithmétique modulaire.

Leçon 1 • Formes normales et simplification

Couvre les formes normales conjonctive et disjonctive ainsi que la simplification booléenne. Relie la simplification logique à la conception de circuits et au raisonnement automatisé.

Leçon 2 • Logique propositionnelle et inférence

Formalise la logique propositionnelle avec des règles d'inférence et des lois logiques. Développe la capacité à dériver des conclusions à partir de prémisses données de manière systématique.

Leçon 3 • Logique dans les algorithmes et les programmes

Applique le raisonnement logique à la correction des programmes, aux invariants de boucle et aux spécifications. Fait le pont entre la logique formelle et la vérification de logiciels ainsi que l'analyse d'algorithmes.

Leçon 1 • Définitions et structures récursives

Définit des suites, des ensembles et des fonctions de manière récursive. Relie les définitions récursives à des structures de données telles que les listes et les arbres.

Leçon 2 • Récurrence forte et bon ordre

Étend la récurrence à sa forme forte et la relie au principe de bon ordre. Permet les démonstrations nécessitant plusieurs cas antérieurs simultanément.

Leçon 3 • Résolution de relations de récurrence

Couvre les méthodes pour trouver des solutions explicites aux récurrences linéaires. Soutient l'analyse de la complexité des algorithmes par la résolution de récurrences.

Leçon 1 • Principe des tiroirs et applications

Énonce le principe des tiroirs et l'applique aux démonstrations d'existence. Montre comment les arguments de dénombrement garantissent des propriétés structurelles dans les systèmes discrets.

Leçon 2 • Introduction aux fonctions génératrices

Introduit les fonctions génératrices ordinaires comme outil de dénombrement. Relie l'algèbre polynomiale à l'énumération combinatoire et à la résolution de récurrences.

Leçon 3 • Permutations et combinaisons

Distingue les sélections ordonnées et non ordonnées et dérive les formules factorielles. Les applique à des problèmes d'ordonnancement, d'arrangement et de sélection.

Leçon 4 • Théorème binomial et identités

Démontre le théorème binomial et dérive des identités combinatoires. Relie le développement algébrique aux arguments de dénombrement et au triangle de Pascal.

Leçon 1 • Relations d'équivalence et partitions

Relie les relations d'équivalence aux partitions d'un ensemble en classes disjointes. Applique les classes d'équivalence à l'arithmétique modulaire et aux systèmes de types.

Leçon 2 • Fonctions : types et propriétés

Classe les fonctions comme injectives, surjectives et bijectives et analyse leurs réciproques. Soutient la compréhension de l'encodage des données, du hachage et des applications cryptographiques.

Leçon 3 • Relations binaires et propriétés

Définit les relations binaires et leurs propriétés : réflexivité, symétrie et transitivité. Fournit le cadre pour les relations d'équivalence et d'ordre.

Leçon 1 • Arbres et arbres couvrants

Définit les arbres, les arbres enracinés et les arbres couvrants et démontre leurs propriétés clés. Relie les structures arborescentes aux données hiérarchiques et aux algorithmes d'arbre couvrant de poids minimum.

Leçon 2 • Propriétés des graphes et graphes particuliers

Examine les séquences de degrés, la connexité et les familles de graphes particuliers. Relie les propriétés structurelles à la conception d'algorithmes et à l'analyse de réseaux.

Leçon 3 • Chemins eulériens et hamiltoniens

Énonce les conditions d'existence des chemins et circuits eulériens et hamiltoniens. Applique ces concepts aux problèmes de routage, d'ordonnancement et de conception de réseaux.

Leçon 4 • Définitions et représentations des graphes

Définit les sommets, les arêtes, les graphes orientés et non orientés, et les représentations courantes. Établit le vocabulaire et les structures de données pour tous les algorithmes de graphes.

Leçon 1 • Flot de réseau et théorème du flot maximum-coupe minimum

Introduit les réseaux de flot, les flots réalisables et le théorème du flot maximum-coupe minimum. Relie le flot de réseau au transport, au routage et à l'allocation de ressources.

Leçon 2 • Couplage et graphes bipartis

Couvre les couplages parfaits, le théorème de Hall et les algorithmes de chemins augmentants. Applique la théorie du couplage à l'optimisation d'affectations et d'ordonnancements.

Leçon 3 • Algorithmes de plus court chemin

Couvre les algorithmes de Dijkstra et de Bellman-Ford pour les plus courts chemins dans des graphes pondérés. Les applique aux protocoles de routage et aux systèmes de navigation géographique.

Leçon 4 • Graphes planaires et isomorphisme de graphes

Démontre la formule d'Euler pour les graphes planaires et introduit les tests d'isomorphisme. Relie la planarité à la conception de circuits et aux requêtes sur les bases de données de graphes.