• FR
  • EN

Informatique fondamentale

Sigle: S1214, ECTS: 1

Objectifs du cours

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 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 utilitaire 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 prévisible des techniques numériques. Celles-ci devront, par contre, toujours se plier aux limitations incontournables qu'imposent les principes fondamentaux de la science informatique qui seront abordés dans ce cours. 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 permet de mieux cerner les limites de tout calcul.
C'est à travers l'étude formelle des notions de calcul, de machine, de langage de programmation ou de complexité que l'ingénieur ou le décideur pourra se forger une vision plus abstraite, plus durable et plus fiable de cet outil prodigieux qu'est l'ordinateur.

Objectifs
Les objectifs de ce cours d'introduction aux principes fondamentaux de l'informatique sont :

  • 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 formels existants ;
  • ... et, surtout, s'amuser et se surprendre !

Pré-requis

L’essentiel des sujets exposés ne supposera aucune connaissance spécifique particulière, hormis un minimum d’intérêt général pour la formalisation des concepts, une connaissance des principes de base de la programmation abordés en première année...  et une bonne dose de curiosité.

Programme

  • Introduction : limites de l'informatique, notion de problème, systèmes logiques, formalisation des mathématiques et applications à l'informatique, notion de résolution effective (incomplétude, décidabilité), langages, 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.

Modalités d'évaluation

Le mode d'évaluation sera fonction du nombre d'élèves présents et de leurs préférences : présentations orales, examen, QCM, élaboration d'une critique d'un article...

Equipe pédagogique

Responsable(s)
Pierre JOUVELOT

Chargé(s) d'enseignement
Samuel BENVENISTE

Intervenant(s)
Olivier HERMANT
Sigle S1214
Année 2ème année
Niveau Graduate 1st year
Crédits ECTS 1
Coefficient 1
Nb. d'heures 12
Nb. de séances 10
Type de cours Enseignement spécialisé
Semestre 4
Période Printemps
Domaines
  • Informatique
Dernière mise à jour:
20 Jun 2017 11:21 par julien