|
École de technologie supérieure
|
Responsable(s) de cours :
|
Mohamed Cheriet
|
PLAN DE COURS
Hiver 2026
GPA675 : Structures de données et algorithmes (4 crédits)
Préalables
Pour tous profils : GPA434
Description du cours
Au terme de ce cours, l’étudiante ou l’étudiant aura acquis les notions et techniques de base en conception, analyse, manipulation et création des structures de données et d’algorithmes.
Définition de types abstraits et
d’algorithmes génériques. Analyse de
complexité. Structures de données
classiques : listes, files, piles, arbres,
tables de hachage, graphes, etc.
Opérations fondamentales sur ces
structures de données.
Stratégies algorithmiques : dichotomie,
partition, recherche, parcours,
programmation dynamique, algorithme
glouton, recherches locales, etc.
Techniques de tri. Listes chaînées simple
et double. Arbres binaires et n-aires,
Graphes orientés et non orientés
(représentation, algorithmes de parcours).
Stratégies d’implémentation. Techniques
de représentation.
Les séances de laboratoire sont axées sur
la résolution de problèmes classiques. Les
travaux sont réalisés avec le langage C++
selon le paradigme orienté-objet.
Stratégies pédagogiques
39 heures de cours magistral (enseignement théorique)
36 heures de laboratoire (projet de session)
3 heures de travail personnel (en moyenne) par semaine
À chaque semaine, trois heures de cours magistraux et trois heures de laboratoire sont données. Les cours présentent les divers concepts théoriques alors que les laboratoires donnent la chance aux étudiants et étudiantes d’approfondir leurs connaissances en solutionnant des problèmes concrets. Les différents laboratoires abordent, par le biais de projets stimulants, les principaux sujets du cours tout en amenant l’étudiant ou l'étudiante à parfaire ses compétences globales en informatique.
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 | 21,38 UA | 32,99 % | |
| Conception Ingénierie | 43,42 UA | 67,01 % | |
Utilisation d’appareils électroniques
Ne s'applique pas.
Horaire
| Groupe | Jour | Heure | Activité |
| 01 | Lundi | 18:00 - 21:30 | Activité de cours |
| Mercredi | 18:00 - 21:00 | Laboratoire |
Coordonnées du personnel enseignant le cours
Cours
| Module |
Semaines |
Sujets couverts |
| 1 |
1-2 |
- Introduction aux structures de données et algorithmes
- Types de données abstraits et paradigme orienté objets
- Opérations fondamentales
- Analyse de complexité
- Techniques de programmation C++
- Retours importants :
- compilation et liaison
- orienté objets, construction/destruction, opérateurs
- pointeurs et références
- tableaux, structures et unions
- Modèle et représentation de la mémoire
- Allocation et gestion de la mémoire
- Retour UML
|
| 2 |
3 |
- Listes généralisées
- Implémentation
- mémoire fixe et redimensionnable
- organisation contiguë
- Tableaux
|
| 3 |
4-5 |
- Itérateurs
- Implémentation : organisation chaînée par enregistrement
- Listes chaînées : simple, double, double entrées, circulaire
- Listes spécialisées : pile, file, file de priorité
- Techniques de programmation C++
- stratégies de gestion d'erreurs
- template
|
| 4 |
9 |
- Implémentation : organisation par clé de localisation
- Hachage
- Table de hachage
- fonctions de hachage
- techniques de gestion des collisions
- table fixe et dynamique
|
| 5 |
6-8 |
- Récursivité
- Arbres généralisés
- binaires : non contraint, arb, avl, arn
- en épi
- d'expression
- n-aire
|
| 6 |
10 |
- Triage
- Algorithmiques génériques
|
| 7 |
11 |
- Graphes généralisés
- non dirigés, dirigés
- parcours
- chemin le plus court
- arbre couvrant minimum
|
| 8 |
12-13 |
- Discussions diverses
- implémentation : organisation chaînée par bloc
- allocation et libération automatique de la mémoire :
- mise à jour du nombre de référence
- pointeurs intelligents
- ramasse-miettes
- pool d'objets
- problèmes complexes et heuristiques
- résolution de problèmes divers
- parallélisme
- autres langages de programmation
|
Laboratoires et travaux pratiques
Déroulement des laboratoires
| Activités |
Semaines |
Modules couverts |
Remise |
| Laboratoire 1 |
2-5 |
1-2 |
avant laboratoire 2 |
| Laboratoire 2 |
6-9 |
3-4 |
avant laboratoire 3 |
| Laboratoire 3 |
10-13 |
5-6 |
avant examen final |
Notes :
- Tous les laboratoires doivent être réalisé en équipe d'au moins 2 étudiants ou étudiantes.
- UML est utilisé dans les échanges enseignant(e)s-étudiant(e)s et étudiant(e)s-étudiant(e)s.
- Les travaux doivent être réalisé en langage C++.
- La blibliothèque Qt est utilisée.
- Les développements sont réalisés avec Visual Studio sous Windows.
Utilisation d'outils d'ingénierie
Outils utilisés
- Ordinateur personnel
- UML
- Langage C++ et Qt
- Visual Studio
Évaluation
Informations additionnelles :
| Activité |
Pondération |
Semaines |
|
Quiz 1
Quiz 2
Quiz 3
Quiz 4
|
2.5%
2.5%
2.5%
2.5% |
4
7
10
13 |
Laboratoire 1
Laboratoire 2
Laboratoire 3 |
20.0%
20.0%
20.0%
|
2-5
6-9
10-13 |
| Examen final |
30.0% |
des examens finaux |
Notes : Une moyenne de 50% est exigée pour l'examen final et pour les travaux individuels afin de réussir le cours (double seuil).
Seuil de passage pour les éléments à caractère individuel
Note minimale : 50
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.
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
Ouvrages de références
- Cormen, T. H., Introduction to Algorithms (third edition, 2009) (fourth edition, 2022)
- Drozdek, A., Data Structures and Algorithms in C++ (2012)
- Goodrich, M. T., Tamassia, R., Mount, D. M., Data Structures and Algorithms in C++ (2011)
Adresse internet du site de cours et autres liens utiles
https://ena.etsmtl.ca/
Autres informations
Ne s'applique pas.