Fiche du document
- handle: 10670/1.y9jqt3
- doi: 10.60527/48k4-dj24
Droit commun de la propriété intellectuelle
Mots-clés
Codage InformatiqueSujets proches
Información--Sistemas Datos--Tratamiento Procesamiento de datos Procesamiento electrónico de datos Proceso electrónico de datos Tratamiento de datos Tratamiento electrónico de datos Ciencia de los ordenadores Información--Tratamiento automático Información automática Tecnología de los ordenadores Traitement des données Information, Traitement électronique de l' Traitement intégré des données Traitement électronique de l'information Informatisation Gestion des donnéesCiter ce document
Paul Gastin, « Quelques rudiments de calculabilité et de complexité », Canal-U, la vidéothèque de l'enseignement supérieur, ID : 10.60527/48k4-dj24
Métriques
Partage / Export
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.