Logo EPFL
Ecole Polytechnique Fédérale de Lausanne
Informatique Théorique III - 2004/2005
français seulement

  • Lire les messages du forum.
  • Consultation des copies le lundi 21 mars 2005 de 9h30 à 12h30 en salle INR331.
  • 2005-01-19 [Notes du cours, version finale] pdf, ps, gz
  • 2005-01-19 [Examen blanc,solutions] pdf, ps, gz (2 par page: pdf, ps, gz).
    Solution alternative pour 2.1: pdf, ps, gz
  • 2005-01-19 [Examen blanc] pdf, ps, gz (2 par page: pdf, ps, gz).
  • 2005-01-28 [Notes, Partie 2] enlevé § 1.5
  • 2005-01-12 [Notes, Partie 11] corrections dans 4.1.3
  • 2005-01-11 [Notes, Partie 11] corrections dans 4.3.1
  • 2005-01-11 [Notes, Partie 1] adaptation de 1.3.9 à la version du cours
  • 2004-12-21 [Notes, Partie 10] corrections dans 3.8.4
  • 2004-12-19 [Notes, Partie 10] corrections dans 3.7.2
  • 2004-12-08 [Notes, Partie 8] renommage de 3.2 à 3.4
  • 2004-12-08 [Notes, Partie 8] corrections dans 3.2.11
  • 2004-12-06 [Notes, Partie 8] corrections dans 3.2.12
  • 2004-12-05 [Notes, Partie 8] corrections dans 3.2.8-9
  • 2004-11-29 [Notes, Partie 7] correction de la définition "arbre de dérivation"
  • 2004-11-27 [Notes, Partie 6] changements dans 2.8.9-11
  • 2004-11-17 [Notes, Partie 5] corrections dans 2.5.6
  • 2004-11-14 [Notes, Préliminaires] ajout de quelques définitions et lemmes
  • 2004-11-09 [Notes, Partie 4] corrections dans 2.4.19
  • 2004-11-08 [Exercices, Série 4] ajout d'une indication pour l'exercice 2
  • 2004-11-03 [Transparents, Partie 3] update
  • 2004-11-03 [Notes, Partie 3] corrections dans 2.3.3-7
  • 2004-10-31 [Notes, Partie 3] correction de 2.2.5
  • 2004-10-28 [Exercise supplementaire] - relations: (pdf, ps, gz).
  • 2004-10-28 [Transparents, Partie 2] update
  • 2004-10-27 [Notes, Partie 2] précision de 1.5.4 et 1.5.5
  • 2004-10-26 [Notes, Partie 2] précision de 1.4.7 et 1.4.8
  • 2004-10-25 [Notes, Partie 1] mauvais symbole de Nat dans 1.2.2

Le cours est donné le lundi et le mercredi de 13h15 à 16h00 en salle CE6.

Les documents du cours sont rendus accessible ci-dessous sont en format pdf, mais aussi en format Postscript (ps) et Postscript "gzippé" (gz). Le format 4on1 contient 4 transparents (taille: 8ème) par pages et laisse beaucoup d'éspace pour des notes personnelles. Pensez au fait que les transparents sont assez grands (>10MB), surtout en format Postscript.

Nous mettrons ces documents sur ce site les jours suivants:

  • Les notes du cours, le vendredi avant le cours.
  • Les transparents, mercredi après-midi (après le cours).
  • Les exercises, le vendredi avant.
  • Les corrigés des exercises, le vendredi après.
  • Le quiz et son corrigé, mercredi soir.

Semaine Sujet Notes Transparents
(4on1)
Exercises
(Corrigé)
Quiz
(Corrigé)
1 Introduction pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
2 Grammaires, AFD pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
3 AFN, AFNe pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
4 Expressions régulières pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
5 Propriétés pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
6 Taille des AFD pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
7 Grammaires non-contextuelles pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
8 Automates à pile pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
9 Forme Normale de Chomsky pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
10 AAP déterministe & stabilité pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
11 Machines de Turing pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
12 Diagonalisation et universalité pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
13 Réduction et Théorème de Rice pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
14 Problèmes indécidables pdf, ps, gz pdf, ps, gz
(pdf, ps, gz)
pdf, ps, gz
(pdf, ps, gz)
Pas de quiz.

La langue de travail sera le français. Mais nous sommes prêts à répondre aux questions in english, auf deutsch, in italiano, español, och på svenska.

Nous vous recommandons fortement d'utiliser le forum: votre question intéresse très certainement d'autres personnes. Il sera plus facile pour tout le monde que vous posiez vos questions via ce canal, étant donné que nous utiliserons celui-ci pour nos réponses. Par ailleurs, vous avez certainement remarqué que parfois, le simple fait de formuler sa question de manière précise afin de se faire comprendre par son interlocuteur suffit à vous en donner la réponse.

Le sujet de ce cours fait partie du domaine plus large de la « théorie de la calculabilité ». Cette dernière est considérée, de pair avec la théorie des language formels, comme étant la base de l'informatique théorique. En bref, le but de ce cours est de fournir une compréhension des possibilités et limites fondamentales des ordinateurs à travers une étude mathématique précise. Nous considérerons également les implications pratiques de ces limites. La calculabilité est l'étude des problèmes calculables et des modèles mathématiques qui nous permettent de les exprimer. Les automates finis sont un modèle formel de base de la calculabilité.

Nous verrons qu'il existe des problèmes pour lequels il n'y aura jamais aucune solution algorithmique. La découverte de l'existence de ces problèmes intrinséquement insolubles a été un des grand achèvements des mathématiques du vingtième siècle.

