Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : INF4223  Gr. 01
Titre : Langages formels
Session : Hiver 2016   Horaire et local
Professeur : Godon, Maxime
1. Description du cours paraissant à l'annuaire :

Objectifs

Introduire l'étudiant aux différents modèles de calcul. Familiariser l'étudiant à la théorie des langages formels. Faire comprendre les limitations des ordinateurs.

Contenu

Langages réguliers et automates finis. Langages hors contexte et automates à pile. Grammaires contextuelles. Hiérarchie de Chomsky. Machine de Turing. Hypothèse de Church. Calculabilité et déterminisme. Problèmes indécidables.
2. Objectifs spécifiques du cours :
  1. Initier l'étudiant aux fondements théoriques de l'informatique ;
  2. Le familiariser avec la théorie des langages formels et à son application à la construction des logiciels, des langages de programmation et ses compilateurs ;
  3. Familiariser l'étudiant avec les limites posées par les ordinateurs contemporains: introduire la classe de problèmes indécidables (impossibles à résoudre) et la classe de fonctions incalculables. Problème de déterminisme en informatique. L'étudiant se rendra compte de ce qui est possible et de ce qui n'est pas possible de réaliser à l'aide des ordinateurs.
3. Stratégies pédagogiques :
  • Cours magistraux
  • Séances d'exercices
  • Devoirs (2)
4. Heures de disponibilité ou modalités pour rendez-vous :
  • Les lundis, entre 15:45 et 18:45 heures (durant les cours)
  • Les jeudis, entre 16:00 et 18:00 heures (durant les séances d'exercices)
  • Rendez-vous par courriel à l'adresse : maxime.godon@uqo.ca
5. Plan détaillé du cours sur 15 semaines :
Semaine Thèmes Dates
1   
  • Préliminaires
  • Alphabets
  • Langages
  • Opérations sur symboles et langages
  • Exercices

    • Séance d'exercices 1 (21 janvier 2016) : Opérations sur les symboles et langages.

 11 jan. 2016 
2   
  • Matrices de transition
  • Automates finis non déterministes
  • Détermination d'automates finis
  • Exercices

    • Séance d'exercices 2 (28 janvier 2016) : Détermination des automates finis.

 18 jan. 2016 
3   
  • Minimisation d'automates finis déterministes
  • Exercices

    • Séance d'exercices 3 (4 février 2016) : Minimisation des automates finis. Construction des automates finis à partir des expressions régulières.

 25 jan. 2016 
4   
  • Lemmes de pompage pour langages réguliers
  • Exercices

    • Séance d'exercices 4 (11 février 2016) : Lemme de pompage.

 01 fév. 2016 
5   
  • Équivalences d'automates finis et expressions régulières
  • Passage des automates finis aux expressions régulières

    • Séance d'exercices 5 (18 février 2016) : Équivalences d'automates finis et expressions régulières.

 08 fév. 2016 
6   

    Mi-examen (1 heure)

  • Grammaire hors-contexte
  • Dérivations et arbres de dérivation

    • Séance d'exercices 6 (25 février 2016) : Introduction aux grammaires hors-contexte.

 15 fév. 2016 
7   
  • Formes normales
      • -Forme normale de Chomsky
      -Forme normale de Greiback

    Séance d'exercices 7 (10 mars 2016) : Formes normales.

 22 fév. 2016 
8    Semaine d'études 29 fév. 2016 
9   
  • Automates à pile (AP)
  • Analyse syntaxique descendante et ascendante
  • Exercices

    • Séance d'exercices 8 (17 mars 2016) : Automates à pile.

 07 mars 2016 
10   
  • Automates à pile déterministes
  • Propriétés des langages hors-contexte
  • Lemme de pompage
  • Langages réguliers et langages hors-contexte (LHC)

    • Séance d'exercices 9 (24 mars 2016) : Lemme de pompage.

 14 mars 2016 
11    Examen mi-session 21 mars 2016 
12   
  • Congé férié : Lundi de Pâques

    • Séance d'exercices 10 (31 mars 2016) : À déterminer.

 28 mars 2016 
13   
  • Propriétés de fermeture
  • Algorithmes de décision pour LHC non-déterministes
  • Machines de Turing
  • Langages récursifs et récursivement énumérables
  • Machine de Turing comme un calculateur de fonctions entières
  • Modifications de machines de Turing. Machines de Turing non-déterministes
  • Hypothèse de Church
  • Hiérarchie de Chomsky

    • Séance d'exercices 11 (7 avril 2016) : Machine de Turing.

 04 avr. 2016 
14   
  • Introduction aux problèmes indécidables
  • Problèmes indécidables et machines de Turing ; Problème d'arrêt
  • Problème de correspondance de Post
  • Problème indécidables pour langages hors-contexte
  • Révision

    • Séance d'exercices 12 (14 avril) : Révision.

 11 avr. 2016 
15    Examen final. 18 avr. 2016 
6. Évaluation du cours :
  • Devoirs : 10 % (5 % chacun)
  • Mi-examen : 15 %
  • Examen intra : 35 %
  • Examen final : 40 %
7. Politiques départementales et institutionnelles :
8. Principales références :
Bibliographie de base
  1. CZYZOWICZ, J.; Langages formels, INF 4223 (notes de cours), UQO, septembre 2011

Bibliographie de références

  1. SIPSER, M.; Introduction to the Theory of Computing, International Thomson Publishing, 2005
  2. COHEN, D.; Introduction to Computer Theory, John Wiley & Sons, 1996
  3. HOPCROFT, J.E. MOTWANI, R. & ULLMAN, J.D.; Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2006
  4. FLOYD, R. & BEIGEL, R.; Le langage des machines: introduction à la calculabilité et aux langages formels, International Thomson Publishing France, 1995
  5. BROOKSHEAR, J.G.; Theory of computation: formal languages, automata, and complexity, Benjamin/Cummings, 1989
  6. LEWIS, H.R. & PAPADIMITRIOU, C.H.; Elements of the Theory of Computation, Prentice-Hall, 1997

9. Page Web du cours :
https://moodle.uqo.ca