Informatique fondamentale et compilation

Nombre de places: 38 - Langue: Français

Objectifs

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 et la compilation 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 ;
•     construire un compilateur, permettant de transformer un langage de haut niveau en des instructions exécutables par une machine ;
... et, surtout, s'amuser et se surprendre !

Evaluation

Le mode d'évaluation sera fonction du nombre d'élèves présents et de leurs préférences : présentations orales, élaboration d'une critique d'un article, ainsi que celle des travaux pratiques en compilation.

Programme

En « informatique fondamentale » :
•     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.
La partie « compilation » exemplifiera les concepts abordés ci-dessus et mènera à une implémentation concrète d’un compilateur :
•     Grammaires formelles.
•     Analyse lexicale, analyse syntaxique et génération automatique de tels analyseurs.
•     Arbres de syntaxe.
•     Représentation intermédiaire.
•     Génération de code assembleur.

Pré-requis

Le mode d'évaluation sera fonction du nombre d'élèves présents et de leurs préférences : présentations orales, élaboration d'une critique d'un article, ainsi que celle des travaux pratiques en compilation.

Equipe enseignante

Olivier HERMANT, Fabien COELHO

Liens Web

https://cri.mines-paristech.fr


 

Adresse e-mail

Mot de passe


S'inscrire - Mot de passe oublié