Mathématiques discrètes FUN3111
Enseignant:
Email:
Durée totale du cours: 30 H
Semestre : 2
Nombre de crédits : 2
| Modules
spécialisés |
Modules de
base |
Sciences et techniques de
l’ingénierie |
Préparation à la carrière professionnelle |
| X |
| Nombre d’heures | Activités hors classe | |||
| 22.5 | 18 | |||
| cours | TD | TP | ||
| 16.5 | 13.5 | |||
Sommaire:
La mathématique discrète traite de divers sujets tels que la logique mathématique, la théorie des ensembles, la théorie des graphes, la théorie des nombres, la combinatoire, la théorie des codes, la théorie de l’information, la théorie des probabilités discrètes et l’algorithmique.
Ces concepts et outils mathématiques trouvent des applications dans divers domaines tels que l’informatique, la cryptographie, les réseaux, la théorie des jeux, l’optimisation, la bioinformatique, les sciences sociales et bien d’autres.
| Code | FUN3201 | Mathématiques discrètes |
Objectifs :
Le cours est une introduction aux notions fondamentales des mathématiques discrètes, l’un des domaines les plus dynamiques des mathématiques modernes. Ces notions sont aujourd’hui de plus en plus utilisées dans le développement, l’analyse et la compréhension de modèles mathématiques dans tous les domaines de l’ingénierie. Le cours est une introduction aux différents sujets qui portent le nom de mathématiques discrètes. Ils vont de la théorie des graphes à la théorie élémentaire des nombres et à l’arithmétique modulaire, à l’algèbre abstraite et à la combinatoire énumérative.
Sujets couverts :
THÉORIE ÉLÉMENTAIRE DES NOMBRES ET ARITHMÉTIQUE MODULAIRE :
Notions de base de la théorie des ensembles. Les nombres naturels et le principe d’induction. Entiers. Divisibilité et nombres premiers. Fonction d’Euler. Congruences. Entiers modulo m. Théorème d’Euler. Petit théorème de Fermat. Éléments de groupe, anneaux et champs. Champs finis. Théorème des restes chinois. Test de primalité de Wilson.
COMBINAIRE ÉNUMÉRATIVE :
Cardinalité d’un ensemble. Principes de base du comptage. Nombres binomiaux, formule de Stiefel et autres identités sur les nombres binomiaux. Permutations et sélections d’un ensemble. Théorème binomial. Séries formelles de puissance. Fractions partielles. Fonctions génératrices. Récursions linéaires homogènes. Nombres de Fibonacci et de Lucas. Forme fermée des nombres de Fibonacci. Nombres de Stirling de seconde espèce. Partitions d’un nombre naturel. Diagrammes de Ferrer. Le problème de la Tour de Hanoï. Principe d’inclusion et d’exclusion. Formules de Sylvester et Da Silva. Dérangements.
GRAPHIQUES :
Définitions de base. Planéité des graphiques. La formule d’Euler. Graphiques bipartis. graphes eulériens. graphes hamiltoniens. Des arbres. Arbres binaires. Enjamber les arbres. Colorations vertex. Numéro chromatique. Colorations de bord. Indice chromatique. Théorème de K\ »{o}nig. Appariements dans les graphes bipartis. Théorème de Hall. Matrice d’adjacence, matrice d’incidence par rapport à une orientation, matrice laplacienne. Théorème de Poincaré. Spectre d’un graphe.
Méthodes d’enseignement et d’apprentissage
¨Enseignement frontal (magistral) avec des exemples à résoudre en commun.
¨Exercices théoriques et études de cas (présentation et discussion).
Connaissances et compétences pré-requises
Les étudiants doivent avoir des connaissances de base en analyse mathématique et en algèbre linéaire.
Références bibliographiques
- Biggs , Discrete Mathematics , Éditeur : Clarendon Press, Oxford, Anno edizione : 1985
- Graham, D. Knuth, O. Patashnik , Concrete Mathematics: A Foundation for Computer Science , Editore: Addison-Wesley, Anno edizione: 1989
FS Roberts , Applied Combinatorics , Editeur : Prentice-Hall, Anno edizione : 1984
Modalité d’évaluation
40% Contrôle continu (TP noté, Test, Assiduité, Devoir surveillé, travaux non présentiel, …)
60% Examen semestriel
Le but de l’examen est de vérifier si chaque étudiant possède les compétences suivantes : capacité d’appliquer des résultats théoriques pour résoudre des exercices, connaissance des définitions, résultats sur les sujets du cours, et preuves des principaux théorèmes mathématiques présentés dans le cours. L’évaluation finale consiste en un examen oral portant sur les thèmes présentés au cours, dont une partie est consacrée à la résolution d’exercices.
Résultats d’apprentissage :
Les cours et les séances d’exercices permettront aux étudiants de se familiariser avec les thèmes du cours et avec quelques applications des thèmes à la résolution de problèmes pratiques.
Plus en détail, les étudiants apprendront à :
• utiliser des règles formelles pour les calculs sur les symboles, indépendamment de la signification des symboles ;
• résoudre des équations sur les entiers ou sur les entiers modulo m ;
• calculer le nombre d’éléments d’ensembles définis par une propriété ;
• analyser des graphiques.
L’étudiant sera en mesure de justifier de l’efficacité des procédures mathématiques utilisées pour résoudre les problèmes présentés dans le cours et d’utiliser correctement le langage mathématique lors de l’argumentation.