Informatique fondamentale

Nombre de places: 42 - 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 cœur 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’œuvre 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 !

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, travaux pratiques ou restitutions par groupe des travaux pratiques.

Programme

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.

Pré-requis

L’essentiel des sujets abordés ne supposera aucune connaissance spécifique particulière, hormis un minimum d’intérêt pour la formalisation des concepts, un attrait pour les langages informatiques et la compréhension des mécanismes permettant à un ordinateur de comprendre et d’exécuter ceux-ci. Enfin, une connaissance des principes de base de la programmation et notamment des notions élémentaires de typage dans ces langages, dont une familiarité avec au moins un langage avec des types statiques et orienté objet (C++, Java, Rust, C#, Kotlin, Swift, Typescript, Scala, OCaml...), et une bonne dose de curiosité seront très utiles.

Equipe enseignante

Responsable : HERMANT Olivier

Pierre Jouvelot, Olivier Hermant

Liens Web

https://cri.mines-paristech.fr


 

Adresse e-mail

Mot de passe


S'inscrire - Mot de passe oublié