Programmes d'études

Détails et horaire du cours

Légende

  Cours de jour
  Cours de soir
  Cours en ligne
Certificats et microprogrammes de 1er cycle
Baccalauréat (formation d'ingénieur)
Études supérieures

INF8775

Analyse et conception d'algorithmes

Nombre de crédits : 3 (3 - 1.5 - 4.5) Les chiffres indiqués entre parenthèses sous le sigle du cours, par exemple (3 - 2 - 4), constituent le triplet horaire.

Le premier chiffre est le nombre d'heures de cours théorique par semaine (les périodes de cours durent 50 minutes).
Le second chiffre est le nombre d'heures de travaux dirigés (exercices) ou laboratoire, par semaine.
(Note : certains cours ont un triplet (3 - 1.5 - 4.5). Dans ce cas, les 1,5 heure par semaine sont des laboratoires qui durent 3 heures mais qui ont lieu toutes les deux semaines. À Polytechnique, on parle alors de laboratoires bi-hebdomadaires).
Le troisième chiffre est un nombre d'heures estimé que l'étudiant doit investir de façon personnelle par semaine pour réussir son cours.
Département : Génies informatique & logiciel
Préalable(s) : INF2010, LOG1810 ou LOG2810, 70 crédits
Corequis : Aucun
Notes :
Responsable(s) : Gilles Pesant
Description
Notions élémentaires d'algorithmique. Notation asymptotique. Analyse d'un algorithme selon les ressources consommées : temps de calcul, espace mémoire et processeurs. Analyse empirique, théorique et hybride. Consommation de ressources en pire cas, en moyenne et amortie. Patrons de conception d'algorithmes : vorace, diviser-pour-régner, programmation dynamique, parcours de graphes, métaheuristique et probabiliste. Caractérisation des algorithmes d'optimisation : exact, heuristique et approximatif. Introduction aux classes de complexité : P et NP. Décidabilité.

Plan triennal

2024-2025 2025-2026 2026-2027
Automne Hiver Été Automne Hiver Été Automne Hiver Été
Cours de jour Cours de jour - Cours de jour Cours de jour - Cours de jour Cours de jour -