100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Thierry Gallay

Introduction à la théorie de la complexité.

Tuesday, 13 December, 2005 - 17:30
Prénom de l'orateur : 
Claire
Nom de l'orateur : 
TAUVEL
Résumé : 

Le but de cet exposé est de définir les classes de complexité P, NP
et de comprendre ce qu'est un problème NP-complet. Dans ce but, on
sera amené à définir les modèles de calcul que sont les automates
finis et les machines de Türing (déterministes ou non). Ces modèles
permettront de formaliser les notions de temps de calcul et de
difficulté des problèmes. L'exposé sera illustré d'exemples
essentiellement issus de la théorie des graphes.

Institution de l'orateur : 
IMAG
Thème de recherche : 
Compréhensible
Salle : 
1 tour Irma
logo uga logo cnrs