Informatique Théorique 2

Licence 3 Informatique - 2022/2023

Questions ?

Contacter l'équipe enseignante

But

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

haut

Équipe d'enseignants

Sara Tari

Sébastien Verel

Pour contacter un des intervenants : contacts. Vous pouvez contacter l'équipe pour tout ce qui concerne cet enseignement et votre orientation.

haut

Evaluation

L'évaluation comprend :

  • 25%, interro 1,
  • 25%, interro 2, le 14/12/2022, durée 45 min, sur objectifs 19 à 30,
  • 50%, examen terminal, le 06/01/2023, 2h, sur l'ensemble des objectifs de 1 à 35.



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 "grand 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 correction
07 Test et vérification d'algorithmes 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

dernière modification : 6 novembre 2022