Logo ÉTS
Session
Cours
Responsable(s) Patrick Cardinal

Se connecter
 

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

Responsable(s) de cours : Patrick Cardinal


PLAN DE COURS

Été 2023
LOG320 : Structures de données et algorithmes (4 crédits)





Préalables
Programme(s) : 7065,7070,7084,7086,7365,7610
             
  Profils(s) : Tous profils  
             
    MAT210 ET LOG121    
             
Unités d'agrément
Total d'unités d'agrément : 64,8 50,0 % 50,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
Acquérir une connaissance spécifique au génie logiciel des structures de données et des algorithmes. Comprendre et utiliser l'analyse asymptotique afin de choisir judicieusement les structures de données appropriées et le type d'algorithme optimal pour résoudre efficacement un problème tout en respectant les contraintes imposées et les ressources disponibles.

Au terme de ce cours, l'étudiante ou l'étudiant sera en mesure de choisir parmi une multitude de structures de données de base (tableau, file, pile ou liste) ou plus avancées (structures en arbre, graphes, tables de hachage) afin de résoudre différents problèmes plus ou moins complexes. Il sera aussi en mesure de les combiner et de les adapter afin de faire face à différentes situations.

L’étudiante ou l'étudiant sera aussi en mesure de choisir le type d’algorithmes et d’analyser ses performances globales pour différents problèmes de base qui impliquent, par exemple, la recherche dans des graphes, l’optimisation combinatoire ou la recherche dans des chaînes de caractères.



Objectifs du cours

À la fin de ce cours, l’étudiant(e) aura assimilé les notions suivantes :

  • structures de données élémentaires : liste, pile, queue, tableau, arbre, graphe, etc.;
  • techniques d’analyse de performance des algorithmes;
  • techniques de base de conception d’algorithmes : récursivité, algorithmes gloutons, programmation dynamique, etc.;
  • algorithmes de recherche et d’extraction de l’information;
  • algorithmes de tri classiques.

À la fin du cours, l’étudiant(e) sera capable de :

  • analyser la performance des algorithmes pour faire un choix réfléchi entre divers algorithmes;
  • choisir des structures de données judicieuses et implanter des algorithmes de manière à obtenir de bonnes performances;
  • concevoir des algorithmes simples en utilisant les techniques classiques de conception;
  • analyser les résultats et faire des améliorations algorithmiques si possible et nécessaires.



Stratégies pédagogiques

- Un cours magistral par semaine (3 heures). Des exemples seront faits en classe pour permettre aux étudiants(es) d’assimiler les concepts théoriques.

- Une séance de travaux pratiques par semaine (1 heure approximativement*).

- Une séance de laboratoire par semaine (2 heures approximativement*).

Le temps pour la séance de travaux pratique peut varier (plus ou moins de temps) d'une semaine à l'autre dépendant de la théorie et des exercices faits en TP.  Ces heures sont fournies à titre indicatif seulement, mais la période de laboratoire au complet (séance de TP et labo) sera de 3 heures totales.



Utilisation d’appareils électroniques

Il est interdit de capter le cours ou des portions du cours (enregistrement vidéo, enregistrement audio, photographie) en salle de classe ou en laboratoire à moins d'avoir obtenue au préalable la permission de l'enseignant.



Horaire
Groupe Jour Heure Activité
01 Mercredi 13:30 - 17:00 Activité de cours
Jeudi 08:30 - 11:30 Laboratoire
02 Lundi 18:00 - 21:00 Laboratoire
Mercredi 18:00 - 21:30 Activité de cours



Coordonnées du personnel enseignant le cours
Groupe Nom Activité Courriel Local Disponibilité
01 Patrick Cardinal Activité de cours Patrick.Cardinal@etsmtl.ca A-4486
01 Alexandrine Fortier Laboratoire alexandrine.fortier.1@ens.etsmtl.ca
02 Francis Cardinal Activité de cours cc-Francis.CARDINAL@etsmtl.ca A-4526
02 Francis Cardinal Laboratoire cc-Francis.CARDINAL@etsmtl.ca A-4526
02 Vincent Séguin Laboratoire vincent.seguin.1@ens.etsmtl.ca



Cours

Introduction, calcul d’ordre asymptotique et analyse des algorithmes (5 heures[1])

  1. Introduction à l’algorithmique.
  2. Algorithmes et programmes.
  3. Efficacité des algorithmes.
  4. Calcul d’ordre des algorithmes et notations asymptotiques : O, Theta, Omega
  5. Estimation de l’ordre du temps de calcul.
  6. Baromètres.
  7. Estimation de l’ordre de la mémoire de travail.

