|
École de technologie supérieure
|
Responsable(s) de cours :
|
Anouk Bergeron-Brlek, Xavier Provençal, Xavier Provençal, Xavier Provençal
|
PLAN DE COURS
Été 2019
MAT210 : Logique et mathématiques discrètes (4 crédits)
Préalables
| Programme(s) : 7365,7610 | | | | | | | | | | | Profils(s) : Tous profils | | | | | | | | | | | | | MAT145 | | | | | | | | | | | |
|
Unités d'agrément
Total d'unités d'agrément : 64,8
|
Qualités de l'ingénieur
|
|
Qualité visée dans ce cours |
|
|
|
Qualité visée dans un autre cours |
|
|
|
Indicateur enseigné |
|
|
Indicateur évalué |
|
|
Indicateur enseigné et évalué |
Descriptif du cours
Acquérir les notions fondamentales de la logique mathématique. S’initier aux concepts des mathématiques discrètes.
Introduction à la logique : calcul propositionnel, calcul des prédicats, méthodes de preuve et algèbre de Boole. Théorie des ensembles. Comportement asymptotique des fonctions et compexité temporelle des algorithmes. Théorie des nombres : nombres premiers, algorithme d'Euclide, arithmétique modulaire et applications. Preuves par récurrence et relations de récurrence. Principes de base du dénombrement. Théorie des graphes : terminologie, représentations, chemins et circuits.
Séances de travaux pratiques portant sur la logique et les applications des mathématiques discrètes.
Note sur le préalable Le cours MAT145 est concomitant pour le programme de baccalauréat en informatique distribuée, c'est-à-dire qu'il peut être suivi avant ou en même temps que le MAT210.
Objectifs du cours
Apprendre et maîtriser les outils de mathématiques discrètes de base liés aux problèmes de programmation et de structures informatiques. À l’occasion, appliquer ces notions par la réalisation de programmes informatiques.
Stratégies pédagogiques
Trois heures et demie de cours magistral par semaine. De nombreux exemples et exercices seront faits en classe pour permettre aux étudiants de bien assimiler la théorie présentée.
Utilisation d’appareils électroniques
S.O.
Horaire
| Groupe | Jour | Heure | Activité |
| 01 | Mardi | 13:30 - 17:00 | Activité de cours |
| Jeudi | 13:30 - 16:30 | Travaux pratiques |
| 02 | Mercredi | 09:00 - 12:30 | Activité de cours |
| Vendredi | 09:00 - 12:00 | Travaux pratiques |
Coordonnées de l’enseignant
Cours
(Les sections indiquées font référence à l’ouvrage de K. H. Rosen – 7e édition.)
|
COURS
|
MATIÈRE
|
SECTIONS À LIRE
|
HEURES
|
|
|
1 - 2
|
Logique. Équivalences propositionnelles. Prédicats et quantificateurs. Règles d'inférence. Méthodes de preuve.
|
1.1 à 1.8
|
6
|
|
|
3
|
Ensemble : opérations sur les ensembles.
Fonctions : injections, surjections, bijections. Relations de récurrence. Suites et sommations.
|
2.1 à 2.4
|
3
|
|
|
4
|
Comportement asymptotique des fonctions. Algorithmes. Complexité des algorithmes.
|
3.1 à 3.3
|
3
|
|
|
5 - 6
|
Nombres entiers et division. Arithmétique modulaire. Entiers et algorithmes. Cryptographie RSA.
|
4.1 à 4.6
|
6
|
|
|
7
|
Examen intra portant sur les cours 1 à 6
|
|
3
|
|
|
8
|
Principe de l’induction. Définitions récursives. Algorithmes récursifs.
|
5.1 à 5.4
|
3
|
|
|
9
|
Notions de base du dénombrement. Principe des tiroirs. Permutations et combinaisons.
|
6.1 à 6.3
|
3
|
|
|
10
|
Relations de récurrence. Solutions des relations de récurrence linéaires. Algorithmes de fractionnement (diviser pour régner).
|
8.1 à 8.3
|
3
|
|
|
11 - 12
|
Graphes : types de graphes, terminologie, représentation et utilisation. Matrices d’adjacence et d’incidence d’un graphe. Connectivité. Chemins eulériens et hamiltoniens d’un graphe, circuit et applications. Problème du plus court chemin d’un graphe
|
10.1 à 10.6
|
6
|
|
|
13
|
Algèbre booléenne. Fonctions booléennes et leurs représentations. Portes logiques. Minimisation de circuit.
|
12.1 à 12.4
|
3
|
|
|
Total
|
39
|
Laboratoires et travaux pratiques
Trois heures de travail pratique par semaine seront consacrées à travailler les exercices hebdomadaires, à demander des éclaircissements sur les notions vues dans le cours, à compléter le cours magistral par certaines démonstrations ou certains exemples.
Utilisation d'outils d'ingénierie
Afin de permettre une participation active en classe, il est obligatoire que chaque étudiant possède une calculatrice TI-Nspire CAS CX. Ces calculatrices sont en vente à la COOP. La calculatrice symbolique sera utilisée tout au long de la session pour illustrer des concepts mathématiques, pour effectuer des calculs, des manipulations algébriques et même pour implémenter certains algorithmes. L’utilisation efficace de cet outil sera vérifiée lors des examens. Pour de l’aide sur l’utilisation de cette calculatrice symbolique, visitez le site http://seg-apps.etsmtl.ca/nspire/.
Voici des objectifs spécifiques d’apprentissage concernant l’utilisation de la calculatrice TI-Nspire CAS CX:
- Connaître la syntaxe des expressions logiques : and, or, not.
- Connaître le fonctionnement de l’éditeur de programmes et de fonctions.
- Savoir implémenter une fonction définie par récurrence.
- Savoir implémenter une fonction récursive définie par une relation de type diviser pour régner.
- Savoir implémenter une suite définie par récurrence, en tracer le graphique en obtenir un terme de rang donné ou une table de valeurs.
- Savoir effectuer différentes opérations matricielles (par exemple : obtenir la 5e puissance d’une matrice M associée à un graphe afin d’établir le nombre de chemins de longueur 5 entre deux sommets donnés).
Évaluation
| |
Gr. 01 |
Gr.02 |
| Examen intra : 30 % |
2019-06-11 |
2019-06-12 |
| Devoirs et ou mini-tests : 40 % |
Dates à communiquer en classe |
| Examen final : 30 % |
Semaines des examens finaux |
Double seuil :
Une note moyenne pondérée de 50 % est exigée pour l’ensemble des évaluations à caractère individuel. Ce seuil est une condition nécessaire à la réussite du cours mais ne la garantit pas.
À propos de l'examen final :
- L'examen final est d'une durée de 3 heures.
- La documentation permise à l'examen final est :
- un résumé personnel de 2 feuilles 8 ½ po X 11 po (recto verso);
- une calculatrice TI Nspire.
Double seuil
Note minimale : 50
Dates des examens intra
| Groupe(s) | Date |
| 1 | 11 juin 2019 |
| 2 | 12 juin 2019 |
Date de l'examen final
Votre examen final aura lieu pendant la période des examens finaux, veuillez consulter l'horaire à l'adresse suivante : http://etsmtl.ca/Etudiants-actuels/Baccalaureat/Examens-finaux
Politique de retard des travaux
Tout travail (devoir pratique, rapport de laboratoire, rapport de projet, etc.) remis en retard sans motif valable, c’est-à-dire autre que ceux mentionnés dans le Règlement des études (1er cycle, article 7.2.7 b / cycles supérieurs, article 6.5.4 b) se verra attribuer la note zéro, à moins que d’autres dispositions ne soient communiquées par écrit par l’enseignant dans les consignes de chaque travail à remettre ou dans le plan de cours pour l’ensemble des travaux.
Absence à un examen
Dans les cinq (5) jours ouvrables suivants, la tenue de son examen, l’étudiant devra justifier son absence d’un examen durant le trimestre auprès de la coordonnatrice – Affaires départementales qui en référera au directeur du département ou du SEG. Pour un examen final, l’étudiant devra justifier son absence auprès du Bureau du registraire. Dans tous les cas, l’étudiant doit effectuer sa demande en complétant le formulaire prévu à cet effet qui se trouve dans son portail Mon ÉTS/Formulaires. Toute absence non justifiée par un motif majeur (maladie certifiée par un billet de médecin, décès d’un parent immédiat, Activité compétitive d’un étudiant appartenant à un club scientifique ou un club sportif d’élite de l’ÉTS ou au programme « Alliance sport étude » ou autre) à un examen entraînera l’attribution de la note zéro (0).
Documentation obligatoire
Notes de cours MAT210 - Logique et mathématiques discrètes vendu a la Coop ETS
Ouvrages de références
ROSEN, Kenneth H. Discrete Mathematics and Its Applications, 7e édition, McGraw-Hill.
Documentation additionnelle :
- ABELSON, H., J. SUSSMAN. Structure et interprétation des programmes informatiques, InterEditions.
- BRASSARD G., P. BRATLEY. Algorithmique conception et analyse, Masson, Presse de l’Université de Montréal.
- COMTET, Louis. Advanced Combinatorics, D. Reidl Publishing Company.
- GRAHAM, KNUTH, PATASHNIK. Concrete Mathematics, A Fondation for Computer Science, Addison-Wesley.
- ROSEN, Kenneth H. Handbook of Discrete and Combinatorial Mathematics, CRC Press.
- STANLEY, Richard P. Enumerative Combinatorics, Wadsworth & Brooks.
- STANAT, MC ALLISTER, Discrete mathematics in computer science, Prentice Hall.