Acquis d'apprentissage visés
- Maîtriser les paradigmes fondamentaux de la programmation, des langages et des algorithmes pour concevoir et développer des applications sur tout type d’environnement.
- Identifier, classer les problèmes selon leur complexité (P, NP, NP-complet) et choisir des stratégies algorithmiques adaptées.
Prérequis
Modules Systèmes et réseaux et Développement des semestres précédents.
Programme
- Fondements (Alphabet, mot, langage, Hiérarchie de Chomsky, Automates finis, ...) et langages réguliers
- Langages hors contexte (Grammaires hors contexte, automates à pile, ...), analyse lexicale et syntaxique
- Calculabilité et complexité (Machines de Turing, indécidabilité et complexité, ...)
Modalités d'évaluation
Deux contrôles continus au minimum, les TPs et un projet.
Bibliographie
"Michael Sipser — Introduction to the Theory of Computation — Cengage Learning John Hopcroft — Introduction to Automata Theory, Languages, and Computation — Pearson"
Supports
Diaporamas, fiches de travaux dirigés et de travaux pratiques.