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 2021
GPA665 : Structures de données et algorithmes (3 crédits)


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
Programme(s) : 7485,7885
             
  Profils(s) : Tous les profils sauf Informatique  
             
    INF155    
             
Unités d'agrément
Total d'unités d'agrément : 64,8 33,3 % 66,7 %




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 acquis les techniques de base en conception et manipulation des structures de données ainsi qu'en algorithmie.

Définition des types abstraits de données pour la description et la mise en œuvre des algorithmes. Complexité et techniques d'analyse des algorithmes. Structures de données classiques (listes, files de priorité, arbres, graphes, etc.). Opérations ensemblistes élémentaires. Techniques de tri. Stratégies algorithmiques (diviser pour résoudre, programmation dynamique, algorithme glouton, recherches locales). Graphes orientés et non orientés (représentation, algorithmes de parcours). Structures de données et algorithmes pour le stockage externe. Types de fichiers (définition, supports physiques, organisation, accès).

Séances de laboratoire et travaux pratiques axés sur la résolution de problèmes classiques. Travaux réalisés avec le langage C.

Précision sur le préalable : il concerne les étudiants des profils E, M et P.




Objectifs du cours

Un ordinateur est un outil qui traite de l’information. Le traitement de l’information inclut la manière dont celle-ci est organisée dans l’ordinateur, comment elle peut être manipulée et comment elle peut être utilisée. Ce cours traitera d’une façon systématique cet aspect non négligeable de l’information.

Objectifs spécifiques

L’objectif principal du cours porte sur la définition, l’usage et la manipulation des structures de données fondamentales ainsi que leurs algorithmes associés. Les applications typiques de ces structures de données sont aussi couvertes.




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 Lundi 18:00 - 21:30 Activité de cours
Mardi 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 Patrick Larose Laboratoire patrick.larose.1@ens.etsmtl.ca
01 Geoffroi Boulanger Laboratoire geoffroi.boulanger.1@ens.etsmtl.ca



Cours

Le plan de cours prévu se veut complet et ordonnancé chronologiquement, mais certaines modifications peuvent être apportées en cours de session.

PÉRIODE ACTIVITÉS DES COURS

1 – 2.5

A :

Techniques de programmation : Les facettes de la qualité du logiciel, les types de données abstraits, programmation en langage C, la récursivité comme un outil de résolution de problème.

2.5 – 5.5

B :

Structure de données élémentaires : Tableaux, listes chaînées, piles, files, files de priorité, etc.

5.5 – 6

C :

Listes généralisées et simulation de la récursivité par utilisation de piles

8 – 9

D :

Arbres : Représentation, parcours et applications

10

E :

Algorithmes de recherche : Recherche linéaire et dichotomique, recherche dans les arbres binaires et recherche par hachage.

11

F :

Algorithmes de tri interne : Tri d’insertion, tri par bulles, tri d’épi, tri rapide. Analyse de complexité.

12

G :

Gestion de la mémoire : Allocation et libération automatique de la mémoire par les méthodes : mise à jour du nombre de référence, ramasse-miettes, chaînage double des blocs par descripteurs.




Laboratoires et travaux pratiques
PÉRIODE ACTIVITÉS DES LABORATOIRES

1

– Première semaine – aucune séance de laboratoire –

2

Début du projet 1

3

Poursuite du projet 1

4

Poursuite du projet 1

5

Poursuite du projet 1

6

Remise du projet 1 et début du projet 2

7

Poursuite du projet 2

8

Poursuite du projet 2

9

Poursuite du projet 2

10

Remise du projet 2 et début du projet 3

11

Poursuite du projet 3

12

Poursuite du projet 3

13

Poursuite du projet 3




Utilisation d'outils d'ingénierie
  • Ordinateur personnel
  • Environnement de développement Visual Studio pour le développement en langage C

 




Évaluation
ACTIVITÉ % DATE ET DURÉE
Mini évaluation 1 2.5 Semaine 3
Mini évaluation 2 2.5 Semaine 6
Mini évaluation 3 2.5 Semaine 8
Mini évaluation 4 2.5 Semaine 10
Laboratoire 1 - Structures dynamiques unitaires 20 Semaine 2 (4 périodes)
Laboratoire 2 - Structures dynamiques linéaires 20 Semaine 6 (4 périodes)
Laboratoire 3 - Structures dynamiques non linéaires 20 Semaine 10 (4 périodes)
Examen final 30 Semaine des examens finaux

 

NOTE CONCERNANT LES TRAVAUX D’ÉQUIPE. Un maximum de 10% du total des notes des divers travaux sera attribué à la présentation et à la qualité du français.  Chaque rapport devra être présenté selon les normes reconnues (voir guide de rédaction de projet de synthèse de l’ÉTS).  Il devra comprendre une introduction, une présentation du problème, l’exposition des méthodes de solution, les résultats et une conclusion.  L’utilisation des outils informatiques pour la rédaction (traitement de textes) ainsi que pour la présentation des données (tabulateurs, graphiques, dessins) est requise.




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
  • DIVAY, M., Algorithmes et structures de données, Dunod, 1999.
  • JAMSA, K. et L. KLANDER, C/C ++ La bible du programmeur  - 1500 astuces pour toutes les situations, Reynald Goulet, 1999.
  • STANDISH, T. A., Data Structure, Algorithms and Software Principles in C, Addison-Wesley Publishing Company Inc., 1995.
  • PRESS, W.H. et al., Numerical Recipes in C, Cambridge University Press, 1992.
  • COLLINS, W.J., Data Structures: An Object-Oriented Approach, Addison-Wesley Publishing Company, 1992.
  • HELMAN,VEROFF et CARRANO, Intermediate Problem Solving and Data Structures: Walls and Mirrors, 2e éd., The Benjamin Cummings Publishing Company Inc., 1991.
  • SCHILDT H., C: The Complete Reference, 2e éd., Osborne McGraw-Hill, 1990.
  • GROFF, J.F. et E. MOTTIER, Le langage C (ANS1), 2e éd., Masson, 1990.
  • LEWIS, H.R. et L. DENENBERG, Data Structure and Their Algorithms, Harper-Collins Publishers, 1991.
  • LEENDERT et AMERAALL, Programs and Data Structures in C,  John Wiley and Sons, 1989.



Adresse internet du site de cours et autres liens utiles

https://cours.etsmtl.ca/gpa665/




Autres informations

Ne s'applique pas