Logo ÉTS
Session
Cours
Responsable(s) Marc Paquet, Mohamed Cheriet

Se connecter
 

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

Responsable(s) de cours : Marc Paquet
Mohamed Cheriet


PLAN DE COURS

Hiver 2025
GPA675 : Structures de données et algorithmes (4 crédits)





Préalables
Programme(s) : 6557,7485,7885
             
  Profils(s) : Tous profils  
             
    GPA434    
             
Unités d'agrément




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



Objectifs du cours

Puisque le traitement de l'information est la seule tâche réalisée par un ordinateur, l'organisation et la manipulation de cette dernière reste au centre de tous développement informatique.

Ce cours traitera d'une façon systématique cet aspect critique et essentiel de l'ingénierie des systèmes informationnels.


Objectifs spécifiques 


Les structures de données et leurs algorithmes sont couverts dans le cours selon ces quatre objectifs pédagogiques :
 - analyse de complexité
 - définition, caractérisation et représentation
 - stratégies de réalisation, implémentation et déverminage
 - utilisation concrète via le développement d'applications pertinentes et stimulantes
 - identification des meilleurs structures de données et algorithmes considérant les compromis optimaux


 



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.



Utilisation d’appareils électroniques

Ne s'applique pas.



Horaire
Groupe Jour Heure Activité
01 Mercredi 18:00 - 21:30 Activité de cours
Jeudi 18:00 - 21:00 Laboratoire



Coordonnées du personnel enseignant le cours
Groupe Nom Activité Courriel Local Disponibilité
01 Jean-Christophe Demers Activité de cours cc-jean-christophe.demers@etsmtl.ca A-3736
01 Laboratoire



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
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).



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 : https://www.etsmtl.ca/programmes-et-formations/horaire-des-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.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 l’enseignante ou l’enseignant du cours.



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.