Informatique fondamentale

42

Français

Mines Paris

Née dans la première moitié du vingtième siècle, l'informatique (Computer Science) est une discipline jeune dont l'impact pratique croissant sur les organisations, les sciences, les pratiques et les modes de pensée a pu faire oublier qu'elle est aussi une branche des mathématiques, celle des mathématiques constructives, qu'elle a contribué à enrichir.


Se limiter à une vision utilitariste de l'informatique, de par le caractère empirique et souvent daté qu'elle suppose, ne prépare pas le futur décideur ou ingénieur à accompagner l'évolution rapide des techniques numériques.


L'ambition de ce cours est donc d'aborder l'étude de l'informatique en tant que discipline, au coeur de laquelle se trouvent les notions de calcul, de machines et de langages. Il permettra de découvrir les mécanismes, théoriques et pratiques, à l'oeuvre derrière ces concepts, ainsi que les limitations incontournables qu'imposent les principes fondamentaux de la science informatique.


Qu'il s'agisse des problèmes sans solution, dits indécidables, ou de ceux, dits NP-complets, pour lesquels les ressources nécessaires à leur résolution dépassent le nombre de particules de l'univers, l'informatique fondamentale permettent de mieux cerner les limites et les modèles de tout calcul et, par là, de tout langage passé, présent, et futur. Il s'agira donc de :
- introduire des connaissances qui seront toujours valables dans dix ans ;
- tisser des liens entre formalisation mathématique et langages de programmation ;
- exhiber les limites intrinsèques de l'outil informatique ;
- rapprocher classes de problèmes et familles de solutions techniques ;
- donner des clefs pour choisir parmi les différents outils existants ;
- transformer un langage de haut niveau en des instructions exécutables par une machine ;
- ... et, surtout, s'amuser et se surprendre !

Nous aborderons les sujets suivants.
- Introduction : langages et grammaires, notion de problème, systèmes logiques, formalisation des mathématiques et applications à l'informatique, limites de l'informatique, notion de résolution effective (incomplétude, décidabilité), modèles opératoires.
- Modèles de calcul : machines de Turing, notion de calculabilité, lambda-calcul, systèmes de réécriture, équations diophantiennes, thèse de Turing/Church, équivalences ; application aux paradigmes de programmation (impératif, fonctionnel, objet, logique).
- Définitions des langages de programmation : syntaxe, typage, notion de point fixe, sémantique opérationnelle (McCarthy, 1963), sémantique axiomatique (Hoare, 1969), sémantique dénotationnelle (Milne et Strachey, 1976).
- Complexité : types de complexité, non-déterminisme, complexité temporelle, problèmes NP-complets, théorème de Cook, complexité spatiale, théorèmes de hiérarchies.
- Aspects avancés : randomisation, informatique quantique, calcul ADN.

Ces concepts seront concrétisés durant des travaux pratiques tels que :
- génération d'un analyseur lexical et syntaxique à partir d'une grammaire ;
- initiation à la programmation fonctionnelle (OCaml) ;
- mathématiques constructives en Coq ;
- sémantique axiomatique et preuve de programmes ;
- programmation d'un algorithme quantique.

Le mode d'évaluation sera fonction de l'assiduité et, en partie, du nombre d'élèves présents et de leurs préférences : présentations orales, élaboration d'une critique d'un article, travaux pratiques ou restitutions par groupe des travaux pratiques.

L'essentiel des sujets abordés ne supposera aucune connaissance spécifique particulière.

HERMANT Olivier

HERMANT Olivier;
JOUVELOT Pierre