Partager cette page :
Discipline(s) : Infomatique et télécommunications

Algorithmique 2 : classes de complexité, algorithmique probabiliste

Semestre Semestre 2
Type Obligatoire
Nature UE
Crédits ECTS 6
Volume horaire total 40
Volume horaire CM 20
Volume horaire TD 20

Responsables

Nathalie BERTRAND

Pré-requis

Avoir suivi ALGO1

Objectifs

À la fin du cours, les étudiant.e.s savent montrer rigoureusement qu’un problème est NP-complet, peuvent proposer des solutions pour traiter un problème difficile, sont capables d’analyser la complexité d’un algorithme.

Contenu

Description du cours

L'objectif de ce cours, à la suite du cours ALGO1, est de fournir les outils de base pour la conception et l'analyse d'algorithmes plus avancés. Il s'agit ici tout d’abord d’étudier la notion de NP-complétude. On présentera ensuite des techniques pour y faire face : heuristiques, approximations, algorithmes probabilistes. D’autre part, on abordera pendant le cours les domaines spécifiques de l’algorithmique du texte, la géométrie algorithmique. On présentera des outils probabilistes (probabilités discrètes, chaînes de Markov) et des techniques de calcul de complexité.

Programme

A- NP-complétude
B- Algorithmes d’approximation
C- Algorithmes probabilistes
D- Quelques problèmes en algorithmique du texte
E- Introduction à la géométrie algorithmique

Bibliographie

Cormen, Leiserson, Rivest, Dunod, Introduction à l'algorithmique : Cours et exercices, Dunod, 2002
 
M. R. Garey, D. S. Johnson, Computers and intractability. A guide in the theory of NP-completness, San Francisco, W. H. Freeman, 1979
 
Olle Häggström. Finite Markov chains and algorithmic applications, volume 52. Cambridge University Press, 2002
 
R. Motwani and P. Raghavan. Randomized algorithms. Cambridge university press, 1995.
 
C.H. Papadimitriou. Computational complexity. John Wiley and Sons Ltd., 2003.

Contrôles des connaissances

Durant le semestre, un contrôle continu (CC) : TD noté et devoir sur table final
En session de rattrapage, un examen oral (O).
Note finale en session 1 : CC
Note finale en session 2 : O

Mise à jour le 12 juillet 2017