Logo ÉTS
Session
Cours
Responsable(s) Kim Khoa Nguyen, Catherine Laporte

Se connecter
 

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

Responsable(s) de cours : Kim Khoa Nguyen, Catherine Laporte


PLAN DE COURS

Automne 2021
ELE440 : Algorithmes (4 crédits)





Préalables
Programme(s) : 7483, 7883
             
  Profils(s) : Électricité, Informatique, Technologie de systemes ordines  
             
    ELE116    
             
Programme(s) : 7694
             
  Profils(s) : Tous profils  
             
    ELE216    
             
Programme(s) : 7483, 7883
             
  Profils(s) : Électricité, Technologie de systemes ordines  
             
    INF147    
             
Programme(s) : 7483, 7883
             
  Profils(s) : Électricité, Technologie de systemes ordines  
             
    INF147    
             
Unités d'agrément
Total d'unités d'agrément : 64,8 25,0 % 75,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

Étudier les caractéristiques des algorithmes dans le but d’obtenir une réalisation efficace sur ordinateur.

Présentation des algorithmes de base comme les algorithmes voraces, des techniques «diviser pour régner», de la programmation dynamique et d’exploration des graphes. Notion de complexité d'algorithme. Techniques de programmation. Récursivité, retour-arrière, allocation dynamique, recherche de solutions. Structures de données : listes, piles, files, arborescences. Algorithmes de tri. Techniques de recherche. Algorithmes élémentaires de manipulation d'arbres. Différents algorithmes sont développés pour le même problème et comparés à partir de moyens analytiques et de simulations.

Séances de laboratoire visant à développer des logiciels appliquant les principes mentionnés précédemment selon des techniques reconnues de génie logiciel.

 



Objectifs du cours

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

  • structures de données élémentaires : liste, pile, file, 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écessaire.



Stratégies pédagogiques

Un (1) cours magistral par semaine (3 heures). Des exemples seront faits en classe pour permettre aux étudiant(e)s d’assimiler les concepts théoriques.

 

Une (1) séance de laboratoire par semaine (3 heures).  Au laboratoire, les étudiants travaillent en équipe de deux ou trois.  Les laboratoires contiennent tous une composante majeure d’implémentation d’algorithmes ; l’étudiant doit donc maîtriser le langage de programmation C. 

 

Des séances de laboratoire pourraient être interverties avec des séances de cours afin de mieux arrimer le contenu des laboratoires à la progression des notions vues en cours.




Utilisation d’appareils électroniques

Le cours étant donné à distance, l'étudiant aura besoin d'un ordinateur avec une connexion Internet et, idéalement, d'une caméra et d'un microphone.  Une caméra pourrait être obligatoire pour l'examen final.

L’utilisation d’appareils électroniques pour l’enregistrement des cours ou des laboratoires doit faire l’objet d’une approbation par le professeur.  L’approbation ne sera donnée que pour des motifs majeurs.




Horaire
Groupe Jour Heure Activité
01 Mardi 08:30 - 11:30 Laboratoire
Jeudi 13:30 - 17:00 Activité de cours



Coordonnées de l’enseignant
Groupe Nom Activité Courriel Local Disponibilité
01 Catherine Laporte Activité de cours Catherine.Laporte@etsmtl.ca A-2464
01 Simon Pichette Laboratoire simon.pichette@etsmtl.ca A-2608



Cours

 

Date Contenus traités dans le cours Heures
  Introduction
  • Introduction à l’algorithmique
  • Algorithmes et programmes
  • Efficacité des algorithmes
3 heures
  Analyse des algorithmes 
  • Calcul asymptotique
  • Baromètres
  • Estimation de l’ordre asymptotique du temps de calcul
  • Estimation de l’ordre asymptotique de la mémoire de travail
  • Notion de temps de calcul amorti
3 heures
  Algorithmes récursifs
  • Règles de conception d’algorithmes récursifs
  • Analyse des algorithmes récursifs et équations de récurrence
  • Preuve de convergence
  • Optimisation des fonctions récursives
3 heures
  Structures de données, opérations élémentaires et efficacité
  • Tableaux
  • Listes
  • Piles et files
  • Arbres
  • Graphes
3 heures  
  Recherche par valeur 
  • Recherche séquentielle
  • Recherche aléatoire
  • Recherche binaire
  • Hachage
  • Arbres de recherche
3 heures
  Algorithmes de tri  
  • Insertion
  • Sélection
  • Quicksort
  • Fusion
  • Heapsort
  • Pigeonnier
4,5 heures
 

Techniques de résolution de problèmes d'optimisation 

  • Algorithmes gloutons 
  • Programmation dynamique
  • Exploration de graphes implicites (backtracking, branch-and-bound)
  • Heuristiques et méta-heuristiques (recuit simulé, algorithmes génétiques)
12 heures
  Problèmes d'optimisation sur des graphes
  • Recherche en largeur et en profondeur
  • Arbres minimaux couvrants
  • Problèmes de plus court chemin
  • Coloration de graphes
4,5 heures
  Algorithmes non-déterministes 
  • Déterminisme, approximation et certitude
  • Algorithmes probabilistes numériques
  • Algorithmes de type Monte Carlo
  • Algorithmes de type Las Vegas
3 heures
  Total 39

 

Note :   Tous les cours sont d'une durée de 3 heures 30 minutes par semaine.  Les sujets seront peut-être abordés dans un ordre différent de  celui indiqué dans le plan de cours.  




Laboratoires et travaux pratiques

L'étudiant devra maîtriser le langage de programmation C pour la réalisation des laboratoires.

Date Description Heures
 
  • Analyse asymptotique et algorithmes de tri.
  • Implémentation d’algorithmes classiques de tri de données.
  • Mesure de performance par analyse asymptotique théorique et expérimentale.
9 heures  
 
  • Structures de données et efficacité
  • Implémentation et analyse d'algorithmes sur des graphes
  • Arbres couvrants minimaux
12 heures
 
  • Algorithmes de recherche par valeur 
  • Algorithmes d’exploration de graphes en largeur, en profondeur, etc.
  • Notions d’algorithme optimal et sous optimal en explorant les problèmes du plus court chemin dans un graphe.
15 heures
  Total 36



Utilisation d'outils d'ingénierie

Dans le cadre des laboratoires, les étudiants seront appelés à utiliser le langage C, le système d'exploitation Linux et l'environnement de développement Eclipse.




Évaluation

 

Activité Description %
  Laboratoires 40 %
  Examen de mi-session 30 %
  Examen final 30 %



Dates des examens intra
Groupe(s) Date
1 14 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

Sauf motif majeur (maladie certifiée par un billet de médecin, décès d’un parent immédiat ou autre), un retard dans la remise d’un rapport de laboratoire ou du projet de recherche entraînera une pénalité de 10% de la valeur du travail par jour de retard, incluant les fins de semaine, les jours fériés et autres congés.




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
  • CORMEN, T., LEISERSON, C., RIVEST, R., Introduction à l’algorithmique, 3e édition, Paris, Dunod, 2010

ou

  • CORMEN, T., LEISERSON, C., RIVEST, R., Introduction to Algorithms, 3rd Ed., Cambridge, MA, MIT Press, McGraw Hill, 2009.



Ouvrages de références
  • BRASSARD, G., BRATLEY, P., Fundamental of Algorithmics, Englewood Cliffs, NJ, Prentice Hall, 1996.
  • KLEINBERG, J., TARDOS, É., Algorithm Design, Addison-Wesley, 2006.



Adresse internet du site de cours et autres liens utiles

 

Site du cours: https://ena.etsmtl.ca/