Logo ÉTS
Session
Cours
Responsable(s) Xavier Provençal, Anouk Bergeron-Brlek

Se connecter
 

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

Responsable(s) de cours : Xavier Provençal
Anouk Bergeron-Brlek


PLAN DE COURS

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





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.

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

Trois heures de cours magistral par semaine. De nombreux exemples seront faits en classe pour permettre aux étudiantes et étudiants de bien assimiler la théorie et les techniques présentées durant le cours.

Les 3 heures hebdomadaires de travaux pratiques pourront servir à travailler les exercices distribués, à demander des éclaircissements sur les notions vues au cours, et à compléter le cours magistral par certaines démonstrations ou certains exemples s’il y a lieu.

 



Utilisation d’appareils électroniques

Afin de permettre une participation active en classe, il est obligatoire que chaque étudiante et étudiant possède une calculatrice TI-Nspire CX II CAS (ou l'ancien modèle TI-Nspire CX CAS). Ces calculatrices sont en vente à la COOP en combo avec le logiciel Nspire. 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.
  2. Utiliser la librarie numtheory pour la manipulation de grands entiers.
  3. Connaître le fonctionnement de l’éditeur de programmes et de fonctions.
  4. Définir une relation de récurrence et obtenir les premiers termes.
  5. Effectuer différentes opérations matricielles.



Horaire
Groupe Jour Heure Activité
01 Lundi 13:30 - 16:30 Laboratoire
Jeudi 09:00 - 12:30 Activité de cours
02 Lundi 18:00 - 21:00 Laboratoire
Mercredi 18:00 - 21:30 Activité de cours
03 Lundi 13:30 - 17:00 Activité de cours
Jeudi 09:00 - 12:00 Laboratoire



Coordonnées de l’enseignant
Groupe Nom Activité Courriel Local Disponibilité
01 Mounira Groiez Activité de cours Mounira.Groiez@etsmtl.ca
01 Zoumana Coulibaly Laboratoire Zoumana.Coulibaly@etsmtl.ca B-2520
02 Xavier Provençal Activité de cours Xavier.Provencal@etsmtl.ca B-2306
02 Xavier Provençal Laboratoire Xavier.Provencal@etsmtl.ca B-2306
03 Xavier Provençal Activité de cours Xavier.Provencal@etsmtl.ca B-2306
03 Xavier Provençal Laboratoire Xavier.Provencal@etsmtl.ca B-2306



Cours
Cours Matière Chapitres des notes de cours Heures

1

Complexité des algorithmes. Notation grand-O. Résolution de sommations.

4

3

2

Algorithmes récursifs. Relations de récurrence. Algorithmes de type diviser pour régner.

5

3

3 - 4

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

1

6

5

Ensemble : opérations sur les ensembles.
Fonctions : injections, surjections, bijections.  

1

3

6

Dénombrement. Principes de base, permutations, arrangements et combinaisons. Dénombrement par relation de récurrence.

7

3

7

Examen intra portant sur les cours 1 à 6

  

3

8

Preuves par récurrence.

6

 3

9 - 10

Arithmétique modulaire. Représentation des entiers dans une base quelconque. Entiers et algorithmes. Cryptographie RSA.

2

 

6

11

Représentation des entiers et manipulations bit à bit.

3

3

12 - 13

Théorie des graphes. Types de graphes, terminologie, représentation et utilisation. Chemins dans un graphe. Chemins eulériens et hamiltoniens. Problème du plus court chemin.

8

 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

S.O.


Évaluation
Mode d'évaluation Pondération
 Mini-tests et devoirs 40%
 Examen intra (3h) 30%
 Examen final (3h) 30%


Examen intra

L'examen intra est d'une durée totale de 3 heures. Il comportera deux parties: une première sans la calculatrice et une deuxième où l'usage de la calculatrice TI-Nspire CX CAS est permis. L'examen portera sur le contenu des cours 1 à 6 tel que décrit à la section « Cours ». Les modalités de l'examen seront communiquées par l'enseignante ou l'enseignant  de chaque cours-groupe.

 

Examen final

L’examen final est d’une durée totale de 3 heures. Il comportera deux parties : une première sans la calculatrice et une deuxième où l'usage de la calculatrice TI-Nspire CX CAS est permis. L'examen portera sur le contenu des cours 8 à 13 tel que décrit à la section « Cours ».  L'ordinateur portable et la documentation électronique sont interdits.

Documentation papier permise pour l’examen final (voir la page Moodle du cours pour des copies) :

  • Un résumé personnel d'une (1) feuille 8½ ×11, recto verso, manuscrit ou tapé à l’ordinateur;
  • La feuille « MAT210 et MAT215 - Tables »;
  • La feuille « MAT210 - Théorèmes »;
  • La feuille « MAT210 - Algorithmes ».

 

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.



Double seuil
Note minimale : 50



Dates des examens intra
Groupe(s) Date
1 15 février 2024
2, 3 19 février 2024



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



Infractions de nature académique
À 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/Etudes/citer-pas-plagier). Les clauses du règlement sur les infractions de nature académique de l’ÉTS (« Règlement ») 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 qui constituent des infractions de nature académique au sens du Règlement ainsi que prendre connaissance des sanctions prévues à cet effet.

Systèmes d’intelligence artificielle générative (SIAG)
L’utilisation des systèmes d’intelligence artificielle générative (SIAG) dans les activités d’évaluation constitue une infraction de nature académique au sens du Règlement sur les infractions de nature académique, sauf si elle est explicitement autorisée par l’enseignant(e) du cours.



Documentation obligatoire

Notes de cours MAT210 - Logique et mathématiques discrètes, disponibles à la COOP ÉTS et en version électronique sur la page Moodle du cours.



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. COMTET, Louis. Advanced Combinatorics, D. Reidl Publishing Company.
  3. GRAHAM, KNUTH, PATASHNIK. Concrete Mathematics, A Fondation for Computer Science, Addison-Wesley.
  4. ROSEN, Kenneth H. Handbook of Discrete and Combinatorial Mathematics, CRC Press.
  5. 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/

Vidéos sur l'utilisation de Nspire à l'ÉTS (chaîne VUnETS sur YouTube) : https://etsmtl.ca/vunets



Autres informations

Les séances de cours et de travaux pratiques des cours-groupes dont le mode d'enseignement est hybride sont offertes entièrement à distance. L'étudiante ou l'étudiant inscrit à un tel cours-groupe n'a donc pas besoin de se déplacer à l'École durant la session, sauf lors des évaluations en présence identifiées à la section "Évaluation".