Logo ÉTS
Session
Cours
Responsable(s) Xavier Provençal, Geneviève Savard

Se connecter
 

Sauvegarde réussie
Echec de sauvegarde
Avertissement
École de technologie supérieure

Responsable(s) de cours : Xavier Provençal, Geneviève Savard


PLAN DE COURS

Hiver 2021
MAT210 : Logique et mathématiques discrètes (4 crédits)


Modalités de la session d’hiver 2021


Pour assurer la tenue de la session d’hiver 2021, les modalités suivantes seront appliquées :


La plupart des cours de la session d'hiver seront donnés à distance. Les autres seront donnés en présence si la situation socio-sanitaire le permet. Cette information est disponible sur l’horaire de la session d’hiver diffusé sur le site de l’ÉTS ainsi que sur Cheminot.

L’étudiant inscrit à un cours à distance doit avoir accès à un ordinateur, un micro, une caméra et un accès à internet, idéalement de 10Mb/s ou plus. L’étudiant doit ouvrir sa caméra et/ou son micro lorsque requis, notamment pour des fins d’identification ou d’évaluation.


Les cours à distance pourraient être enregistrés, à la discrétion de l’ÉTS, afin de les rendre disponibles aux étudiants inscrits aux cours.


La notation des cours sera la notation régulière prévue aux règlements des études de l'ÉTS.


Les examens intra se feront normalement à distance. Les examens finaux se feront normalement en présence si la situation socio-sanitaire le permet.


Pour les examens (intra, finaux) qui devaient se faire à distance, leur surveillance se fera à l’aide de la caméra et du micro de l’ordinateur et pourrait être enregistrée. Ceci est nécessaire pour se conformer aux exigences du Bureau canadien d’agrément des programmes de génie (BCAPG) afin d’assurer la validité des évaluations.

Le contexte actuel oblige bien sûr l’ÉTS à suivre de près l’évolution de la pandémie de COVID-19, laquelle pourrait entraîner, avant ou après le début de la session d’hiver 2021, un resserrement des directives et recommandations gouvernementales. Nous vous assurons que l’ÉTS se conformera aux règles en vigueur afin de préserver la santé publique et que, si requis, elle pourrait aller jusqu’à interdire l’accès physique au campus universitaire et ordonner que toutes les activités d’enseignement et d’évaluation soient exclusivement données à distance pour tout ou partie de la session d’hiver 2021.

Des exigences additionnelles pourraient être spécifiées par l’ÉTS ou votre département, suivant les particularités propres à votre programme.

En vous inscrivant ou en demeurant inscrit, vous acceptez les modalités particulières de la session d’hiver 2021.


Nous vous rappelons que vous avez jusqu’au 17 janvier 2021 pour vous désinscrire de vos cours et être remboursé.


Pour les nouveaux étudiants inscrits au programme de baccalauréat uniquement, vous avez jusqu’au 31 janvier 2021 pour vous désinscrire de vos cours et être remboursé.




Préalables
Programme(s) : 7065,7070,7084,7086,7365,7610
             
  Profils(s) : Tous profils  
             
    MAT145    
             
Unités d'agrément
Total d'unités d'agrément : 64,8 100,0 %




Qualités de l'ingénieur

Qn
Qualité visée dans ce cours  
Qn
  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.




Objectifs du cours

Apprendre et maîtriser les concepts de logique et de mathématiques discrètes liés aux problèmes de programmation et de structures informatiques. À l’occasion, appliquer ces notions à la réalisation de programmes informatiques.




Stratégies pédagogiques

Chaque rencontre comportera une partie théorique et une partie pratique, pour un total d'environ trois heures trente de théorie et trois heures d'exercices par semaine.

Pendant que les cours seront donnés à distance, certaines notions théoriques seront présentées sous forme de capsules vidéos. 




Utilisation d’appareils électroniques

S.O.




Horaire
Groupe Jour Heure Activité
01 Jeudi 09:00 - 12:00 Travaux pratiques
Vendredi 09:00 - 12:30 Activité de cours
02 Mardi 09:00 - 12:00 Travaux pratiques
Mercredi 09:00 - 12:30 Activité de cours
03 Lundi 09:00 - 12:30 Activité de cours
Jeudi 13:30 - 16:30 Travaux pratiques
04 Lundi 18:00 - 21:00 Travaux pratiques
Mardi 18:00 - 21:30 Activité de cours



Coordonnées du personnel enseignant le cours
Groupe Nom Activité Courriel Local Disponibilité
01 Xavier Provençal Activité de cours Xavier.Provencal@etsmtl.ca B-2306
01 Xavier Provençal Travaux pratiques Xavier.Provencal@etsmtl.ca B-2306
02 Geneviève Savard Activité de cours Genevieve.Savard@etsmtl.ca B-2554
02 Geneviève Savard Travaux pratiques Genevieve.Savard@etsmtl.ca B-2554
03 Geneviève Savard Activité de cours Genevieve.Savard@etsmtl.ca B-2554
03 Geneviève Savard Travaux pratiques Genevieve.Savard@etsmtl.ca B-2554
04 Xavier Provençal Activité de cours Xavier.Provencal@etsmtl.ca B-2306
04 Xavier Provençal Travaux pratiques Xavier.Provencal@etsmtl.ca B-2306



