Sommaire
cours / présentation
Quelques rudiments de calculabilité et de complexité
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 g...
Date de création :
02.06.2010Auteur(s) :
Paul GASTINAccéder à la ressource :
Présentation
Informations pratiques
Langue du document : Français
Type : cours / présentation
Niveau : formation continue
Durée d'exécution : 1 heure 21 minutes 10 secondes
Contenu : vidéo
Document : video/mp4
Poids : 467.55 Mo
Droits d'auteur : libre de droits, gratuit
Droits réservés à l'éditeur et aux auteurs.
Droits réservés à l'éditeur et aux auteurs.
Description de la ressource
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.
"Domaine(s)" et indice(s) Dewey
- Modélisation mathématique (511.8)
Domaine(s)
- Informatique théorique
- Généralités, philosophie, théorie des mathématiques
- Fondamentaux et modèles mathématiques
- Principes généraux
Intervenants, édition et diffusion
Intervenants
Fournisseur(s) de contenus : INRIA (Institut national de recherche en informatique et automatique)
Diffusion
Cette ressource vous est proposée par :
Document(s) annexe(s)
- Cette ressource fait partie de
Fiche technique
Identifiant de la fiche : 6494
Identifiant OAI-PMH : oai:canal-u.fr:6494
Schéma de la métadonnée : oai:uved:Cemagref-Marine-Protected-Areas
- LOMv1.0
- LOMFRv1.0
- Voir la fiche XML
Entrepôt d'origine : Canal-U
Voir aussi
31.01.2011
Description
:
Née au milieu du vingtième siècle avec les premiers calculateurs électroniques, l’informatique n’a cessé de se développer, touchant tous les secteurs d’activité.
- histoire de l'informatique
- ordinateur
- théorie de la calculabilité
- théorie de la complexité
- loi de Moore
- sciences du numérique
- fuscia
21.12.2012
Description
:
Retracer le parcours scientifique d’Alan Turing c’est explorer en mathématiques,
surprendre en physique et recommencer en biologie… C’est suivre un
cheminement intellectuel qui témoigne d’une grande liberté d’esprit.
- histoire de l'informatique
- Alan Turing
- calcul
- calculabilité
- philosophie des sciences
- fuscia