Logique, mathématiques, informatique

Sujets

• mathématiques
• mathématique

Informations

• Publié par: ojurarop
• Nombre de lectures: 357
• Langue: Français

Extrait

Logique, mathÉmatiques, informatique

Logique, mathÉmatiques, informatique

Objectifs Qu’est ce qu’un ordinateur, un programme, une fonction calculable ? Quelles sont les limites de la calculabilitÉ? Qu’estce qu’une dÉmonstration? Dans quelles parties des mathÉmatiques peuton faire des dÉmonstrations “automatiques”? Ce qui est calculable en thÉorie l’estil en pratique sur des ordinateurs rÉels? Voici quelques unes des questions concernant les fondements Étroitement mlÉ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ÉoLa logique mathÉmatique rÈme de Gdel. •La calculabilitÉ: machines de Turing, fonctions rÉcursives, langage de Markov, lambda calcul. Le problÈme de l’arrt. 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.

ECP 20052006

Cours d’approfondissement