Canal-U_EZpublish 217315 fre 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. calculabilité codage complexité diagonalisation modèle de calcul programme réduction science informatique LOMFRv1.0 image en mouvement LOMv1.0 author 2010-06-02 LOMv1.0 content provider 2010-06-02 LOMv1.0 LOMFRv1.0 video/x-flvhttp://www.canal-u.tv/canalu/producteurs/fuscia/dossier_programmes/science_info_lycee/quelques_rudiments_de_calculabilite_et_de_complexitertmpt://mediaFM01.cines.fr/3517/cerimes/fuscia/p_gastin.mp4 490264229 PT1H21M10S LOMv1.0 lecture LOMv1.0 higher education LOMv1.0 formation continue LOMv1.0 no LOMv1.0 no Droits réservés à l'éditeur et aux auteurs LOMv1.0 ispartof URI http://www.canal-u.tv/producteurs/fuscia/(onglet)/collections/(id)/217136#onglet_collection Science Info Lycée LOMv1.0 discipline Universités Numériques Thématiques 2009 http://www.universites-numeriques.fr LOMv1.0 discipline CDD 22e éd. DDC 22nd ed. 511.8 Modélisation mathématique