LOG2810 A2020 Plan cours PDF

Preview

Summary

Download LOG2810 A2020 Plan cours PDF

Description

Plan de cours LOG2810 - Structures discrètes Département de génie informatique et de génie logiciel Automne 2020 3 Crédits Triplet horaire : 3 - 3- 3 http://www.moodle.polymtl.ca/

Chargé de cours Nom Aurel RANDOLPH Bureau Téléphone Courriel Disponibilité

Pavillon MacKay-Lassonde, bureau M-3010 (514) 340-4711 - 2025 [email protected] Sur rendez-vous

Coordonnateur du cours Nom John MULLINS Bureau Téléphone Courriel Disponibilité

Pavillon MacKay-Lassonde, bureau M-4101 (514) 340-4711 - 4233 [email protected] Sur rendez-vous

Chargés de laboratoire Noms Mohameth Alassane Ndiaye Bureaux Pavillon MacKay-Lassonde, bureau M-4122 Courriels [email protected] Disponibilités Sur rendez-vous

Saif-Eddine Sajid Pavillon MacKay-Lassonde, bureau M-4122 [email protected] Sur rendez-vous

Description du cours Rôle des structures discrètes en génie logiciel et génie informatique. Ensembles et logique de base. Techniques de preuves : règles d'inférence et de déduction. Relations et fonctions. Algorithmes : définition, analyse, récursivité. Éléments de combinatoire : énumération, permutations et combinaisons. Relations de récurrence. Théorie des graphes. Arbres. Automates, grammaires et langages.

Polytechnique Montréal

1

Qualités du BCAPG Dans le cadre de ce cours, les étudiants développeront les qualités précisées dans le tableau cidessous (www.polymtl.ca/etudes/bc/qualites). 1 Connaissance en génie

2 Analyse de problèmes

3 Investigation

4 Conception

Introduction

Introduction

Introduction

Introduction

7 Communication

8 Professionnalisme

9 Impacts du génie sur la société et l’env.

10 Déontologie

5 Utilisation d’outils d’ing.

6 Travail ind. et équipe

11 Économie et gestion de projets

12 Apprentissage continu

Introduction

Cours préalables Aucun¶

Cours corequis

Cours subséquents

INF2010-Structures de données et algorithmes ¶

▪ LOG3210 - Éléments de langage et compilateurs ▪ LOG3430 - Méthodes de test et de validation du logiciel ▪ LOG4410 - Méthodes formelles en fiabilité et sécurité des systèmes ▪ LOG8470 – Vérification de fiabilité et de la sécurité ▪ INF4705 (INF8775) - Analyse et conception d'algorithmes

Objectifs d’apprentissage Ce cours a pour but de présenter les fondements du raisonnement et les méthodes rigoureuses appliquées dans le traitement des structures discrètes. À la fin du cours, l'étudiant sera en mesure : ▪ d'appliquer des techniques de preuves pour la démonstration formelle de propositions concernant les structures discrètes ; ▪ de maîtriser le raisonnement mathématique nécessaire à la vérification d'algorithmes ; ▪ d'appliquer des notions de la théorie des graphes et des structures arborescentes au développement d'algorithmes et de structures de données ; ▪ d'appliquer les notions de langages formels et d’automates pour modéliser, spécifier et vérifier les systèmes à états finis ; ▪ d'implanter les algorithmes sur les structures discrètes.

Méthodes d’enseignement et d’apprentissage Les notions étudiées seront présentées en cours. Des séances de travaux dirigées permettront aux étudiants d'appliquer ces notions en réalisant des exercices d'applications et des exercices d'approfondissement. Des travaux de laboratoire, en équipe, consacrés à la réalisation de travaux pratiques permettront d'implanter des algorithmes sur les structures discrètes étudiées. Le triplet horaire indique 3 heures de travail personnel par semaine. Pendant ces heures, il est conseillé aux étudiants de lire, dans les notes de cours et dans le manuel du cours (livre de Rosen), les chapitres présentés durant les séances de cours, en particulier les nombreux exemples. On préconise aussi de résoudre certains des exercices du livre - noter que de nombreux exercices sont corrigés succinctement à la fin du livre.

Polytechnique Montréal

2

Évaluation L'évaluation des étudiants se fonde sur les contrôles périodiques, les travaux pratiques et sur l'examen final selon la pondération indiquée ci-dessous.

Nature Contrôle périodique 1 Contrôle périodique 2 Travail pratique 1 Contrôle périodique 3 Travail pratique 2 Examen final

Nombre

Pondération

1 1 1 1 1 1

10% 10% 10% 10% 10% 50%

Date Voir calendrier Voir calendrier Voir calendrier Voir calendrier Voir calendrier xx décembre 2020

Contrôles périodiques •

• • •

Les contrôles périodiques se dérouleront à la date consignée dans le calendrier. Ils auront lieu en ligne. La copie de l’étudiant(e) doit être soumise pour évaluation, au plus tard à la fin du délai qui sera indiqué. Aucune copie ne sera acceptée hors délai. Des directives complémentaires pourraient communiquées avant ou au début de chaque contrôle périodique. Chaque contrôle périodique durera 60 minutes environ. La documentation sera permise lors des contrôles périodiques. Toute absence à un contrôle périodique doit être motivée selon les règlements en vigueur. Une absence non motivée entraînera automatiquement une note de 0 à ce contrôle périodique. Une absence motivée à un contrôle périodique entraînera une reprise qui peut être ou non sous la forme d'un examen oral devant jury.

Examen final • •

•

L’examen final se déroulera en présentiel ou en ligne. Toute absence à l'examen final doit être motivée selon les règlements en vigueur. Une absence non motivée entraînera automatiquement une note de 0 à l'examen final. Une absence motivée à l'examen final entraînera une reprise qui peut être ou non sous la forme d'un examen oral devant jury. Aucune documentation ne sera permise lors de l’examen final, à l’exception d’une feuille recto-verso destinée à servir d’aide-mémoire à l’étudiant. Cette feuille doit être manuscrite et au format 8 1/2 x 11.

Des directives complémentaires pourraient communiquées avant ou au début de l’examen final.

Travaux dirigés Durant les séances de TD, les étudiants résoudront des exercices d'application du cours, ainsi que des exercices d'approfondissement. On souhaite que les étudiants jouent un rôle actif durant les TD, le chargé de laboratoire étant là principalement pour les guider. Les étudiants sont encouragés à travailler en groupes de trois (3) personnes ou plus. Au début de la séance, le chargé de laboratoire indique la liste des exercices proposés. Les étudiants se rassemblent pour former des groupes de trois ou plusieurs membres. Au sein de chaque groupe, les étudiants discutent afin de formuler et de rédiger leurs réponses - les étudiants peuvent préparer de réponses individuelles ou par groupe, selon leur gré. Pendant les travaux en groupe, le chargé de laboratoire répond aux questions des étudiants. Il corrige certains des exercices proposés, mais pas nécessairement tous. Compte tenu du nombre d'exercices proposés, il est normal que certains étudiants n'aient pas le temps de les résoudre tous pendant la séance de TD. Si un étudiant a traité un exercice qui n'a pas été corrigé durant la séance, il peut néanmoins obtenir une correction. Pour cela, il lui suffit de transmettre ses propositions de solutions (lisiblement rédigées) au chargé de TD à la fin de la séance. Les copies remises au chargé de TD seront rendues lors de la séance suivante, avec les annotations du chargé de TD. Les copies ne seront pas notées.

Polytechnique Montréal

3

