Objectifs Qu’est ce qu’un ordinateur, un programme, une fonction calculable ? Quelles sont les limites de la calculabilitÉ? Qu’estce qu’une dÉmonstration? Dans quelles parties des mathÉmatiques peuton faire des dÉmonstrations “automatiques”? Ce qui est calculable en thÉorie l’estil en pratique sur des ordinateurs rÉels? Voici quelques unes des questions concernant les fondements Étroitement mlÉs des mathÉmatiques et de l’informatique que nous allons approfondir dans ce cours.
1
PrÉsentation du cours Programme Les principaux points du programme sont : •: syntaxe, thÉorÈmes de complÉtude, modÈles, dÉmonstration. Le thÉoLa logique mathÉmatique rÈme de Gdel. •La calculabilitÉ: machines de Turing, fonctions rÉcursives, langage de Markov, lambda calcul. Le problÈme de l’arrt. Les rÉsultats d’indÉcidabilitÉ. •: la complexitÉ en temps et la complexitÉ algorithmique, NP complÉtude, complexitÉLa complexitÉ et suites alÉatoires. •: l’analyse non standard, la dÉmonstration automatique, compression etApplications et extensions codage, cryptographie, programmation symbolique.
ContrÔle Il y a deux parties : −Vous devrez faire un petit projet (À rendre avant le 15 juin) comportant une petite Étude bibliogra phique sur un sujet que vous aurez choisi parmi tous les thÈmes abordÉs dans le programme et un rÉsumÉ d’un article, une dÉmonstration d’un point imprtant ou une application, une expÉrience (par exemple Écriture d’un programme dans le style duλcalcul ou dans un langage de programmation par rÈgles). −Vous aurez un contrÔle d’une durÉe de 1 h 30 sur un programme couvrant quelques points princi paux du cours qui sera prÉcisÉ ultÉrieurement.