Département d'informatique et de recherche opérationnelle

IFT 2102 --- H98
Introduction à l'informatique théorique

Professeur: Claude Crépeau, 3347 André--Aisenstadt
Début des cours: le mercredi 7 janvier 1998
Début des TPs: le lundi 5 janvier 1998
Horaire: cours mercredi 10:30-11:30, vendredi 13:30-15:30, TPs lundi 13:30-15:30


Objectifs: Au début il y avait la paresse. Alors l'homme inventa la machine qui, après quelques hésitations, devint puissante, très puissante. Tellement puissante que la vision populaire la conçoit comme tout-puissante. Et pourtant... Ce cours a pour but de nous faire nous pencher sur les fondements même de l'informatique. Qu'est ce que c'est qu'un problème? Qu'est ce que c'est qu'un programme? Qu'est ce que c'est qu'un algorithme? Qu'est ce que cela veut direcalculer? Pourquoi un problème semble plus difficile qu'un autre?. Pour essayer de répondre à ces questions, nous allons traverser un peu l'histoire de l'informatique, en commençant par Aristote, en passant par Boole, Hilbert et Russell, pour atterrir en plein XX-ème siècle avec ses modèles formels de calcul tels automates finis et machines de Turing. La plus grande partie du cours sera occupée par ces modèles de calculs, leurs propriétés, leurs puissances et leurs limites.
évaluation:
Le cours ne demande pas de programmation. Il y aura un examen intra, un examen final et un certain nombre d'exercices théoriques. L'évaluation durant le cours se fera avec des notes numériques; la conversion en notation littérale se fera sur la note cumulative finale.

Barème (avec seuil):
Examen intra: 25%
Examen final: 35%
Exercices: 40%

Le seuil: Pour que les exercices comptent dans la note finale, vous devez obtenir une moyenne pondérée d'au moins 40% aux examens.


Livre obligatoire:
Introduction to the Theory of Computation, Micheal Sipser, PWS Publishing Co.
(Notez que nous utiliserons la version FINALE du livre de Sipser et PAS LES VERSIONS PRÉLIMINAIRES.)

Autres livres utiles (la plupart en réserve à la bibliothèque) :
J.-M.Autebert, Langages Algébriques, Masson, 1987; F.Hennie, Introduction to Computability, Addison-Wesley, 1977 ; J.E.Hopcroft, J.D.Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979; H.R.Lewis, C.H.Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1988; R.McNaughton, Elementary Computability, Formal Languages and Automata, Prentice-Hall, 1982; Pierre Wolper, INTRODUCTION À LA CALCULABILITÉ, InterEditions, 1991.
Plan approximatif du cours: