Logo ÉTS
Session
Cours
Responsable(s)

Se connecter
 

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

Responsable(s) de cours :


PLAN DE COURS

Hiver 2021
LOG780 : Sujets émergents en génie logiciel (3 crédits)
Programmation compétitive


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
Aucun préalable requis
Unités d'agrément
Total d'unités d'agrément : 58,8 60,0 % 40,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’étudiant aura vu les aspects nouveaux et cruciaux en génie logiciel.

Stratégies technologiques pertinentes liées à la planification, à la conception ou à la gestion des systèmes logiciels actuels ou proposés par les industries qui évoluent dans le domaine du génie logiciel.



Objectifs du cours

Étude des aspects nouveaux et d'intérêt majeur en génie logiciel. Les concepts abordés couvrent les stratégies technologiques pertinentes liées à la planification, à la conception ou à la gestion des systèmes matériels ou logiciels actuels ou proposés par les industries qui évoluent dans le domaine de génie logiciel.

La mouture du cours LOG780 offert à la session H-2021 portera spécifiquement sur la Programmation Compétitive.

Ce cours permet aux étudiant(e)s le suivant:

  • Choisir les structures de données adéquates pour la résolution de problèmes
  • Améliorer leurs compétences en conception d'algorithmes et résolution de problèmes
  • Développer des programmes efficaces et fiables
  • Pratiquer leurs compétences de travail d'équipe dans des compétitions de programmation
  • Bien gérer leur temps avec des délais serrés



Stratégies pédagogiques

Le cours comprend:
- Un cours magistral par semaine, couvrant les aspects théoriques ainsi que des exemples et exercices (3 heures)
- Une séance de laboratoire par semaine, permettant aux étudiants de se préparer pour les compétitions (2 heures)

Le cours sera dispensé à distance via Zoom. Les informations pour se connecter aux sessions Zoom seront communiquées sur Moodle.



Utilisation d’appareils électroniques

Tel que stipulé par les directives de l'ÉTS, les étudiant(e)s doivent avoir un ordinateur muni d'une caméra et d'un microphone, de la dernière version du logiciel Zoom, et d'une connexion Internet adéquate. L'ordinateur sera utilisé pour suivre le cours magistral ainsi que pour la réalisation des exercices, laboratoires, devoirs et compétitions.



Horaire
Groupe Jour Heure Activité
01 Mardi 13:30 - 15:30 Laboratoire
Vendredi 13:30 - 17:00 Activité de cours



Coordonnées de l’enseignant
Groupe Nom Activité Courriel Local Disponibilité
01 Diala Naboulsi Activité de cours Diala.Naboulsi@etsmtl.ca A-4496 Sur rendez-vous
01 Guillaume Baril Laboratoire cc-Guillaume.Baril@etsmtl.ca A-4526



Cours

Ci-dessous se trouve le plan de cours prévu avec les heures approximatives d'enseignement pour chaque sujet et incluent le temps alloué pour une compétition de groupe et l'examen intra (compétition individuelle). Des modifications et ajustements au plan du cours pourront avoir lieu durant la session.

  1. Introduction à la programmation compétitive (3.5 heures)
    • Introduction aux compétitions et platformes existantes
    • Comment être compétitif
  2. Structures de données (SD) (7 heures)
    • SD linéaires avec librairies intégrées
    • SD non linéaires avec librairies intégrées
    • SD avec nos propres librairie
  3. Chaines (3.5 heures)
    • Algorithmes de recherches de sous-chaine
    • Arbre et tableau de suffixe
  4. Paradigmes de résolution de problèmes (5.5 heures)
    • Recherche exhaustive
    • Diviser pour régner
    • Algorithmes gloutons
    • Programmation dynamique
  5. Graphes (5 heures)
    • Algorithmes de parcours de graphes
    • Arbre couvrant de poids minimal
    • Problème du plus court chemin avec source unique
    • Problème de toutes les paires de plus courts chemins
    • Graphes spéciaux
  6. Analyse combinatoire (2.5 heures)
    • Nombres de Fibonacci
    • Coefficients binomiaux
    • Nombres Catalans
  7. Autres sujets mathématiques (1.5 heure)
    • Probabilités
    • Théorie de jeu
  8. Théorie des nombres (3.5 heures)
    • Nombres premiers
    • Décomposition en facteurs premiers
    • Crible d'Érastosthène
    • PGCD et PPCM
    • Factoriel
    • Arithmétique modulaire
    • Algorithme d'Euclide étendu
  9. Géométrie (3.5 heures)
    • Objets géométriques de base
    • Périmètre et aire d'un polygone
    • Test de convexité d'un polygone
    • Emplacement d'un point par rapport à un polygone
    • Découpage d'un polygone avec une droite
    • Enveloppe convexe
  10. Sujets divers (3.5 heures)
    • Algorithmes de recherche avancés
    • Problème du flot maximum
    • Couplage d'un graphe

Tous les cours sont d'une durée de 3 heures et 30 minutes par semaine (incluant une pause de 30 minutes).



Laboratoires et travaux pratiques

Des laboratoires seront proposés au cours de la session et permettront aux étudiants de mettre en pratique leurs compétences de résolution de problèmes.

  • Laboratoire 1: Introduction à la plateforme codewars
  • Laboratoire 2 et 3:
    • Introduction à la plateforme kattis
    • Structures de données
  • Laboratoire 4: Chaines
  • Laboratoire 5: Résolution de la compétition 1
  • Laboratoire 6/7/8:
    • Paradigmes de résolution de problèmes
    • Graphes
  • Laboratoire 9: Analyse combinatoire
  • Laboratoire 10: Résolution de la compétition 2
  • Laboratoire 11: Théorie des nombres
  • Laboratoire 12: Géométrie



Utilisation d'outils d'ingénierie

Les étudiant(e)s utiliseront un outil de développement logiciel intégré (IDE) pour développer des logiciels.

Note importante: Les exemples de cours seront en Java. Les exercices, laboratoires, devoirs et compétitions sont aussi vérifiés en Java. Vous pouvez utiliser d’autres langages, mais nous ne pouvons pas garantir les différences de performance.


Évaluation

 

8 Devoirs  20 %
Compétition de groupe  20 %
Examen intra (Compétition individuelle) 30 %
Examen final 30 %

 

Dates et modalités :

Compétition de groupe 5 Février 2021
Examen intra  12 Mars 2021
Examen final Durant la période des examens finaux

 

Veuillez noter qu’une moyenne inférieure à 50% dans les évaluations individuelles de type "examen" (examens intra et final) entraîne automatiquement un échec au cours. Ceci est une condition nécessaire mais non suffisante pour réussir ce cours.



Double seuil
Note minimale : 50



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.

Dispositions additionnelles

Les travaux remis en retard ne seront pas corrigés et l’étudiant(e) se verra attribué(e) la note zéro (0).



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

Aucune documentation obligatoire.



Ouvrages de références
  • S. Halim, F. Halim, S. Effendy “Competitive Programming 4 – Book 1", Lulu Independent Publish, 2020
  • S. Halim, F. Halim, S. Effendy “Competitive Programming 4 – Book 2", Lulu Independent Publish, 2020
  • S. Skienna, M. Revilla, "Programming Challenges", Springer Verlag, 2003
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms (Third Edition)", MIT Press, Cambridge, MA, 2009



Adresse internet du site de cours et autres liens utiles

Site Moodle/ENA du cours: https://ena.etsmtl.ca/course/view.php?id=13756