Revenir à Maîtrise d’ informatique

Calculabilité et complexité

Objectifs

Présenter, d’un point de vue théorique, les limites des capacités des ordinateurs, les limites entre problèmes accessibles et inaccessibles, et les limites inhérentes à l’informatique. Cette étude porte, non sur la programmation, mais sur les programmes eux-mêmes.

Programme

Bibliographie

  • Introduction à la calculabilité, P. Wolper, [InterÉditions]
  • Le langage des machines, R. Floyd et R. Biegel, [InternationalThomsonPublishing]
  • Calculabilité et décidabilité, une introduction, J. M. Autebert, [Masson]
  • Godel Escher Bach, Les brins d’une guirlande éternelle, D. Hofstadter, [InterÉditions]

Annales d’examens

Travaux dirigés

Devoirs

Wikipedia