Recherche avancée
Libres Savoirs >> Sciences et technologies de l'information et de la communication >> Informatique
Responsable :

Pierre Jouvelot
  

Equipe Pédagogique :
Samuel Benveniste

Niveau : Graduate

Langue du cours : Français

Période : Printemps

Nombre d'heures : 12

Crédits ECTS : 1
SGS_S1214 Informatique fondamentale
Ressources Pédagogiques :
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 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 ;
  • 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 !


Programme:
  • Introduction : limites de l'informatique, notion de problème, notion de résolution effective (incomplétude, décidabilité), langages, modèles opératoires.
  • Modèles de calcul : machines de Turing, notion de calculabilité, 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.


Niveau 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é.

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


Dernière mise à jour : dimanche 12 décembre 2010

© Mines de Paris 2017 - Réalisé par Winch Communication