Logo ÉTS
Session
Cours
Responsable(s) Patrick Cardinal

Se connecter
 

Sauvegarde réussie
La notification a été envoyée
Echec de sauvegarde
Avertissement
École de technologie supérieure

Responsable(s) de cours : Patrick Cardinal


PLAN DE COURS

Hiver 2026
LOG320 : Structures de données et algorithmes (4 crédits)


Préalables
Pour tous profils : MAT210, LOG121



Description du cours
Acquérir une connaissance spécifique au génie logiciel des structures de données et des algorithmes. Comprendre et utiliser l'analyse asymptotique afin de choisir judicieusement les structures de données appropriées et le type d'algorithme optimal pour résoudre efficacement un problème tout en respectant les contraintes imposées et les ressources disponibles.

Au terme de ce cours, l'étudiante ou l'étudiant sera en mesure de choisir parmi une multitude de structures de données de base (tableau, file, pile ou liste) ou plus avancées (structures en arbre, graphes, tables de hachage) afin de résoudre différents problèmes plus ou moins complexes. Il sera aussi en mesure de les combiner et de les adapter afin de faire face à différentes situations.

L’étudiante ou l'étudiant sera aussi en mesure de choisir le type d’algorithmes et d’analyser ses performances globales pour différents problèmes de base qui impliquent, par exemple, la recherche dans des graphes, l’optimisation combinatoire ou la recherche dans des chaînes de caractères.



Stratégies pédagogiques

- Un cours magistral par semaine (3 heures). Des exemples seront faits en classe pour permettre aux étudiants(es) d’assimiler les concepts théoriques.

- Une séance de travaux pratiques par semaine (1 heure approximativement*).

- Une séance de laboratoire par semaine (2 heures approximativement*).

Le temps pour la séance de travaux pratique peut varier (plus ou moins de temps) d'une semaine à l'autre dépendant de la théorie et des exercices faits en TP.  Ces heures sont fournies à titre indicatif seulement, mais la période de laboratoire au complet (séance de TP et labo) sera de 3 heures totales.




Informations concernant l’agrément du BCAPG
Ce cours compte 64,8 unités d'agrément réparties comme suit :

Catégories de UA Nombre Proportion Matière(s) traitée(s)
Science du génie 32,4 UA 50,00 %
Conception Ingénierie 32,4 UA 50,00 %






Utilisation d’appareils électroniques