Cours
Cours Matière Chapitres des notes de cours Sections du manuel de Rosen, 7e édition Heures

1 - 2

Logique. Équivalences propositionnelles. Prédicats et quantificateurs. Règles d'inférence. Méthodes de preuve.

1

1.1 à 1.8

6

3

Ensemble : opérations sur les ensembles.

Fonctions : injections, surjections, bijections.  

1

2.1 à 2.3, 2.5

3

4-5

Nombres entiers et division. Arithmétique modulaire. Entiers et algorithmes. Cryptographie RSA.

2

 

4.1 à 4.6

6

6

Algèbre booléenne. Fonctions booléennes et leurs représentations. Portes logiques. Minimisation de circuit.

3

12.1 à 12.4

3

7

Examen intra portant sur les cours 1 à 6

 

 

3

8 - 9

Comportement asymptotique des fonctions. Suites et sommations. Algorithmes. Complexité des algorithmes.

4

3.1 à 3.3 et 2.4

6

10

Principe de récurrence. Définitions récursives. Algorithmes récursifs.

5

5.1 à 5.4

3

11

Notions de base du dénombrement. Permutations et combinaisons. Relations de récurrence.

6

6.1 à 6.3

3

12 - 13

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

8

10.1 à 10.6

6

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:

  1. Connaître la syntaxe des expressions logiques : and, or, not.
  2. Connaître le fonctionnement de l’éditeur de programmes et de fonctions.
  3. Savoir implémenter une fonction définie par récurrence.
  4. Savoir implémenter une fonction récursive définie par une relation de type diviser pour régner.
  5. 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.
  6. 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
Examen intra : 30 % Voir le tableau des dates des examens intra
Devoirs : 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 aura lieu en présence si les conditions le permettent.
  • L'examen final est d'une durée de 3 heures.
  • Toute documentation est permise.



Double seuil
Note minimale : 50



Dates des examens intra
Groupe(s) Date
1 18 février 2021
2 16 février 2021
3, 4 15 février 2021



Date de l'examen final
Votre examen final aura lieu pendant la période des examens finaux, veuillez consulter l'horaire à l'adresse suivante : https://www.etsmtl.ca/programmes-et-formations/horaire-des-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.

Dispositions additionnelles

Tout retard pourra entraîner la note zéro.




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).



Infractions de nature académique
Les clauses du « Règlement sur les infractions de nature académique de l’ÉTS » s’appliquent dans ce cours ainsi que dans tous les cours du département. Les étudiants doivent consulter le Règlement sur les infractions de nature académique (https://www.etsmtl.ca/docs/ETS/Gouvernance/Secretariat-general/Cadre-reglementaire/Documents/Infractions-nature-academique ) pour identifier les actes considérés comme étant des infractions de nature académique ainsi que prendre connaissance des sanctions prévues à cet effet.  À l’ÉTS, le respect de la propriété intellectuelle est une valeur essentielle et les étudiants sont invités à consulter la page Citer, pas plagier ! (https://www.etsmtl.ca/Etudiants-actuels/Baccalaureat/Citer-pas-plagier).



Documentation obligatoire

Notes de cours  MAT210 - Logique et mathématiques discrètes, version révisée en juillet 2020, disponibles en version électronique sur Moodle.

 




Ouvrages de références

ROSEN, Kenneth H. Discrete Mathematics and Its Applications, 8e édition, McGraw-Hill. (Suggéré mais non obligatoire.)

Documentation additionnelle :

  1. ABELSON, H., J. SUSSMAN. Structure et interprétation des programmes informatiques, InterEditions.
  2. BRASSARD G., P. BRATLEY. Algorithmique conception et analyse, Masson, Presse de l’Université de Montréal.
  3. COMTET, Louis. Advanced Combinatorics, D. Reidl Publishing Company.
  4. GRAHAM, KNUTH, PATASHNIK. Concrete Mathematics, A Fondation for Computer Science, Addison-Wesley.
  5. ROSEN, Kenneth H. Handbook of Discrete and Combinatorial Mathematics, CRC Press.
  6. STANLEY, Richard P. Enumerative Combinatorics, Wadsworth & Brooks.
  7. STANAT, MC ALLISTER, Discrete mathematics in computer science, Prentice Hall.



Adresse internet du site de cours et autres liens utiles

Site web du cours : https://ena.etsmtl.ca/course/view.php?id=95

Site consacré à la TI-nspire CX CAS : https://seg-apps.etsmtl.ca/nspire/