4 pages
Français

Logique, mathématiques, informatique

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Logique, mathématiques, informatique

Sujets

Informations

Publié par
Nombre de lectures 271
Langue Français

Exrait

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