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

Se connecter
 

École de technologie supérieure
Département de génie électrique
Responsable(s) de cours : Catherine Laporte, Kim Khoa Nguyen


PLAN DE COURS

Automne 2018
ELE440 : Algorithmes (4 crédits)



Préalables
Programme(s) : 7483
             
  Profils(s) : Électricité, Informatique, Technologie de systemes ordines  
             
    ELE116    
             
Programme(s) : 7694
             
  Profils(s) : Tous profils  
             
    ELE216    
             
Programme(s) : 7483
             
  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.

Précision sur les préalables : un préalable seulement est requis pour cours le ELE440, soit ELE116 OU INF145.



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

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 Vendredi 08:30 - 11:30 Laboratoire
Vendredi 13:30 - 17:00 Activité de cours



Coordonnées de l’enseignant
Groupe Nom Activité Courriel Local Disponibilité
01 Kim Khoa Nguyen Activité de cours Kim-Khoa.Nguyen@etsmtl.ca A-2632



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
3 heures
  Techniques de conception d’algorithmes 
  • Algorithmes Diviser-pour-conquérir
  • Algorithmes gloutons (Greedy)
  • Programmation dynamique
6 heures
  Exploration de graphes
  • Recherche en largeur et en profondeur
  • Problèmes de plus court chemin
4,5 heures
  Heuristiques 
  • Classification des algorithmes
  • Techniques de conception d’algorithmes heuristiques
  • Coloration de graphes
  • Branch-and-bound
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
  Programmation linéaire et méthode du simplexe
  • Modèle linéaire
  • Résolution de problème linéaire
  • Résolution avec les solveurs
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.  Les durées indiquées incluent l’examen de mi-session.




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.
12 heures  
 
  • Algorithmes de recherche, choix heuristique et calcul de temps amorti 
  • Implémentation d’algorithmes classiques de recherche.
  • Optimisation des recherches par heuristiques basées sur le calcul du temps amorti.
12 heures
 
  • Exploration de graphes
  • Implémentation d’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.
12 heures
  Total 36



Utilisation d'outils d'ingénierie

Dans le cadre des laboratoires, les étudiants seront appelés à utiliser des langages de programmation et des environnements de développement logiciel.




Évaluation

 

Activité Description % Date de remise
  Laboratoires 48 %  
  Examen Intra 22 % Groupe 1: 12 octobre 2018
  Examen final 30 %  



Dates des examens intra
Groupe(s) Date
1 12 octobre 2018



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
• Pour les départements à l'exception du SEG :
Dans les cinq (5) jours ouvrables suivant 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. Pour un examen final, l’étudiant devra justifier son absence auprès du Bureau du registraire. 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 ou autre) à un examen entraînera l’attribution de la note zéro (0).

• Pour SEG :
Dans les cinq (5) jours ouvrables suivant la tenue de son examen, l’étudiant devra justifier son absence auprès de son enseignant. Pour un examen final, l’étudiant devra justifier son absence auprès du Bureau du registraire. 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 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/A-propos/Direction/Politiques-reglements/Infractions_nature_academique.pdf ) 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, 2e édition, Paris, Dunod, 2002

ou

  • CORMEN, T., LEISERSON, C., RIVEST, R., Introduction to Algorithms, 2nd Ed., Cambridge, MA, MIT Press, McGraw Hill, 2001.



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/