Algorithmique avancée, algorithmes d'approximation, parallèles et probabilistes, complexité - 4MMALGA6

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 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

Le cours est programmé dans ces filières :

• Cursus ingénieur - Filière MMIS - Semestre 8
• Cursus ingénieur - Filière MMIS - Semestre 8
• 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

Code de l'enseignement : 4MMALGA6
Langue(s) d'enseignement :

Le cours est rattaché aux structures d'enseignement suivantes :

• Equipe Algorithmique-Mathématiques discrètes

Vous pouvez retrouver ce cours dans la liste de tous les cours.

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