Logo ÉTS
Session
Cours
Responsable(s) Geneviève Savard, Anouk Bergeron-Brlek

Se connecter
 

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

Responsable(s) de cours : Geneviève Savard
Anouk Bergeron-Brlek


PLAN DE COURS

Automne 2022
MAT215 : Logique et mathématiques discrètes pour l’optimisation (4 cr.) (4 crédits)





Préalables
Programme(s) : 7095, 7495
             
  Profils(s) : Informatique  
             
    MAT145    
             
Programme(s) : 7095, 7495
             
  Profils(s) : Administration, Production, Reseaux  
             
    MAT145 ET *INF130    
             
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
Au terme de ce cours, l’étudiante ou l'étudiant aura acquis les notions fondamentales de la logique mathématique. S’initier aux concepts des mathématiques discrètes utilisés dans les méthodes d’optimisation. Introduction à la logique et son utilisation pour la modélisation de contraintes. Théorie des ensembles : terminologie, notion de fonctions et dénombrement. Rédaction de preuves mathématiques. Introduction aux algorithmes et à l’analyse de la complexité. Principe de récursivité et preuves par récurrence. Théorie des graphes : terminologie, arbres, algorithmes et applications. Séances de travaux pratiques composées d'exercices choisis pour illustrer et compléter la théorie vue en classe. Précision sur le préalable INF130 : ce cours est un cours associé, c'est-à-dire qu'il doit être suivi en même temps que MAT215.



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 modélisation. À 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.

 



Utilisation d’appareils électroniques

S.O.



Horaire
Groupe Jour Heure Activité
01 Mercredi 09:00 - 12:30 Activité de cours
Vendredi 09:00 - 12:00 Travaux pratiques
02 Lundi 09:00 - 12:00 Travaux pratiques
Mercredi 13:30 - 17:00 Activité de cours



Coordonnées de l’enseignant
Groupe Nom Activité Courriel Local Disponibilité
01 Omar Foutlane Activité de cours Omar.Foutlane@etsmtl.ca B-2520
01 Omar Foutlane Travaux pratiques Omar.Foutlane@etsmtl.ca B-2520



Cours

Cours

Matière

Chapitres des notes de cours

Heures

1 - 2

Logique propositionnelle. Équivalences propositionnelles. Prédicats et quantificateurs. Règles d'inférence. Cohérence d’un ensemble de spécifications. Types de preuve.

1

6

3

Ensemble : opérations sur les ensembles. Fonctions.

1

1.5

3 - 4

Modélisation. Identification des variables, des contraintes et de la fonction-objectif dans un problème d'optimisation. Solution admissible, solution optimale.

2

3

4-5

Théorie des graphes : types de graphes, terminologie, représentation et utilisation. Matrice d’adjacence d’un graphe. Connectivité. Chemins eulériens et hamiltoniens d’un graphe, circuit et applications. Problème du plus court chemin (algorithme de Dijkstra).

3

4.5

6

Théorie des graphes (suite): tri topologique (algorithme de Kahn), chemin de poids maximal, chemin critique.

3

3

7

Examen intra portant sur les cours 1 à 6

4

3

8

Arbres: définitions de base, théorèmes sur les arbres, arbre couvrant de poids minimal (algorithme de Prim).

4

3

 9

Introduction à la complexité des algorithmes: mesurer un temps de calcul à l’aide d’une fonction, notation grand-O et grand-Θ, résolution de sommations, fonction de complexité d’un algorithme.

5

4.5

10

Algorithmes récursifs. Fonctions récursives et relations de récurrence. Algorithmes de type diviser pour régner.

5

3

11

Preuves par récurrence. Principe de récurrence forte. Preuve de validité d’un algorithme récursif.

7

3

12 -13

Notions de base du dénombrement. Permutations et combinaisons. Dénombrement par relation de récurrence.

8

4.5

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·e possède une calculatrice TI-Nspire CX II CAS. 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).

Le programme Excel sera utilisé pour trouver des solutions optimales à des problèmes de programmation linéaire dans le chapitre sur la modélisation. L'utilisation du solveur sera présentée.


Évaluation
Examen intra : 30 % Voir le tableau des dates des examens intra
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.

Note: Les évaluations effectuées en classe pour lesquelles l’entraide n’est pas permise, notamment l’examen intra et l’examen final, sont considérées comme étant individuelles. Toutes autres évaluations pour lesquelles l’entraide entre étudiant·es est possible qu'elles aient lieu en classe ou non, et ce même si une remise par étudiant·e est exigée, sont considérées comme étant en équipe.

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 est permis.

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 est permis.

Matériel permis pour l’examen final

  • Un résumé personnel de 2 feuilles 8½ ×11, recto verso, manuscrit ou tapé à l’ordinateur.
  • Une calculatrice TI-Nspire pour la 2e partie de l'examen seulement.



Double seuil
Note minimale : 50



Dates des examens intra
Groupe(s) Date
1 21 octobre 2022



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
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  MAT215 - Logique et mathématiques discrètes pour l'optimisation, publiées en août 2021, disponibles à la Coop ÉTS et 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.)

Yves Norbert, Roch Ouellet, Régis Parent: Méthodes d’optimisation pour la gestion. Chenelière Éducation, 2016. 2e édition. (Suggéré pour le chapitre modélisation, 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=15071 

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'étudiant·e inscrit·e à 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".