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

À la fin de ce cours, 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’é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 Lundi 13:30 - 16:30 Laboratoire (Groupe A)
Lundi 13:30 - 16:30 Laboratoire (Groupe B)
Mardi 13:30 - 17:00 Activité de cours
02 Lundi 18:00 - 21:30 Activité de cours
Mardi 18:00 - 21:00 Laboratoire
03 Lundi 13:30 - 17:00 Activité de cours
Mardi 13:30 - 16:30 Laboratoire (Groupe A)
Mardi 13:30 - 16:30 Laboratoire (Groupe B)
04 Lundi 18:00 - 21:00 Laboratoire
Mardi 18:00 - 21:30 Activité de cours



Coordonnées de l’enseignant
Groupe Nom Activité Courriel Local Disponibilité
01 Pierre Dumouchel Activité de cours Pierre.Dumouchel@etsmtl.ca
01 Philippe Charbonneau Laboratoire (Groupe A) philippe.charbonneau.2@ens.etsmtl.ca
01 Francis Cardinal Laboratoire (Groupe B) cc-Francis.Cardinal@etsmtl.ca A-4526
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 Hung Tam Nguyen Laboratoire viet_cheater@hotmail.com
04 Pierre Dumouchel Activité de cours Pierre.Dumouchel@etsmtl.ca
04 Philippe Charbonneau Laboratoire philippe.charbonneau.2@ens.etsmtl.ca
04 Antoine Grenier Laboratoire antoine.grenier3@gmail.com



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.

Recherche d'anagrammes (5 points) (2 séances)

Description : Conception d'un logiciel qui recherche dans un dictionnaire les anagrammes de mots.

Sujets couverts : Analyse asymptotique, conception, algorithmique.

Algorithmes de compression (5 points) (2 séances)

Description : Conception d'un logiciel de compression de données qui utilise le l'algorithme de Huffman.

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

 

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,2 et 3

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 4

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, 2, 4 19 octobre 2021



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



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