Imprimer Version XML Ajouter à mon panier

Ressource pédagogique : Quelques rudiments de calculabilité et de complexité

Mots-clés :

Accéder à la ressource pédagogique

cours / présentation - Date de création : 02-06-2010

Auteur(s) : Paul GASTIN

Partagez !

Présentation
Intervenants, éditions et diffusion
Documents annexes

Présentation de: Quelques rudiments de calculabilité et de complexité

Informations pratiques sur cette ressource

Langue du document : Français

Type pédagogique : cours / présentation

Niveau : formation continue

Durée d'exécution : 1 heure 21 minutes 10 secondes

Contenu : image en mouvement

Document : video/mp4

Taille : 467.55 Mo

Droits d'auteur : libre de droits, gratuit
Droits réservés à l'éditeur et aux auteurs.

Description de la ressource pédagogique

Description (résumé)

Dans cet exposé, Paul Gastin, à travers des exemples concrets tel que le jeu du Sudoku, pose les deux problématiques fondamentales de l'algorithmique théorique que sont calculabilité et complexité, en définissant les notions et en donnant des jalons historiques de Hilbert à Gödel et Turing sur les grandes étapes des idées à ce sujet. Il définit les classes de complexité et donne quelques clés pour les évaluer. Ce cours a été donné en juin 2010 lors des journées de formation à l'informatique organisées par l'INRIA à destination des professeurs de mathématiques d'Ile de France. Il est composé d'une présentation et d'une séance de questions-réponses.