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

Automne 2020
LOG320 : Structures de données et algorithmes (4 crédits)


Modalités de la session d’automne 2020
Pour assurer la tenue de la session d’automne 2020, les modalités suivantes seront appliquées :


La plupart des cours de la session d'automne seront donnés à distance. Les autres seront donnés en présence. Cette information vous a déjà été communiquée.

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.

Les cours à distance pourraient être enregistrés, à la discrétion de l’ÉTS. Le cas échéant, les enregistrements de cours pourraient notamment être rendus accessibles aux étudiants par le biais notamment du portail de l’ÉTS.

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

Pour les cours à distance, les examens (intra, finaux) se feront normalement à 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 à envisager la possibilité d’une deuxième vague de la pandémie de COVID-19, laquelle pourrait entraîner, après le début de la session d’automne 2020, 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 la dispense en ligne de toutes les activités d’enseignement et d’évaluation pour la durée restante de la session d’automne 2020.

Des exigences additionnelles pourraient être spécifiées par l’ÉTS ou votre département, suivant les particularités propres à votre programme.

Si vous ne consentez pas aux modalités décrites précédemment, vous devez vous désinscrire de vos cours avant le 13 septembre et vous pourrez être remboursé.

Pour les nouveaux étudiants inscrits au programme de baccalauréat uniquement, vous devez vous désinscrire avant le 25 septembre et vous pourrez être remboursé.

En demeurant inscrit, vous acceptez les modalités particulières de la session d'automne 2020.




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 Mardi 08:30 - 12:00 Activité de cours
Mercredi 08:30 - 11:30 Laboratoire
02 Mercredi 18:00 - 21:30 Activité de cours
Jeudi 18:00 - 21:00 Laboratoire
03 Mercredi 18:00 - 21:00 Laboratoire
Jeudi 18:00 - 21:30 Activité de cours
04 Mardi 08:30 - 11:30 Laboratoire
Mercredi 08:30 - 12:00 Activité de cours



Coordonnées de l’enseignant
Groupe Nom Activité Courriel Local Disponibilité
01 Pierre Dumouchel Activité de cours Pierre.Dumouchel@etsmtl.ca A-4450
01 Francis Cardinal Laboratoire cc-Francis.CARDINAL@etsmtl.ca A-4526
01 Philippe Charbonneau Laboratoire philippe.charbonneau.2@ens.etsmtl.ca
02 Pierre Dumouchel Activité de cours Pierre.Dumouchel@etsmtl.ca A-4450
02 Guillaume Baril Laboratoire cc-Guillaume.Baril@etsmtl.ca A-4526
03 Pierre Dumouchel Activité de cours Pierre.Dumouchel@etsmtl.ca A-4450
03 Guillaume Baril Laboratoire cc-Guillaume.Baril@etsmtl.ca A-4526



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.
  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
  7. Programmation linéaire

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.



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.

 

Algorithmes de compression (10 points) (4 séances)

Description : Conception d'un logiciel de compression de données qui utilise les algorithmes LZW et Huffman.

Sujets couverts : Algorithmes de compression, analyse asymptotique, conception, algorithmique.

 

Recherche de mots dans une grille (style mot mystère) (5 points) (2 séances)

Description :    Le but de ce laboratoire est de concevoir un programme qui cherche dans une grille de dimension NxN tous les mots d'un dictionnaire fourni en paramètre. Seul certains mots du dictionnaire sont présents dans la grille. 

Sujets couverts : Implémentation d'algorithmes, analyse d’algorithme, structure de données Trie

 

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:

 

Pour les laboratoires 1, et 2

Il est impératif de respecter TOUTES les directives relatives à la remise du .jar (et aux sorties textes de l'exécution de ce dernier) pour fins d'évaluation du fonctionnement par script.  Ces directives sont spécifiées dans chacun des énoncés.

Toute entorse aux directives peut entraîner la note de zéro (0) pour la partie fonctionnement.

 

Pour le laboratoire 3

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 à 50% 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 : 50



Dates des examens intra
Groupe(s) Date
1 20 octobre 2020
2 14 octobre 2020
3 22 octobre 2020



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.

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.