Cette UE vise à initier les étudiantes aux divers niveaux de complexité d'un calcul ou une décision, ainsi qu'aux différentes modalités de décision (décision ou semi-décision, déterministe ou non). Cela se fait de plusieurs manières : d'abord par la distinction entre fonction récursive primitive et fonction mu-récursive (illustrée par la fonction d'Ackermann-Péter et le problème de l'hydre), ensuite par les différents niveaux de généralité de langages (régulier, algébrique, récursif, récursivement énumérable) et les outils correspondants (automate fini, grammaire algébrique, machine de Turing). Enfin on introduira le non-déterminisme et la complexité au sens de la machine de Turing, en particulier la décision non-déterministe, les classes P, NP et EXP.

À l'issue de cette UE un étudiant devrait savoir :
- distinguer récursion primitive et mu-récursion ;
- manipuler les expressions régulières, automates finis, grammaires algébriques et machines de Turing ;
- ce que signifie la décision non-déterministe ;
- reconnaître des problèmes de classe P, NP ou EXP.

À l'entrée de cette UE, une étudiante devrait comprendre la notion d'algorithme et calcul en informatique, et connaître la machine de Turing comme modèle de base d'un algorithme (cf. UE "Modèles de calcul" en S2).