Travaux pratiques Les séances de TP se font sur ordinateur. Les étudiants sont incités à travailler en groupes de trois personnes. Les énoncés des TP seront affichés sur le site Moodle du cours. Ces énoncés contiennent une description précise du travail à réaliser, ses livrables, la grille d'évaluation et la date de remise. Pendant la séance de TP, le chargé de laboratoire répond aux questions des étudiants. Les livrables sont remis au chargé de laboratoire via Moodle. Ces livrables seront corrigés et un rapport avec les annotations du chargé de laboratoire sera remis à chaque groupe. Les travaux pratiques remis en retard seront pénalisés de 10% par jour de retard.

Documentation Manuel du cours obligatoire : Mathématiques discrètes K.H. Rosen, publié chez Chenelière, édition révisée, 2006. Notes de cours : Elles sont présentes sur le site du cours. Il s'agit du texte des présentations utilisées en cours.

Plan des séances de cours Le tableau ci-dessous présente la planification détaillée du cours. Elle est à titre indicatif et peut être modifiée par l’enseignant durant la session. La colonne Manuel indique des numéros de chapitre dans le manuel du cours (le livre de Rosen). Séance

Sujets traités

Manuel

1

Présentation du cours. Logique propositionnelle et logique du premier ordre. Ensembles.

1.(1,2,3,4,5)

2

Raisonnement mathématique : déduction. Relations : propriétés d’une relation, relation d'équivalence. Raisonnement mathématique : relation d'ordre Fonctions : propriétés d'une fonction, composition. Notation asymptotique. Raisonnement mathématique : déduction.

3.1 ; 6.1, 6.3, 6.5

Raisonnement mathématique : induction. Récursivité : ensembles définis récursivement,

3.2-5

3

4

6.6 1.(6,7,8)

algorithmes récursifs. Fermeture d’une relation

6.4

5

Graphes : introduction, isomorphisme de graphes.

6

Graphes : parcours de graphe. Arbres : introduction.

7.(1-3) 7.(4-6) ; 8.(1-3)

7

Arbres : propriétés, arborescence ordonnée, parcours

8.(5,6)

8

Dénombrement : combinatoire, techniques avancées (fonctions génératrices, récurrence avec

4.(1,2,3)

fractionnement), inclusion/exclusion Langages et grammaires. Automates à états finis avec sortie. Équivalence des machines de

4.6 ; 5.(1-5) 10.(1,2) ; Notes

Moore et de Mealy.

de cours.

10

Automates à états finis sans sortie. Automates non-déterministes. Déterminisation.

10.4 ; notes de cours.

11

Langages réguliers, expressions régulières, théorème de Kleene, lemme de pompage.

Notes de cours.

12

Révision

9

Polytechnique Montréal

4

Calendrier Il est à titre indicatif et peut être modifié par l’enseignant durant la session pour s’arrimer à la modification du plan des séances de cours.

Dimanche

AOÛT

30

SEPTEMBRE

6

Lundi

Mardi 31

Mercredi 1

Cours 1 – 01

13

20

7 Fête du travail 14 Date limite d'ab. sans frais 21

8 Cours 2 – 01

Cours 3 – 01

OCTOBRE

Contrôle 1

R

E 18

1

20

9 Date limite d'ab. facture

15

10

DÉCEMBRE

30

Contrôle 3 7

14

TD 5 / TP1 15

TD 5 / TP1 16

H 22 TD 6 / TP 1

28

23

24

TD 6 / TP 1

29 TD 7

30

31

6

7

13

14

TD 7

4

5 TD 8

11 Cours 10 – 02 TP2

17

E

TD 8 12

TP2

TP2

18 Cours 11 – 02 TD 9 / TP2

24

25 Cours 12 – 02 TD 10 / TP2

26

27

TD 10 / TP2

TD 10 / TP2

1

2

3

4

5

9

10 Début des examens

11

12

Cours 13 – 01 Remise TP2 6

9

17

Cours 12 – 01 29

TD 4 8

Cours 9 – 02 TD 8

Cours 10 – 01

23

10 RELÂCHE