Il est interdit de capter le cours ou des portions du cours (enregistrement vidéo, enregistrement audio, photographie, captures d'écrans) en salle de classe (en présence ou à distance par Zoom) ou en laboratoire (en présence ou à distance par Zoom) à moins d'avoir obtenue au préalable la permission de l'enseignant.

Pour les examens, vous avez besoin d'un ordinateur portable avec Windows ou Macos (en natif, pas dans une machine virtuelle) pour Safe Exam Browser. Les tablettes ne sont pas autorisées.




Horaire
Groupe Jour Heure Activité
01 Lundi 08:30 - 12:00 Activité de cours
Vendredi 13:30 - 16:30 Laboratoire
02 Mardi 13:30 - 16:30 Laboratoire
Mercredi 13:30 - 17:00 Activité de cours
03 Lundi 08:30 - 11:30 Laboratoire
Vendredi 13:30 - 17:00 Activité de cours
04 Mardi 13:30 - 17:00 Activité de cours
Mercredi 13:30 - 16:30 Laboratoire



Coordonnées du personnel enseignant le cours
Groupe Nom Activité Courriel Local Disponibilité
01 Alessandro Lameiras Koerich Activité de cours alessandro.lameiras-koerich@etsmtl.ca A-4487
01 Souad Hadjres Laboratoire cc-Souad.Hadjres@etsmtl.ca A-4526
01 Laboratoire
02 Christian Desrosiers Activité de cours christian.desrosiers@etsmtl.ca A-3416
02 Bilal Alchalabi Laboratoire CC-bilal.alchalabi@etsmtl.ca
03 Alessandro Lameiras Koerich Activité de cours alessandro.lameiras-koerich@etsmtl.ca A-4487
03 Souad Hadjres Laboratoire cc-Souad.Hadjres@etsmtl.ca A-4526
03 Laboratoire
04 Patrick Cardinal Activité de cours patrick.cardinal@etsmtl.ca
04 Souad Hadjres Laboratoire cc-Souad.Hadjres@etsmtl.ca A-4526
04 Francis Cardinal Laboratoire cc-Francis.Cardinal@etsmtl.ca A-4526



Cours
Semaine Contenu du cours
1
  • Introduction au cours
  • Analyse asymptotique : grand oh, grand omega et grand theta
  • Algorithmes de tri:
    • Tri par sélection
    • Tri par insertion
    • Tri à bulle
2
  • Algorithme récursif
    • Rappel sur la récursion
    • L'arbre de récursivité
    • Diviser pour régner
    • Retour en arrière
  • Analyse asymptotique
    • Méthode itérative
    • Méthode de l'arbre de récursivité
    • Méthode générale
3
  • Arbres de jeu
    • Algorithme Minimax
    • Algorithme alpha-beta
    • Heuristique
  • Structures de données de base
    • Pile, file, liste
    • Heap
4
  • Arbre binaire de recherche
    • Opérations de base
    • Recherche 
    • Insertion
    • Suppresion
  • Abre rouge-noir
    • Rotation
    • Insertion
5
  • Arbre rouge-noir (suite)
    • Suppresion
    • Augmentation de structure
  • Table de hachage
6
  • Graphes
    • Introduction et définitions
    • Recherche en largeur d'abord
    • Recherche en profondeur d'abord
    • Chemin de Euler
    • Chemin Hamiltonien
  • Exercices pour l'examen intra
7  Examen intra (Feuille de note fournie avec l'examen)
8
  • Introduction à l'optimisation combinatoire
    • Survol de la notion du NP-Complet
  • Algorithmes glouton
    • Dijkstra
    • A*
    • Sélection d'activité
    • Algorithme de Prim
    • Couverture de sommets
9
  • Programmation dynamique
    • Introduction
    • Mémoïsation
    • Exemples 
10
  • Branch and bound
  • Algorithmes probabilistes
11
  • Recherche dans les chaines de caractères
    • Algorithme naïf
    • Algorithme Boyer-Moore
    • Algorithme Knuth-Morris-Pratt
    • Distance de Leivenstein
12
  • Algorithmes parallèles
13
  • Exercices (quelques-un de programmation dynamique) pour l'examen final

 

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

NOTE : L'ordre et le contenu peut être modifié en cours de session en fonction de circonstances particulières

 




Laboratoires et travaux pratiques

Des laboratoires seront proposés au cours du trimestre afin de permettre aux étudiants (es) d’approfondir leurs connaissances et d’expérimenter les algorithmes montrés en classe.

Programmation compétitive (15 points) (6 séances) 

Description : Simulation de programmation compétitive avec des problèmes couvrant différents sujets du cours. Il y aura 5 séances de laboratoire qui seront dédiées à la programmation compétitive. 

Sujets couverts : Analyse asymptotique, structures de données, programmation dynamique, algorithmes glouton, recherche dans les chaines de caractères, conception, algorithmique.

Notation :  

  • Les 5 meilleurs résultats sur 6 sont considérés dans la note finale.
  • Les différents problèmes sont notés en fonction de vos performances : c’est-à-dire que le problème le mieux réussi est celui qui vaut le plus de points. Le deuxième mieux réussi vaut le deuxième plus grand nombre de points, et ainsi de suite. 
  • Pour obtenir des points dans un problème, il faut avoir réussi au moins 60 % des cas de test.

Notes importantes:

  • Ce laboratoire est individuel et se fait entièrement durant la période de laboratoire.  Cette activité est à réaliser en présence dans le local de l'ÉTS assigné.  Ceci est valable pour tous les cours-groupes peu importe les modalités d'enseignements du cours-groupe.  
  • La présence au laboratoire est obligatoire. L’étudiant(e) absent(e) se verra attribuer la note zéro (0). Accéder au laboratoire en ligne constitue une infraction et le cas pourrait être soumis au comité de discipline. Ce laboratoire est considéré comme une seule évaluation de 15%

  • L’utilisation de l’IA ou de toute autre ressource, sauf celles clairement spécifiées, est strictement interdite.

Jeu de plateau (15 points) (6 séances)

Description : Création d’un joueur « CPU » pour un jeu de plateau.

Sujets couverts : Algorithmes minimax et alpha-beta, tables de hachage, heuristiques.

Notes importantes:

  • Ce laboratoire se fait en équipe de 2 ou 3 (peut être fait individuellement aussi).
  • Lors des points de contrôle et du tournoi à la fin de la session,  tous les membres de l’équipe doivent être présents. L’étudiant(e) absent(e) se verra attribuer la note zéro (0).



Utilisation d'outils d'ingénierie

L’étudiant utilisera un outil de développement logiciel intégré (IDE) tel que : ECLIPSE, INTELLIJ ou VSCODE afin de développer des logiciels en JAVA.

 

Pour la réalisation des travaux de laboratoires, les étudiants pourront utiliser un ordinateur MAC ou PC.




Évaluation


Informations additionnelles :

Évaluations individuelles

Examen intra                         30 %
Examen final 30 %
Devoirs (11) 10 %
Laboratoire programmation compétitive 15 %

Évaluations considérées non individuelles

Laboratoire jeu de plateau.                     15 %

À noter:

  • Une moyenne inférieure à 60% dans les évaluations individuelles entraîne automatiquement un échec au cours. Ceci est une condition nécessaire mais non suffisante pour réussir ce cours.
  • Il y a 11 devoirs au cours de la session, les 10 meilleurs sont considérés dans la note finale
  • Il y a 6 séances de programmation compétitive au cours de la session; les 5 meilleures sont utilisées pour la note finale.
  • Il y a deux laboratoires pour un total de 30%, répartis sur plusieurs séances.  Ce ne sont pas plusieurs petits laboratoires.

Documentation permise:

  • Examen intra : Feuille de notes fournie avec l'examen.  La feuille de notes est disponible sur Moodle et sera fournie avec l'examen. Pas de calculatrice.
  • Examen Final : Aucune documentation permise. Calculatrice non programmable.



Seuil de passage pour les éléments à caractère individuel

Note minimale : 60



Dates des examens intra
Groupe(s) Date
1 16 janvier 2026
1 23 janvier 2026
1 13 février 2026
1 27 février 2026
1 20 mars 2026
1 27 mars 2026
1, 3 16 février 2026
2 10 février 2026
2 24 février 2026
2 20 janvier 2026
2 13 janvier 2026
2 24 mars 2026
2 17 mars 2026
2, 4 17 février 2026
3 23 février 2026
3 19 janvier 2026
3 9 février 2026
3 16 mars 2026
3 23 mars 2026
3 12 janvier 2026
4 25 mars 2026
4 18 mars 2026
4 21 janvier 2026
4 14 janvier 2026
4 25 février 2026
4 11 février 2026



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.5/ cycles supérieurs, article 6.5.2) se verra attribuer la note zéro, à moins que d’autres dispositions ne soient communiquées par écrit par l’enseignante ou l’enseignant dans les consignes de chaque travail à remettre ou dans le plan de cours pour l’ensemble des travaux.

Dispositions additionnelles

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.5/ cycles supérieurs, article 6.5.2) se verra attribuer la note zéro, à moins que d’autres dispositions ne soient communiquées par écrit par l’enseignante ou l’enseignant dans les consignes de chaque travail à remettre ou dans le plan de cours pour l’ensemble des travaux.




