Version PDF

Programme(s) : 7485,7885

Profils(s) : Tous profils

Afficher les préalables et les unités d'agrément

Afficher les qualités de l'ingénieur

École de technologie supérieure

Responsable(s) de cours :

Mohamed Cheriet

PLAN DE COURS

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

Préalables

Unités d'agrément
Total d'unités d'agrément : 64,8

Qualités de l'ingénieur

Q10

Q11

Q12

Qualité visée dans ce cours

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 ou l'étudiante 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	Lundi	18:00 - 21:00	Laboratoire
	Mercredi	18:00 - 21:30	Activité de cours

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	François Côté-Raiche	Laboratoire	francois.cote-raiche.1@ens.etsmtl.ca
01	Patrick Quevillon	Laboratoire	patrick.quevillon.1@ens.etsmtl.ca

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

Infractions de nature académique
À 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/Etudes/citer-pas-plagier). Les clauses du règlement sur les infractions de nature académique de l’ÉTS (« Règlement ») 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 qui constituent des infractions de nature académique au sens du Règlement ainsi que prendre connaissance des sanctions prévues à cet effet.

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’enseignant(e) 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.