Aller au menu Aller au contenu
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

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

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo
  • Volumes horaires

    • CM : 16.5
    • TD : 16.5
    Crédits ECTS : 3.0

Objectifs

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

Contact Frédéric WAGNER

Contenu

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ôles 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 ISI->Semestre 8
Cursus ingénieur->Filière IF->Semestre 8
Cursus ingénieur->Filière MMIS->Semestre 8

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

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail Partagez cet article Facebook Twitter Linked In Google+ Viadeo

mise à jour le 15 janvier 2017

Grenoble INP Institut d'ingénierie Univ. Grenoble Alpes