Rapidement, l'objet d'étude de la théorie de la calculabilité est la définition précise de la notion informelle d'algorithme et la caractérisation des problèmes qui peuvent (ou, de manière plus intriguante, ne peuvent pas) être résolus par un algorithme. Au cours du developpement de cette théorie, nous allons aborder des sujets tels que :

  • Introduction aux automates finis et aux langages formels.
  • Introduction à la hiérarchie de Chomsky
  • Modèles de description et exécution des algorithmes. Machines de Turing , fonctions récursive et ensembles récursivement dénombrables, (lambda calcul).
  • Concepts de calculabilité: thèse de Church-Turing.
  • Problèmes indécidables: le problème de l'arrêt, ...

Pour une excellente description alternative de ce cours, je recommande fortement la préface de « Computers Ltd.: What They Really Can't Do » Oxford University Press par David Harel (si vous desirez lire ce livre consultez cette critique du livre dans Plus magazine).

A la fin de ce cours, l'étudiant devrait être capable de

  • Donner un modèle mathématique aux algorithmes en utilisant, par exemple, une machine de Turing.
  • Formuler et de prouver des propositions sur la calculabilité de problèmes.

Pour la complexité et les languages formels, référez vous à la seconde partie du cours intitulée « Langages Formels ». En résumé, la théorie de la calculabilité parle des problèmes qui peuvent être résolus (ou non) algorithmiquement, alors que la théorie de la complexité se donne pour but de caractériser les problèmes pour lesquels il existe une solution algorithmique efficace par rapport à sa consommation en temps et en espace.

Le cours est constitué d'une série de 28 séances agendées selon cet horaire.

Ce cours suppose une connaissance de base des mathématiques discrètes, tel que celles utilisées dans des cours comme « Logique élémentaire ». Ceux d'entre vous qui souhaiteraient rafraîchir leur mémoire ou qui ne sont pas confiants dans leur compréhension de ces bases sont invités à consulter les deux ouvrages suivants:

  • Chapter Zero - Fundamental Notions of Abstract Mathematics de Carol Schumacher. Addison Wesley, 2001, ISBN 0-201-43724-4. 232 pages.
  • Concrete Mathematics de Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Addison Wesley, 1994, ISBN 0-201-55802-5, 656 pages.

Voici deux références sur la notion de preuve

Ce cours est donné sous cette forme pour la première fois; il n'y a donc pas de polycopié. Malheureusement, il n'existe pas encore de livre en français susceptible de fournir une base appropriée au cours de la manière dont nous voulons le donner. C'est pourquoi nous utiliserons un livre écrit en anglais comme support principal :

Nour faisons aussi référence à certains chapitre de:
  • Introduction to the Theory of Computation de Michael Sipser. PWS Publishing Company, 1997, 396 pages.
  • Automata & Computability de Dexter Kozen, Springer-Verlag, 1997, ISBN 0-387-94907-0, 400 pages.

Si vous souhaitez lire des écrits français, vous pouvez consulter les deux références données ci-dessous. Notez cependant qu'ils ne couvrent pas exactement tout ce que nous allons faire et que nous ne pouvons dès lors pas indiquer les correspondances entre ces sources et le livre principal.

Pour les alémaniques, nous pouvons recommander:

  • Theoretische Informatik - kurzgefaßt de Uwe Schöning. Spektrum Akademischer Verlag, 1995, ISBN 3-86025-711-0. 188 Seiten.

Comme matériel supplémentaire de lecture sur l'informatique en général nous vous recommandons fortement,

Autre matériel de cours (rassemblé par Luca Aceto, en anglais)

Pour quelques conseils sur la manière d'apprendre la substance de ce cours (et en fait de n'importe quel cours), vous pouvez consulter les transparents de l'exposé intitulé « Psychologists' tips on how and how not to learn » de Wilfrid Hodges. Essayez de réfléchir sur ses suggestions et de les comparer avec votre manière de travailler. Une autre lecture intéressante est « How to Read Mathematics » par Shai Simonson et Fernando Gouveau --- une collection utile et réaliste de suggestions sur la manière de lire et d'apprendre les mathématiques.

Chaque semaine, nous vous donnerons quelques exercices. Nous vous conseillons bien évidement de prendre le temps de les résoudre... Ils seront d'une difficulté variée, mais ils seront tous « faisables ». Ils contribueront fortement — vous vous en doutez — à votre compréhension des sujets abordés dans le cours.

Le meilleur conseil que nous puissions vous donner est de les résoudre par vous même et d'être sûr de comprendre les solutions dans le cas où nous vous les donnerons sur un plateau. Surtout, n'abandonnez pas si vous n'arrivez pas à résoudre un problème immédiatement. La résolution d'un problème est souvent une question d'endurance et de créativité. Nous vous encourageons à travailler en groupes. Surtout, essayez d'avoir un regard critique sur vos solutions. Vous n'aurez peut être pas besoin de tout le matériel couvert par ce cours dans vos futures carrières, mais avoir une attitude analytique et critique vous sera certainement d'une grande aide.

Les exercices ne sont pas notés. Un corrigé sera rendu accessible.

A chaque cours nous associerons une heure d'exercices en salle, généralement de 15h15 à 16h00 après les deux heures de théorie. Durant ces exercices, vous pouvez,

  • bénéficier de nos commentaires sur vos solutions des exercices de la semaine précédente.
  • bénéficier de conseils et d'explications sur les exercices de la semaine courante
  Examen

L'examen est un écrit, il aura lieu à la session de printemps 2005 (entre le 7 et le 28 février). Une session de réponses aux questions sera organisée pendant la dernière leçon du cours.