UCL - Etudes

English version

Formations
Premier cycle
Second cycle
Troisième cycle
Certificats (programmes non académiques)
Passerelles
Formation continue
Facultés et entités
Cadre académique
Réforme de Bologne
Accès aux études
Organisation des études
Lexique
Calendrier académique
Règlement des études et examens
Charte pédagogique
Renseignements généraux
Recherche
Simple
Détaillée
Par cours

Mathématiques discrètes II : Algorithmes et complexité [INMA2111]
[30h+15h exercices] 4 crédits

English version

Version imprimable

Cette activité se déroule pendant le 2ème semestre

Enseignant(s):

Vincent Blondel, Laurence Wolsey, Laurence Wolsey (supplée Vincent Blondel)

Langue d'enseignement :

français

Niveau :

Second cycle

>> Objectifs (en termes de compétences)
>> Objet de l'activité (principaux thèmes à aborder)
>> Résumé : Contenu et Méthodes
>> Autres informations (Pré-requis, Evaluation, Support, ...)
>> Programmes proposant cette activité
>> Autres crédits de l'activité dans les programmes

Objectifs (en termes de compétences)

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.

Objet de l'activité (principaux thèmes à aborder)

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.

Résumé : Contenu et Méthodes

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 informations (Pré-requis, Evaluation, Support, ...)

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.

Programmes proposant cette activité

INFO2

Ingénieur civil informaticien

Autres crédits de l'activité dans les programmes

INFO23

Troisième année du programme conduisant au grade d'ingénieur civil informaticien

(4 crédits)

MAP22

Deuxième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées

(4 crédits)

MAP23

Troisième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées

(4 crédits)



Ce site a été conçu en collaboration avec ADCP, ADEF, CIO et SGSI
Responsable : Jean-Louis Marchand - Contact : secretaire@fsa.ucl.ac.be
Dernière mise à jour :02/08/2006