Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : MAT1153  Gr. 01
Titre : Structures discrètes
Session : Automne 2018  Horaire et local
Professeur : Yapi, Daniel
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 ndahdaniel.yapi@uqo.ca

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
 04 sept. 2018 
2   

Logique propositionnelle (suite) :

  • Arguments valides
  • Règles d'inférence (modus ponens, modus tollens, syllogismes, etc.)

Travail dirigé 1 : Logique propositionnelle (Les 13 et 14 septembre 2018).

 11 sept. 2018 
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 (Les 20 et 21 septembre 2018).

 18 sept. 2018 
4   

Preuves en mathématiques :

  • Applications de tautologies logiques
  • Principe d'induction

Travail dirigé 3 : Preuves en mathématiques (Les 27 et 28 septembre 2018).

 25 sept. 2018 
5   

Ensembles :

  • Opérations sur les ensembles : union, intersection, différence
  • Produit cartésien
  • Famille des sous-ensembles

Travail dirigé 4 : Ensembles(Les 4 et 5 octobre 2018).

 02 oct. 2018 
6   

Semaine d'études

 09 oct. 2018 
7   

Examen de mi-session

 16 oct. 2018 
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 (Les 25 et 26 octobre 2018).

 23 oct. 2018 
9   

Relations :

  • Relations binaires
  • Compositions de relations
  • Relations d'ordre
  • Relations d'équivalence

Travail dirigé 6 : Relations (Les 1 et 2 novembre 2018).

 30 oct. 2018 
10   

Fonctions :

  • Injection, surjection, bijection
  • Composition des fonctions, fonction inverse
  • Permutation et cycle

Travail dirigé 7 : Fonctions (Les 8 et 9 novembre 2018).

 06 nov. 2018 
11   

Graphes :

  • Éléments de la théorie
  • Graphe simple
  • Chaîne et cycle
  • Graphe eulérien, cycle hamiltonien
  • Arbre

Travail dirigé 8 : Graphes (Les 15 et 16 novembre 2018).

 13 nov. 2018 
12   

Éléments d'algèbre :

  • Semi-groupes, monoïdes groupes
  • Sous-structures
  • Exemples
  • Groupe quotient, théorème de Lagrange
 20 nov. 2018 
13   

Éléments d'algèbre (suite) :

  • Homomorphismes de groupe
  • Isomorphismes
  • Noyau

Travail dirigé 9 : Éléments d'algèbre (Les 29 et 30 novembre 2018).

 27 nov. 2018 
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 (Les 6 et 7 décembre 2018).

 04 déc. 2018 
15   

Examen final

 11 déc. 2018 
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