Discrete mathematics II : Algorithms and complexity

LINMA2111  2016-2017  Louvain-la-Neuve

Discrete mathematics II : Algorithms and complexity
5.0 crédits
30.0 h + 22.5 h
1q

Enseignants
Delvenne Jean-Charles (coordinateur); Blondel Vincent;
Langue
d'enseignement
Français
Prérequis

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

Eu égard au référentiel AA, ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :

  • AA1 : 1,2,3
  • AA3 : 1,3
  • AA4 : 1
  • AA5 : 1,2,3,5,6

À l'issue de ce cours, l'étudiant sera en mesure de :

  • 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é.
  • Mettre en 'uvre des techniques générales (diviser pour régner, programmation dynamique, etc.) pour résoudre des problèmes algorithmiques de base (par exemple le tri) et en faire une analyse de complexité en moyenne et dans le pire des cas.
  • Evaluer la complexité algorithmique d'un problème donné.
  • Prendre des initiatives pour rechercher des informations utiles à l'analyse d'un problème.
  • Proposer des solutions originales et les comparer aux solutions disponibles.
  • Rédiger un rapport sur les solutions proposées et disponibles.

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) ».

Modes d'évaluation
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.

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.

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.

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


Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
Master [120] : ingénieur civil en mathématiques appliquées
5
-

Master [120] : ingénieur civil électricien
5
-