Volumes horaires
- CM 13.5
- TD 13.5
- TP 6.0
Crédits ECTS
Crédits ECTS 2.5
Objectif(s)
A partir de la notion de complexité d'un problème (bornes inférieures, réductions, classes de complexité, classification NP), le cours présente les principales techniques pour la résolution efficace de problèmes : heuristiques, algorithmes d'approximation, probabilistes, parallèles, interactifs. Le cours est associé à un travail pratique de programmation d'un jeu multi-joueurs, en C++.
Contact Jean-Louis ROCHContenu(s)
1. Introduction. Modèles de calcul et complexité. Heuristiques (ex. alpha-beta)
2. Complexité; bornes inférieures; réductions.
3. Classes de complexité P, NP, NP-complet.
4. Algorithmes d'approximation. Classes APX.
5. Algorithmes probabilistes. Classes [BRZ]PP.
6. Algorithmes parallèles. Classes [ RZ][AN]C.
7. Algorithmes et preuves interactives (IP), hiérarchie polynomiale.
Prérequis
Un prérequis est une très bonne compréhension de l'analyse du coût d'algorithmes séquentiels simples (itératif/boucles, récursif/diviser pour régner).
Prérequis vus en cours de 1ère année: Algorithmique et programmation de première année (3MMALG2), graphes (3MMRO), notions élémentaires de complexité/machine de Turing (3MMTL2).
Contrôle des connaissances
CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) :travail pratique avec rapport (TP : coef 1 / 4).
SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : un examen écrit (2h)(E : coef 3 / 4)
Salle spécifique :
Durée : 2h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) :tous documents
Documents interdits (ex : livres, tous documents) : livres
Matériel (ex : calculatrices):
- matériel autorisé, préciser :aucun
- matériel interdit, préciser : ordinateur, téléphone, tablette, ...
Commentaires :
SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : oral si nombre d'étudiants < 6
Salle spécifique :
Durée : 2h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) :tous documents
Documents interdits (ex : livres, tous documents) :livres
Matériel (ex : calculatrices):
- matériel autorisé, préciser :aucun
- matériel interdit, préciser :
Commentaires :
N1=3/4E1+1/4P
N2=3/4E2+1/4P
Informations complémentaires
Cursus ingénieur->Filière MMIS->Semestre 4
Cursus ingénieur->Filière ISI->Semestre 4
Cursus ingénieur->Filière IF->Semestre 4
Bibliographie
S. Arora, B. Barak, Computaional complexity: a modern approach, 2009
P. Berlioux, M.-P. Cani, A. Lux, R. Mohr, D. Naddef, J.-L. Roch : Algorithmique II.. Polycopié ENSIMAG
T. Cormen, C.E. Leiserson, R. Rivest, C. Stein : Introduction to Algorithms, 2nd edition, 2001