Informatique Théorique 2

But

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

Evaluation

L'évaluation comprend :

• 50%, interro 1, 23/11/2020 à 9h, 1h30 min, sur objectifs 1 à 14,
• 50%, examen terminal, 26/01/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. Savoir définir un ensemble dénombrable
4. Savoir définir une bijection entre deux ensembles dénombrables
5. Savoir montrer qu'un ensemble est non dénombrable
6. Connaitre le cardinal de l'ensemble des partis d'un ensemble fini
7. Connaitre les opérations algébriques sur les langages
8. Savoir définir langage rationnel
9. Savoir définir le langage reconnu par un automate fini déterministe
10. Savoir construire un automate fini déterministe reconnaissant un langage
11. Savoir écrire l'expression régulière du langage reconnu par un automate fini déterministe
12. Connaitre la définition d'un automate fini non-déternimiste
13. Savoir déterminiser un automate
14. Savoir construire un automate à état fini reconnaissant un language rationnel simple
15. Connaître le théorème de Kleene
16. Savoir définir un automate fini déterministe
17. Connaitre le principe de recherche de motif par automate
18. Connaître la définition d'une grammaire
19. Savoir dessiner l'arbre de dérivation d'un mot selon une grammaire
20. Connaitre la définition d'une grammaire régulière
21. Savoir concevoir un automate fini reconnaissant le langage d'une grammaire régulière
22. Savoir définir une grammaire engendrant le même langage qu'un automate fini déterministe
23. Connaitre la classification de Chomsky des langages
24. Connaitre les définitions de clôture
25. Savoir les propriétés de clôture des langages rationnels
26. Connaitre le lemme de l'étoile
27. Savoir que le langage 0^n1^n n'est pas rationnel
28. Savoir démontrer qu'un langage n'est pas rationnel par le lemme de l'étoile
29. Savoir démontrer qu'un langage n'est pas rationnel en utilisant les propriétés de clôture
30. Savoir représenter graphiquement un mot issu d'un système de réécriture
31. Connaitre la définition d'une machine de Turing
32. Savoir exécuter une machine de Turing
33. Savoir définir le langage reconnu par une machine de Turing
34. Savoir définir la fonction calculée par une machine de Turing
35. Savoir définir une machine de Turing pour reconnaître un langage ou calculer une fonction
36. Connaitre la thèse de Church-Turing
37. Savoir que le problème de l'arrêt est non calculable
38. Connaitre les notions de complexité temporelle et spatiale
39. Connaitre la notation "grand O" et sa signification
40. Connaitre les classes de complexité
41. Savoir calculer la complexité temporelle d'un algorithme itératif
42. Savoir calculer la complexité temporelle d'un algorithme récursif simple

Supports des cours et des travaux

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

Bibliographie

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

• Sandrine Julia, Université Côte d'Azur.

Horaires

12h de CM, et 15h de TD.


Consulter l'emploi de la licence : ADE