Mathématiques Discrètes
Transféré par
ScribdTranslationsMathématiques Discrètes
Transféré par
ScribdTranslationsMCA NSAKCET (A) 2023-2025
PCC101 Mathématiques discrètes
Instructions 4 périodes par semaine
Durée de l'examen universitaire 3 Heures
Examen universitaire 60 points
Saisonnière 40 points
Crédits 4
Objectifs du cours :
[Link] une terminologie et une notation mathématiquement correctes.
2. Construisez des preuves directes et indirectes correctes.
3. Utilisez la division en cas dans une preuve.
4. Utilisez des contre-exemples.
[Link] un raisonnement logique pour résoudre une variété de problèmes
Résultats du cours :
À la fin du cours, les étudiants seront capables de :
1. Exprimer une phrase logique donnée en termes de prédicats, de quantificateurs et de connecteurs logiques
2. Dériver la solution d'un problème donné en utilisant la logique déductive et prouver la solution basée sur
inférence illogique
3. Classifiez la structure algébrique pour un problème mathématique donné,
4. Évaluer les fonctions booléennes et simplifier les expressions en utilisant les propriétés de l'algèbre booléenne
5. Développez le problème donné en tant que réseaux de graphes et résolvez-le avec des techniques de théorie des graphes.
UNITÉ -I
Ensembles, Relation et Fonction : Opérations et Lois des Ensembles, Produits Cartésiens, Binaire
Relation, Relation d'ordre partiel, Relation d'équivalence, Image d'un ensemble, Somme et
Produit de fonctions, Fonctions bijectives, Fonction inverse et fonction composée, Taille d'un ensemble
Ensembles finis et infinis, ensembles dénombrables et indénombrables, argument diagonal de Cantor et
Le théorème de l'ensemble des puissances, le théorème de Schroeder-Bernstein.
Principes de l'induction mathématique : Le principe de bien-ordre, définition récursive
L'algorithme de division : Nombres premiers, Le plus grand commun diviseur : Algorithme d'Euclide
Le théorème fondamental de l'arithmétique.
UNITÉ-II
Techniques de comptage de base - inclusion et exclusion, principe des tiroirs, permutation et
combinaison.
UNITÉ-III
Logique propositionnelle : Syntaxe, Sémantique, Validité et Satisfaction, Connecteurs de base
et Tables de Vérité, Équivalence Logique : Les Lois de la Logique, Implication Logique, Règles
de l'inférence, L'utilisation des quantificateurs. Techniques de preuve : Une terminologie, Preuve
Méthodes et stratégies, preuve directe, preuve par contradiction, preuve par contraposition
Preuve de nécessité et de suffisance.
2
MCA NSAKCET (A) 2023-2025
UNITÉ-IV
Structures algébriques et morphisme : Structures algébriques avec une opération binaire,
Sémigroupes, Monoïdes, Groupes, Relation de congruence et Structures quotient, Libre et
Monoïdes cycliques et groupes, groupes de permutations, sous-structures, sous-groupes normaux,
Structures algébriques avec deux opérations binaires, anneaux, domaines intègres et corps.
Algèbre booléenne et anneau booléen, identités de l'algèbre booléenne, dualité
Représentation de la fonction booléenne, forme normale disjointe et conjonctive
UNITÉ–V
Graphes et Arbres : Graphes et leurs propriétés, Degré, Connectivité, Chemin, Cycle, Sous
Graphe, Isomorphisme, Promenades eulériennes et hamiltoniennes, Coloration de graphe, Coloration
cartes et graphes planaires, coloriage des sommets, coloriage des arêtes, coloriage par liste, parfait
Graph, definition properties and Example, rooted trees, trees and sorting, weighted
arbres et codes préfixes, composante bi-connectée et points d'articulation, chemin le plus court
distances.
Lectures suggérées :
Kenneth H. Rosen, Mathématiques discrètes et ses applications, Tata McGraw –Hill
2. Susanna S. Epp, Mathématiques discrètes avec applications, 4e édition,
Wadsworth Publishing Co. Inc
3.C L Liu et D P Mohapatra, Éléments de mathématiques discrètes A Un ordinateur
Approche Orientée, 3e Édition par Tata McGraw – Hill.
4. J.P. Tremblay et R. Manohar, « Structure Mathématique Discrète et son
Application à l'informatique”, édition TMG, Tata McGraw -Hill
5. Norman L. Biggs, Mathématiques discrètes, 2e édition, Oxford University Press.
Série Schaum's Outlines, Seymour Lipschutz, Marc Lipson.
