Volumes horaires
- CM 16.5
- Projet -
- TD 16.5
- Stage -
- TP -
- DS -
Crédits ECTS
Crédits ECTS 3.0
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.
Responsable(s)
Frederic WAGNER
Contenu(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.
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 :
- MCC en présentiel ou distanciel **
N1=3/4E1+1/4P
N2=3/4E2+1/4P
dans le cas du distanciel l'examen ecrit e1 sera a distance
- MCC en présentiel ou distanciel **
Calendrier
Le cours est programmé dans ces filières :
- Cursus ingénieur - Filière ISI - Semestre 8
- Cursus ingénieur - Filière ISI - Semestre 8
- Cursus ingénieur - Filière IF - Semestre 8
- Cursus ingénieur - Filière IF - Semestre 8
- Cursus ingénieur - Filière MMIS - Semestre 8
Informations complémentaires
Code de l'enseignement : 4MMALGA6
Langue(s) d'enseignement : 
Le cours est rattaché aux structures d'enseignement suivantes :
Vous pouvez retrouver ce cours dans la liste de tous les cours.
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