Info

• Cours : Paolo Tranquilli
• TD : Adrien Friggeri
• Liste de diffusion : intro.info.ixxi@listes.ens-lyon.fr (archives) (inscription)
• Horaires :
  • Cours : Mardi 13h30-15h30 (sauf le 12/10 : 10h15-12h15)
  • TD: Mardi (28/09, 26/10, 09/11) 15h30-17h30 + mardi 12/10 13h30-15h30 + mardi 23/11 10h15-12h15
  • Les horaires et la répartition entre cours et TDs sont susceptibles de changement, dûment communiqué

Cours

• 1. [14/09] Présentation du cours. Petit historique. (transparents)
• 2. [21/09] Notions d'ensembles et dénombrabilité. (notes)
• 3. [28/09] Mots, langages, automate finis. (transparents)
• 4. [05/10] Automates finis déterministes et non-déterministes, expressions régulières.
• 5. [19/10] Lemme de l'étoile, machines de Turing. (simulateur de machines de Turing, avec quelques exemples)

TDs

Bibliographie

• Micheal Sipser, Introduction to the Theory of Computation
• John E. Hopcroft, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation
• Douglas R. Hofstadter, Gödel Escher Bach, an eternal golden braid
• wikipedia.org