Planifier son trajet en voiture, trouver une bonne stratégie au jeu du go, trier ses chaussettes, résoudre un sudoku, optimiser une chaîne de production… Notre quotidien est jonché de problèmes à résoudre ; certains semblent faciles, d’autres beaucoup moins. La théorie de la complexité algorithmique vient à notre rescousse afin d’y voir un peu plus clair.
Mot(s) clés libre(s) : complexité algorithmique, calculabilité, NP-complet

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.
Mot(s) clés libre(s) : calculabilité, codage, complexité, diagonalisation, modèle de calcul, programme, réduction, science informatique

En 1931, Kurt Gödel (1906 - 1978) démontrait, dans un article révolutionnaire, qu'un système d'axiomes cohérent et suffisamment expressif est susceptible de générer des énoncés dont la validité ne peut être démontrée dans le cadre des règles mêmes qui gouvernent la formulation de ces énoncés et leurs déductions. Apparemment très technique, ce théorème bouleversait la philosophie des mathématiques, et en particulier la vieille question de leur "fondement". Jean-Marc Deshouillers se propose ici de décrire l'avant et l'après Gödel en retraçant l'histoire des théories mathématiques depuis Aristote et Euclide jusqu'au renversement révolutionnaire des fondements mathématiques induit par le théorème d’incomplétude.La conférence a été donnée à l'Université Victor Segalen Bordeaux 2 dans le cadre du cycle de conférences "L'invité du Mercredi" / Saison 2005-2006 sur le thème "L'espoir". Service culturel Université Victor Segalen de Bordeaux 2 / DCAM /
Mot(s) clés libre(s) : calculabilité, formalisation mathématique, intuitionnisme, philosophie des mathématiques, théorème de Gödel, théorème d’incomplétude, théorie des ensembles, théorie des groupes, théorie mathématique