Version PDF

Programme(s) : 7483, 7883

Profils(s) : Électricité, Informatique, Technologie de systemes ordines

Afficher les préalables et les unités d'agrément

Afficher les qualités de l'ingénieur

École de technologie supérieure

Responsable(s) de cours :

Kim Khoa Nguyen, Catherine Laporte

PLAN DE COURS

Automne 2023
ELE440 : Algorithmes (4 crédits)

Préalables

Unités d'agrément
Total d'unités d'agrément : 64,8

Qualités de l'ingénieur

Q10

Q11

Q12

Qualité visée dans ce cours

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

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	Jeudi	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	Catherine Laporte	Activité de cours	Catherine.Laporte@etsmtl.ca	A-4490
01	Laurent Morissette	Laboratoire	cc-laurent.morissette@etsmtl.ca

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, l'environnement de développement Visual Studio Code et les outils de gestion de version git et gitlab.

Évaluation

Activité	Description	%	Date
	Laboratoires	45 %
	Examen de mi-session	25 %
	Examen final	30 %

Dates des examens intra

Groupe(s)	Date
1	20 octobre 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 : 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).

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

CORMEN, T., LEISERSON, C., RIVEST, R., Introduction à l’algorithmique, 3^eédition, Paris, Dunod, 2010

CORMEN, T., LEISERSON, C., RIVEST, R., Introduction to Algorithms, 3^rd 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/