Vidéo pédagogique
Chapitres
Notice
Langue :
Français
Crédits
INRIA (Institut national de recherche en informatique et automatique) (Réalisation), Paul Gastin (Intervention)
Conditions d'utilisation
Droit commun de la propriété intellectuelle
DOI : 10.60527/48k4-dj24
Citer cette ressource :
Paul Gastin. Inria. (2010, 2 juin). Quelques rudiments de calculabilité et de complexité. [Vidéo]. Canal-U. https://doi.org/10.60527/48k4-dj24. (Consultée le 26 mai 2024)

Quelques rudiments de calculabilité et de complexité

Réalisation : 2 juin 2010 - Mise en ligne : 1 juin 2010
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

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.

Intervention

Sur le même thème