| ||||
Sigle : INF4223 Gr. 01 Titre : Langages formels Session : Automne 2017 Horaire et local Professeur : Godon, Maxime | ||||
1. Description du cours paraissant à l'annuaire : | ||||
ObjectifsIntroduire l'étudiant aux différents modèles de calcul. Familiariser l'étudiant à la théorie des langages formels. Faire comprendre les limitations des ordinateurs.ContenuLangages réguliers et automates finis. Langages hors contexte et automates à pile. Grammaires contextuelles. Hiérarchie de Chomsky. Machines de Turing. Hypothèse de Church. Calculabilité et déterminisme. Problèmes indécidables. Ce cours comporte des séances obligatoires de travaux dirigés (TD) de deux heures par semaine. | ||||
2. Objectifs spécifiques du cours : | ||||
| ||||
3. Stratégies pédagogiques : | ||||
| ||||
4. Heures de disponibilité ou modalités pour rendez-vous : | ||||
| ||||
5. Plan détaillé du cours sur 15 semaines : | ||||
Semaine | Thèmes | Dates | ||
1 |
Séance d'exercices 1 (13 septembre 2017) : Opérations sur les symboles et langages. |
11 sept. 2017 | ||
2 |
Séance d'exercices 2 (20 septembre 2017) : Détermination des automates finis. |
18 sept. 2017 | ||
3 |
Séance d'exercices 3 (27 septembre 2017) : Minimisation des automates finis. Construction des automates finis à partir des expressions régulières. |
25 sept. 2017 | ||
4 |
Séance d'exercices 4 (4 octobre 2017) : Lemme de pompage. |
02 oct. 2017 | ||
5 | Semaine d'études | 09 oct. 2017 | ||
6 |
Séance d'exercices 5 (18 octobre 2017) : Équivalences d'automates finis et expressions régulières. |
16 oct. 2017 | ||
7 | Examen de mi-session | 23 oct. 2017 | ||
8 |
Séance d'exercices 6 (1er novembre 2017) : Introduction aux grammaires hors- contexte. |
30 oct. 2017 | ||
9 |
Séance d'exercices 7 (8 novembre 2017) : Formes normales. |
06 nov. 2017 | ||
10 |
Séance d'exercices 8 (15 novembre 2017): Automates à pile. |
13 nov. 2017 | ||
11 |
Séance d'exercices 9 (15 novembre 2017) : Lemme de pompage. |
20 nov. 2017 | ||
12 |
Séance d'exercices 10 (29 novembre 2017): Révision: langages hors-contexte |
27 nov. 2017 | ||
13 |
Séance d'exercices 11 (6 décembre 2017) : Machine de Turing. |
04 déc. 2017 | ||
14 |
Séance d'exercices 12 (13 décembre 2017) : Révision. |
11 déc. 2017 | ||
15 | Examen final. | 18 déc. 2017 | ||
6. Évaluation du cours : | ||||
| ||||
7. Politiques départementales et institutionnelles : | ||||
| ||||
8. Principales références : | ||||
Bibliographie de base
Bibliographie de références
| ||||
9. Page Web du cours : | ||||
https://moodle.uqo.ca |