Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : MAT1153  Gr. 01
Titre : Structures discrètes
Session : Automne 2016  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 programme 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-2024).

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.
 06 sept. 2016 
2    Logique propositionnelle (suite) :
  • Arguments valides
  • Règles d'inférence (modus ponens, modus tollens, syllogismes, etc.)
  • Introduction à la programmation logique.

Travail dirigé 1 : Logique propositionnelle (Le 16 septembre 2016).

13 sept. 2016 
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 23 septembre 2016).

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

Travail dirigé 3 : Preuves en mathématiques (Le 30 septembre 2016).

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

Travail dirigé 4 : Ensembles (Le 7 octobre 2016).

04 oct. 2016 
6    Semaine d'études. 11 oct. 2016 
7    Examen de mi-session. 18 oct. 2016 
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 28 octobre 2016).

25 oct. 2016 
9    Relations :
  • Relations binaires
  • Compositions de relations
  • Relations d'ordre
  • Relations d'équivalence.

Travail dirigé 6 : Relations (Le 4 novembre 2016).

01 nov. 2016 
10    Fonctions :
  • Définitions et exemples
  • Injection, surjection, bijection
  • Composition des fonctions, fonction inverse
  • Permutation et cycle.

Travail dirigé 7 : Fonctions (Le 11 novembre 2016).

08 nov. 2016 
11    Graphes :
  • Éléments de la théorie
  • Graphe simple
  • Chaîne et cycle
  • Graphe eulérien, cycle hamiltonien
  • Représentations informatisées.

Travail dirigé 8 : Graphes (Le 18 novembre 2016).

15 nov. 2016 
12    Éléments d'algèbre :
  • Semi-groupes, monoïdes groupes
  • Sous-structures
  • Homomorphismes, isomorphismes
  • Groupe quotient, théorème de Lagrange
  • Groupes cycliques.

Travail dirigé 9 : Éléments d'algèbre (le 25 novembre 2016).

22 nov. 2016 
13    Théorie de codage :
  • Codage
  • Code parfait, code de Hamming
  • Décodage.
 29 nov. 2016 
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 9 décembre 2016).

06 déc. 2016 
15    Examen final 13 déc. 2016 
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