TD 3 1

TD 4

Cours 8 – 02 TD 7

Cours 11 – 01 22

3

24

7

3

16

2

TD 2

TD 3

21 Cours 7 – 02 TD 6 / TP 1

27

Cours 9 – 01 8 Contrôle 2

26

C

LÂ

2

25

TD 2

Cours 6 – 02 TD 5 / TP1

Cours 8 – 01 Remise TP1

NOVEMBRE

19

TD 1 17

30

13

26

18

Cours 5 – 02 TD 4

Cours 7 – 01 25

12

TD 1

6

19

11

23

29

12

10

Cours 4 – 02 TD 3

Cours 6 – 01 11

9

16

22

5

5

Cours 3 – 02 TD 2

Cours 5 – 01 4

Samedi

4

Cours 2 – 02 TD 1 15

28

Vendredi 3

Cours 1 – 02

Cours 4 – 01 27

Jeudi 2

8 Présentation des projets

19 TD 9 / TP2

20

21

TD 9 / TP2 28

Cours 13 – 02

Fraude : infractions et sanctions En tant que futur ingénieur, l’étudiant doit adopter une attitude professionnelle exemplaire. L’article 8 des règlements des études au baccalauréat présente la position de Polytechnique Montréal à l’égard de la fraude sur la base du principe de tolérance zéro. Voici quelques éléments de cet article tirés de l’annuaire. Par fraude, on entend toute forme de plagiat, de tricherie ou tout autre moyen illicite utilisé par l'étudiant pour obtenir un résultat d’évaluation non mérité ou pour influencer une décision relative à un dossier académique. À titre d’exemple, constituent une fraude : Polytechnique Montréal

5

▪

▪ ▪ ▪ ▪

l’utilisation totale ou partielle, littérale ou déguisée, d’une œuvre d’autrui, y compris tout extrait provenant d’un support électronique, en le faisant passer pour sien ou sans indication de référence à l’occasion d’un examen, d’un travail ou de toute autre activité faisant l’objet d’une évaluation; le non respect des consignes lors d’un contrôle, d’un examen, d’un travail ou de toute autre activité faisant l’objet d’une évaluation; la sollicitation, l’offre ou l’échange d’information pendant un contrôle ou un examen; la falsification de résultats d’une évaluation ou de tout document en faisant partie; la possession ou l’utilisation pendant un contrôle ou un examen de tout document, matériel ou équipement non autorisé y compris la copie d’examen d’un autre étudiant;

Selon la gravité de l’infraction et l’existence de circonstances atténuantes ou aggravantes, l’étudiant peut se voir imposer une sanction correspondant à, entre autres, l’attribution de la cote 0 pour l’examen, le travail ou toute autre activité faisant l’objet d’une évaluation qui est en cause, l’attribution de la note F pour le cours en cause, l’attribution de la note F à tous les cours suivis au trimestre. Dans le cas d’un travail en équipe, les étudiants d’une même équipe de travail tel que reconnu par l’enseignant sont solidaires du matériel produit au nom de l’équipe. Si un membre de l’équipe produit et remet un travail au nom de l’équipe et qu’il s’avère que ce travail est frauduleux tous les membres de l’équipe sont susceptibles de recevoir une sanction à moins qu’il soit démontré sans ambiguïté que l’infraction est le fait d’un ou de quelques membres de l’équipe en particulier.

Les enregistrements vidéo auxquels l’étudiant(e) a accès dans le cadre de ce cours à l’École Polytechnique de Montréal sont protégés par la Loi sur le droit d’auteur du Canada (L.R.C. (1985) ch. C-42). En s’inscrivant au cours, l’étudiant(e) s’engage à ne pas les copier ou à les rediffuser sans l’accord préalable écrit de l’École Polytechnique de Montréal ou de l’enseignant. Toute violation de cet engagement pourra entraîner des sanctions à son égard.

Polytechnique Montréal

6...