Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : MAT1153  Gr. 01
Titre : Structures discrètes
Session : Automne 2017  Horaire et local
Professeur : El Guemhioui, Karim
1. Description du cours paraissant à l'annuaire :

Objectifs

Au terme de cette activité, l'étudiant sera en mesure : de décrire et d'utiliser les notions et outils mathématiques de base indispensables en informatique; d'identifier et de mettre en application des méthodes de raisonnement rigoureux.

Contenu

Logique propositionnelle et éléments du calcul des prédicats, leur application aux modes de raisonnement. Ensembles. Éléments d'analyse combinatoire. Notion de relation, ordres et équivalences, applications. Fonction, leurs propriétés et rôle en informatique. Graphes, propriétés, applications et représentations informatisées. Éléments d'algèbre et applications au codage, codes corrigeants, codes de Hamming. Automates finis et expressions régulières, applications en informatique. Ce cours comporte des séances obligatoires de travaux dirigés (TD) de deux heures par semaine.
2. Objectifs spécifiques du cours :
  1. Développer l'aptitude de formulation rigoureuse de pensée.
  2. Introduire les méthodes de raisonnement rigoureux.
  3. Familiariser l'étudiant avec les notions et outils mathématiques de base indispensables en informatique.
  4. Montrer les liens entre les mathématiques et l'informatique à l'aide d'exemples.

Ce cours couvre 1 des 12 qualités requises des diplômés telles que définies dans les normes d'agrément des programmes de génie au Canada (http://www.engineerscanada.ca/fr/ressources-en-matiere-dagrement):

a. Qualité 1: Connaissance en génie

3. Stratégies pédagogiques :
Les formules pédagogiques suivantes seront utilisées :
  1. Cours magistraux.
  2. Séances de travaux dirigés.
  3. Examen de mi-session.
  4. Examen final.
  5. Devoirs.
4. Heures de disponibilité ou modalités pour rendez-vous :

Heures de consultation : Sur rendez-vous (local B-0123).

5. Plan détaillé du cours sur 15 semaines :
Semaine Thèmes Dates
1    Logique propositionnelle :
  • Propositions logiques atomiques et composées
  • Connecteurs logiques, leur syntaxe et sémantique
  • Tautologies et contradictions
  • Équivalences propositionnelles
05 sept. 2017 
2    Logique propositionnelle (suite) :
  • Arguments valides
  • Règles d'inférence (modus ponens, modus tollens, syllogismes, etc.)

Travail dirigé 1 : Logique propositionnelle (Le 15 septembre 2017).

12 sept. 2017 
3    Logique des prédicats :
  • Limitations de la logique propositionnelle
  • Prédicats
  • Quantificateurs logiques
  • Traduction de phrases en expressions logiques - variables liées

Travail dirigé 2 : Logique des prédicats (Le 22 septembre 2017).

19 sept. 2017 
4    Preuves en mathématiques :
  • Applications de tautologies logiques
  • Principe d'induction

Travail dirigé 3 : Preuves en mathématiques (Le 29 septembre 2017).

26 sept. 2017 
5    Ensembles :
  • Opérations sur les ensembles : union, intersection, différence
  • Produit cartésien
  • Famille des sous-ensembles

Travail dirigé 4 : Ensembles (Le 6 octobre 2017).

03 oct. 2017 
6    Semaine d'études 10 oct. 2017 
7    Examen de mi-session 17 oct. 2017 
8    Éléments d'analyse combinatoire :
  • Principes de la somme et du produit
  • Permutations, arrangements, combinaisons
  • Applications des notions combinatoires à la solution des problèmes pratiques

Travail dirigé 5 : Éléments d'analyse combinatoire (Le 27 octobre 2017).

24 oct. 2017 
9    Relations :
  • Relations binaires
  • Compositions de relations
  • Relations d'ordre
  • Relations d'équivalence

Travail dirigé 6 : Relations (Le 3 novembre 2017).

31 oct. 2017 
10    Fonctions :
  • Injection, surjection, bijection
  • Composition des fonctions, fonction inverse
  • Permutation et cycle

Travail dirigé 7 : Fonctions (Le 10 novembre 2017).

07 nov. 2017 
11    Graphes :
  • Éléments de la théorie
  • Graphe simple
  • Chaîne et cycle
  • Graphe eulérien, cycle hamiltonien
  • Arbre

Travail dirigé 8 : Graphes (Le 17 novembre 2017).

14 nov. 2017 
12    Éléments d'algèbre :
  • Semi-groupes, monoïdes groupes
  • Sous-structures
  • Exemples
  • Groupe quotient, théorème de Lagrange
21 nov. 2017 
13    Éléments d'algèbre (suite) :
  • Homomorphismes de groupe
  • Isomorphismes
  • Noyau

Travail dirigé 9 : Éléments d'algèbre (Le 1er décembre 2017).

28 nov. 2017 
14    Introduction à la théorie des automates :
  • Définition et exemples d'automates finis
  • Expressions régulières et leur lien avec les automates

Travail dirigé 10 : Automates (Le 8 décembre 2017).

05 déc. 2017 
15    Examen final 12 déc. 2017 
6. Évaluation du cours :
  • Examen de mi-session : 40 %
  • Examen final : 40 %
  • Devoirs : 20 %
7. Politiques départementales et institutionnelles :
8. Principales références :
  1. Kenneth H. Rosen, Mathématiques discrètes, édition révisée, Chenelière McGraw-Hill, 2002.
  2. Judith L. Gersting, Mathematical Structures for Computer Science, Freeman & Co., 6e édition, 2006.
  3. Rod Haggarty, Mathématiques discrètes appliquées à l’informatique, Pearson Education, 2005.
9. Page Web du cours :
https://moodle.uqo.ca