Pierre Rouge Sciences - La complexité en Informatique

Date: 
le 16 janvier 2018
Horaires: 
18h à 20h
Commune: 
Assas
Lieu: 
Salle Pierre Rouge (près du château)

 

La complexité en Informatique
Complexité spatio-temporelle des programmes, des algorithmes  et des problèmes

Les notions de programme, algorithme et problème sont intimement liées puisqu’un programme est la réalisation d’un algorithme, résolvant un certain problème, sur un système informatique. Partant d’une question naturelle, et en apparence simple, /de quels moyens en espace mémoire et en temps de calcul un programme doit-il disposer ?/, nous passerons à la complexité spatio-temporelle d’un algorithme puis à celle d’un problème.

Pour formaliser cette complexité algorithmique nous présenterons le modèle de calculabilité inventé par Turing et dénommé par Church « machine de Turing ». Nous terminerons par une question concernant des classes de problèmes : /la classe des problèmes « faciles à résoudre » est-elle différente ou égale à la classe des problèmes « faciles à vérifier » ?/  De nombreux chercheurs travaillent sur ce problème ouvert depuis plus de quarante ans.

Conférence par M. Michel Chein, Professeur émérite à l'Université de Montpellier, Chercheur au LIRMM  Membre de l'Académie des Sciences et Lettres de Montpellier

Une participation aux frais de 2€ par adulte sera demandée aux non-adhérents.
Entrée gratuite aux adhérents et étudiants.

Renseignements
pierre-rouge.fr

Tél St Mathieu de Tréviers : 04 11 95 05 75
Tél St Martin de Londres : 04 67 55 09 59