INF1703 - Algorithmique

Scolarité

Premier cycle - 3,0 crédit(s)

Département

Aucun

Objectifs

Au terme de ce cours, l'étudiant.e sera en mesure de concevoir des solutions algorithmiques à un problème et de les analyser selon plusieurs critères de performance.

Contenu

Critères de choix d'une solution algorithmique de problèmes, complexité d'algorithme versus performance de l'implantation, complexité en pire cas et en moyenne. Principaux types d'algorithmes, leurs qualités et défauts: algorithmes voraces, diviser pour régner, retour arrière, «branch and bound», programmation dynamique; exemples de problèmes résolus par des algorithmes de chaque type et leur analyse. Méthodes d'exploitation des graphes et leurs applications. Bornes inférieures de performance des algorithmes. Problèmes polynomiaux et intraitables, problèmes NP-complets, heuristiques, solutions approximatives. Ce cours comporte des séances obligatoires de travaux dirigés (TD).

Préalables

Exigences de qualification pour l'enseignement

Diplôme(s)
Aucun
Expérience
Aucune
Corps professionnel
Aucun
Autre(s) exigence(s)
Aucune

CAFF

Aucun