Mathématiques discrètes

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

1. Biggs , Discrete Mathematics , Éditeur : Clarendon Press, Oxford, Anno edizione : 1985
2. 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.