Algorithmes récursifs (5 heures)

  1. Règles de conception de fonctions récursives.
  2. Optimisation de fonctions récursives.
  3. Preuves de convergence.
  4. Équations de récurrence.
  5. Analyse des algorithmes récursifs.
  6. Méthode générale.

Structures de données (11 heures)

  1. Tableaux.
  2. Listes.
  3. Piles.
  4. Queues.
  5. Arbres binaires de recherche (arbres k-d).
  6. Arbres rouge-noir.
  7. Arbres AVL.
  8. Graphes.
  9. Tables de hachage.

 Recherche dans les graphes (4 heures)

  1. Arbres de jeux : algorithme MinMax et élagage alpha/bêta.
  2. Autres optimisations des arbres de jeux.
  3. Algorithme de Dijkstra
  4. Recherche du meilleur en premier (« best-first search »)
  5. Algorithmes A*

  Optimisation combinatoire (7 heures)

  1. Théorie des classes.
  2. Programmation dynamique.
  3. Séparation et évaluation.
  4. Algorithmes « retour en arrière ».
  5. Algorithmes gloutons.
  6. Algorithmes non-déterministes[2]
  7. Programmation linéaire[2]

Recherche d’une sous-chaîne de caractère dans un texte (3.5 heures)

  1. Algorithme naïf.
  2. Algorithme Rabin-Karp.
  3. Algorithme Boyer-Moore.
  4. Algorithme Knuth-Morris-Pratt.
  5. Algorithmes utilisant une notion de distance.

Sujets spéciaux (3.5 heures)

NOTE : Tous les cours sont d'une durée de 3 heures et 30 minutes par semaine (incluant une pause de 30 minutes).

 [1]    Ces heures sont des heures approximatives d’enseignement pour chaque sujet et incluent le temps alloué à l’examen intra-trimestriel.

 [2]    Ces sujets pourraient être remplacés par d'autres sujets en cours de session.



Laboratoires et travaux pratiques

Des laboratoires seront proposés au cours du trimestre afin de permettre aux étudiants (es) d’approfondir leurs connaissances et d’expérimenter les algorithmes montrés en classe.

Programmation compétitive (15 points) (6 séances)

Description : Simulation de programmation compétitive avec des problèmes couvrant différents sujets du cours. Il y aura 6 séances de de laboratoire qui seront dédiées à la programmation compétitive. 

Sujets couverts : Analyse asymptotique, structures de données, programmation dynamique, algorithmes glouton, recherche dans les chaines de caractères, conception, algorithmique.

Jeu de plateau (15 points) (6 séances)

Description : Création d’un joueur « CPU » pour un jeu de plateau.

Sujets couverts : Algorithmes min - max et alpha-beta, tables de hachage, heuristiques.

Notes importantes:

Équipe

Les laboratoires se font en équipe de 2 ou de 3.

Pour la programmation compétitive

La présence au laboratoire est obligatoire pour la programmation compétitive.

L’étudiant(e) absent(e) se verra attribuer la note zéro (0).

Pour le jeu de plateau

Lors de la correction du dernier laboratoire (le tournoi du jeu), tous les membres de l’équipe doivent être présents.

L’étudiant(e) absent(e) se verra attribuer la note zéro (0).

 



Utilisation d'outils d'ingénierie

L’étudiant utilisera un outil de développement logiciel intégré (IDE) tel que : ECLIPSE ou INTELLIJ afin de développer des logiciels en JAVA.

 

Pour la réalisation des travaux de laboratoires, les étudiants pourront utiliser un ordinateur MAC ou PC.


Évaluation
Laboratoires 30 %
Devoirs (10) 10 %
Examen intra 30 %
Examen final 30 %

 

À noter qu’une moyenne inférieure à 55% dans les évaluations individuelles (examens intra et final) entraîne automatiquement un échec au cours. Ceci est une condition nécessaire mais non suffisante pour réussir ce cours.

 



Double seuil
Note minimale : 55



Dates des examens intra
Groupe(s) Date
1, 2 21 juin 2023



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

Dispositions additionnelles

Les travaux remis en retard ne seront pas corrigés et l’étudiant(e) se verra attribué(e) la note zéro (0).



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



Ouvrages de références

Suggérées

 

CORMEN, T., C. LEISERSON et R. RIVEST, Introduction to Algorithms. Third edition, Cambridge (MA), MIT Press, McGraw Hill, 2009.

CORMEN, T., C. LEISERSON et R. RIVEST, Introduction à l’algorithmique. 2e éd., Paris, Dunod, 2002.

BRASSARD, G. and BRATLEY, P. Fundamental of Algorithmic. Englewood Cliffs (N.J.), Prentice-Hall, 1996.



Adresse internet du site de cours et autres liens utiles

Site moodle de log320.