Mathématiques discrétes

Contenus

Objectif du Cours

L’objectif de ce cours est de fournir aux étudiants les concepts fondamentaux des mathématiques discrètes qui constituent une base essentielle de l’informatique et du génie informatique, tout en développant leurs capacités de raisonnement logique, de modélisation mathématique, de résolution de problèmes et de démonstration. Les étudiants apprendront notamment à mettre en relation les ensembles, les relations, la combinatoire, la théorie des nombres, la théorie des graphes, les structures algébriques, les algorithmes et la calculabilité avec des problèmes relevant de l’informatique.

Contenu du Cours

Logique propositionnelle et tables de vérité ; prédicats, quantificateurs et méthodes de preuve ; théorie des ensembles et ensembles des parties ; ensembles partiellement ordonnés ; relations, fermetures et relations d’équivalence ; théorie des nombres, arithmétique modulaire et cryptographie ; combinatoire et principes de dénombrement ; principe d’inclusion-exclusion et fonctions génératrices ; relations de récurrence et analyse d’algorithmes ; concepts fondamentaux de la théorie des graphes et isomorphisme ; arbres, parcours et codage de Huffman ; algorithmes de graphes, chemins et arbres couvrants ; structures algébriques pour l’informatique ; automates à états finis et théorie de la calculabilité.

Acquis d'Apprentissage du Cours

À l’issue du cours, les étudiants seront capables de :

1. Analyser des propositions logiques et construire des tables de vérité.
2. Formuler des énoncés mathématiques à l’aide de prédicats et de quantificateurs.
3. Appliquer les principales méthodes de preuve, notamment la preuve directe, la preuve par contradiction, la preuve par contraposée et la récurrence mathématique.
4. Définir et analyser les ensembles, les relations et les relations d’équivalence.
5. Décrire et analyser les ensembles partiellement ordonnés et leurs propriétés fondamentales.
6. Appliquer les concepts de théorie des nombres et d’arithmétique modulaire à des problèmes d’informatique et de cryptographie.
7. Appliquer les techniques fondamentales de dénombrement et le principe d’inclusion-exclusion à des problèmes de combinatoire.
8. Résoudre des relations de récurrence et effectuer une analyse élémentaire de la complexité des algorithmes.
9. Modéliser des problèmes à l’aide de graphes et d’arbres et appliquer les principales techniques de parcours de graphes.
10. Expliquer et appliquer les concepts et algorithmes relatifs aux chemins, aux arbres couvrants et au codage de Huffman.
11. Décrire les principales structures algébriques utilisées en informatique et analyser leurs propriétés.
12. Expliquer les principes fondamentaux des automates à états finis et le concept de calculabilité.
13. Utiliser les concepts de mathématiques discrètes pour modéliser, analyser et résoudre des problèmes de génie informatique.

Méthodes d'Enseignement

* Cours magistraux et séances interactives
* Présentations conceptuelles au tableau et/ou à l’aide de supports numériques
* Résolution de problèmes mathématiques
* Démonstrations et exercices corrigés
* Questions-réponses et discussions en classe
* Exemples issus de l’informatique et du génie informatique
* Exercices pratiques portant sur les algorithmes et les problèmes de graphes
* Travail individuel et devoirs

Ressources

Rosen, Kenneth H., and Kamala Krithivasan. Discrete mathematics and its applications: with combinatorics and graph theory. Tata McGraw-Hill Education, 2012.

Intitulés des Sujets

Système d'évalution

Evalution de la Compétence

Tableau de la Charge de Travail