Note du 29 juin 2020
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.
5 crédits
30.0 h + 22.5 h
Q1
Enseignants
Blondel Vincent; Delvenne Jean-Charles (coordinateur);
Langue
d'enseignement
d'enseignement
Anglais
Préalables
Ce cours suppose une maturité suffisante en mathématique, d'un niveau équivalent à celle d'un étudiant ingénieur arrivé au terme de sa troisième année d'étude. Le cours est une introduction à l'algorithmique et traite principalement des aspects non numériques. On y fait une analyse mathématique de l'existence et de la complexité d'algorithmes pour des problèmes classiques liés aux structures et problèmes discrets. Il est utile que les étudiants aient déjà été confrontés à des questions algorithmiques non-élémentaires ; il n'y a toutefois pas de prérequis particulier en algorithmique.
Thèmes abordés
Ce cours est une introduction à l'algorithmique et traite principalement des aspects non numériques. On y fait une analyse mathématique de l'existence et de la complexité d'algorithmes pour des problèmes classiques liés aux structures et problèmes discrets.
Acquis
d'apprentissage
d'apprentissage
A la fin de cette unité d’enseignement, l’étudiant est capable de : | |
| 1 |
Eu égard au référentiel AA, ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
|
La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».
Contenu
Introduction aux algorithmes de base en algorithmique (tri, implémentations efficaces de différentes structures de données) avec une analyse de complexité en moyenne et dans le pire des cas. Etudes de différentes classes d'algorithme comme les algorithmes gloutons, la programmation dynamique et les algorithmes approximatifs. Aspects de la théorie de la complexité et la calculabilité : classes de complexité, NP-complétude, difficulté d'approximation, existence d'algorithmes.
Méthodes d'enseignement
Le cours est organisé autour de séances de cours et de devoirs hebdomadaires pour lesquels un service de consultance facultatif est offert.
Modes d'évaluation
des acquis des étudiants
des acquis des étudiants
Les étudiants sont évalués individuellement et par écrit sur base des objectifs particuliers énoncés plus haut. En outre les étudiants réalisent des devoirs durant le cours. Les devoirs sont corrigés et commentés. Les notes obtenues pour les devoirs sont comptabilisées dans la note finale.
Ressources
en ligne
en ligne
Bibliographie
- Algorithmics: Theory and Practice, G. Brassard and P. Bratley, Prentice Hall, 1988.
- Introduction to Algorithms, T.H. Cormen, C.E. Leierson and R.L. Rivest, MIT Press 1986.
Faculté ou entité
en charge
en charge
MAP
