Informatique Théorique 2

But

Le but principal de cette UE est d'introduire aux fondements de l'informatique et d'introduire à la compilation.

haut

Evaluation

L'évaluation comprend :

• 20%, interro 1, 13/10/2021 à 10h30, 45 min, sur objectifs 1 à 16,
• 30%, interro 2, 26/10/2020 à 8h30, 45 min, sur objectifs 19 à 25,
• 50%, examen terminal, 26/11/2021 à 9h00, 2h, sur l'ensemble des objectifs.


Cette UE compte pour 3 crédits ECTS.


haut

Objectifs

liste complète des objectifs du cours :

1. Savoir définir mot et langage
2. Savoir écrire une expression réguliére simple
3. Connaitre les opérations algébriques sur les langages
4. Savoir définir langage rationnel
5. Savoir définir le langage reconnu par un automate fini déterministe
6. Savoir construire un automate fini déterministe reconnaissant un langage
7. Savoir écrire l'expression régulière du langage reconnu par un automate fini déterministe
8. Connaitre la définition d'un automate fini non-déternimiste
9. Savoir déterminiser un automate
10. Savoir construire un automate à état fini reconnaissant un language rationnel simple
11. Connaître le théorème de Kleene
12. Savoir définir un automate fini déterministe
13. Savoir définir un automate fini à partir d'une expression rationnelle
14. Savoir construire un automate à partir des opérations algébriques sur les langages
15. Savoir minimiser un automate fini
16. Savoir comparer deux automates finis
17. Connaitre la définition d'un automate pondéré
18. Savoir définir et interpréter un automate pondéré
19. Connaitre la définition d'une machine de Turing
20. Savoir exécuter une machine de Turing
21. Savoir définir le langage reconnu par une machine de Turing
22. Savoir définir la fonction calculée par une machine de Turing
23. Savoir définir une machine de Turing pour reconnaître un langage ou calculer une fonction
24. Connaitre la thèse de Church-Turing
25. Savoir que le problème de l'arrêt est non calculable
26. Connaitre les notions de complexité temporelle et spatiale
27. Connaitre la notation $\mathcal{O}$ et sa signification
28. Connaitre les classes de complexité
29. Savoir calculer la complexité temporelle d'un algorithme itératif
30. Savoir calculer la complexité temporelle d'un algorithme récursif simple
31. Connaitre la logique propositionnelle
32. Connaitre le problème SAT et 3-SAT
33. Savoir réduire un problème en problème SAT
34. Connaitre les définitions de P, NP et NP-complet
35. Connaitre le théorème de Cook et Levin

haut

Supports des cours et des travaux

Voici l'ensemble des supports des cours et des émoncés des travaux.

Séance	Titre	cours	fiche
01	Langage rationnel, automate fini	cours	fiche
02	Automate minimal	cours	fiche
03	Automate pondéré	cours	fiche
04	Machine de Turing	cours article de Turing, 1936	fiche correction
05	Complexité	cours	fiche correction
06	SAT et problèmes P, NP	cours	fiche

haut

Bibliographie

Quelques repères biblio- /webo- graphiques qui vont se complèter au fur et à mesure :

• Sandrine Julia, Université Côte d'Azur.
• Introduction to Automata theory, Languages, and Computation, J.Hopcroft, J.Ullman, Addison-Wesley, 1979
• Automates à états finis et langages réguliers - Rappels des notions essentielles et plus de 170 exercices corrigés, Yliès Falcone, Jean-Claude Fernandez, Dunod, 2020
• A Second Course in Formal Languages and Automata Theory, J.Shallit, Cambridge Univ.Press, 2009
• Langages formels, calculabilité et complexité, O.Carton, Vuibert, 2008
• Introduction à la calculabilité, P.Wolper, Dunod, 3e édition, 2006
• Logique et automates, P.Bellot, J.Sakarovitch, Ellipses, 1998
• Introduction to the Theory of Computation, M.Sipser, PWS publishing company, 2014
• O. Carton. Langages formels, Calculabilité et Complexité. Vuibert, 2008.
• Ch. Papadimitriou. Computational complexity. Addison-Wesley, 1995.
• M. Garey, D. Johnson. Computers and intractability. W.H. Freeman & Co, 1979.

N'hésitez pas à me proposer des livres ou cours que vous pourriez rencontrer dans vos recherches.
Vous pouvez aussi trouver beaucoup de cours en cherchant sur un moteur de recherche les mots clés suivants : "automate fini cours livre".

haut

Horaires

12h de CM, et 15h de TD.


Consulter l'emploi de la licence : ADE

haut