Logo ÉTS
Session
Cours
Responsable(s) Mohamed Cheriet

Se connecter
 

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

Responsable(s) de cours : Mohamed Cheriet


PLAN DE COURS

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


Modalités de la session d’hiver 2022


Pour assurer la tenue de la session d’hiver 2022, les modalités suivantes seront appliquées :


Les activités d’enseignement de la session d’hiver 2022 comprendront des activités en présence et à distance, lesquelles seront ajustées en fonction de l’évolution de la situation socio-sanitaire.


Pour les cours (ou séances de cours) donnés à distance, l’étudiant ou l'étudiante doit avoir accès à un ordinateur, un micro, une caméra et un accès à internet, idéalement de 10Mb/s ou plus. Il ou elle doit ouvrir sa caméra et/ou son micro lorsque requis, notamment pour des fins d’identification ou d’évaluation.


Les cours (ou séances de cours) donnés à distance pourraient être enregistrés afin de les rendre disponibles aux personnes inscrites au cours.


La notation des cours sera la notation régulière prévue aux règlements des études de l’ÉTS.


Les examens (intra, finaux) se feront en présence, si la situation socio-sanitaire le permet.


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 2022, 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, si requis, qu'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 toute ou pour une partie de la session d’hiver 2022. Ainsi, si les examens (intra, finaux) 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.


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 à la session d'hiver 2022, vous acceptez les modalités particulières de la session d’hiver 2022.


Nous vous rappelons que vous avez jusqu’au 18 janvier 2022 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 1er février 2022 pour vous désinscrire de vos cours et être remboursé.




Préalables
Programme(s) : 7485,7885
             
  Profils(s) : Tous profils  
             
    GPA434    
             
Unités d'agrément
Total d'unités d'agrément : 64,8 33,0 % 67,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

Ce cours sera nouvellement offert à une session ultérieure.

Au terme de ce cours, 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 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 à parfaire ses compétences globales en informatique.




Utilisation d’appareils électroniques

Ne s'applique pas.




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



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



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.
 - UML est utilisé dans les échanges enseignants-étudiants et étudiants-étudiants.
 - 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 : 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.



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



Plagiat et fraude
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




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/