Mathématiques discrètes II : algorithmes et complexité [ LINMA2111 ]
5.0 crédits ECTS
30.0 h + 22.5 h
2q
| Enseignant(s) |
Blondel Vincent ;
|
Langue
d'enseignement: |
Anglais
|
| Lieu de l'activité |
Louvain-la-Neuve
|
| 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 |
Etudier des algorithmes exacts et approximatifs pour des problèmes combinatoires de différents points de vue : conception, structures de données, analyse de performance, existence, complexité, implémentation.
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.
|
| Autres infos |
Introduction to Algorithms, T.H. Cormen, C.E. Leierson and R.L. Rivest, MIT Press 1986.
Algorithmics: Theory and Practice, G. Brassard and P. Bratley, Prentice Hall 1988.
|
Cycle et année
d'étude |
> Master [120] : ingénieur civil en mathématiques appliquées
> Master [120] : ingénieur civil en informatique
> Master [120] en sciences informatiques
> Master [120] : ingénieur civil électricien
> Master [120] : ingénieur civil électromécanicien
|
Faculté ou entité
en charge |
> MAP
|
<<< Page précédente
|