Absence à une évaluation

Afin de faire valider une absence à une évaluation en vue d’obtenir un examen de compensation, l’étudiante ou l’étudiant doit utiliser le formulaire prévu à cet effet dans son portail MonÉTS pour un examen final qui se déroule durant la période des examens finaux ou pour tout autre élément d’évaluation surveillé de 15% et plus durant la session. Si l’absence concerne un élément d’évaluation de moins de 15% durant la session, l’étudiant ou l’étudiante doit soumettre une demande par écrit à son enseignante ou enseignant.

Toute demande de validation d’absence doit se faire dans les cinq (5) jours ouvrables suivant la tenue de l’évaluation, sauf dans les cas d’une absence pour participation à une activité prévue aux règlements des études où la demande doit être soumise dans les cinq (5) jours ouvrables avant le jour de départ de l’ÉTS pour se rendre à l’activité.

Toute absence non justifiée par un motif majeur (voir articles 7.2.6.1 du RÉPC et 6.5.2 du RÉCS) 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 étudiantes et les étudiants doivent consulter le Règlement sur les infractions de nature académique (www.etsmtl.ca/a-propos/gouvernance/secretariat-general/cadre-reglementaire/reglement-sur-les-infractions-de-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 tous les membres de la communauté étudiante sont invités à consulter la page Citer, pas plagier ! (www.etsmtl.ca/Etudiants-actuels/Baccalaureat/Citer-pas-plagier).

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 la personne enseignante du cours ou la personne coordonnatrice dans le cas des stages.



Documentation obligatoire

Aucune documentation obligatoire.




Ouvrages de références

Suggérées

 

CORMEN, T., C. LEISERSON et R. RIVEST, Introduction to Algorithms. Third edition, Cambridge (MA), MIT Press, McGraw Hill, 2009.

CORMEN, T., C. LEISERSON et R. RIVEST, Introduction à l’algorithmique. 2e éd., Paris, Dunod, 2002.

BRASSARD, G. and BRATLEY, P. Fundamental of Algorithmic. Englewood Cliffs (N.J.), Prentice-Hall, 1996.




Adresse internet du site de cours et autres liens utiles

Adresse internet du site de cours et autres liens utiles

Site moodle de log320.