INF1723 - Théorie des langages et calculabilité

Scolarité

Premier cycle - 3,0 crédit(s)

Département

Département d'informatique et d'ingénierie

Objectifs

Au terme de ce cours, l'étudiant.e sera initié aux différents modèles de calcul; sera familier avec la théorie des langages formels; aura une compréhension des limitations des ordinateurs.

Contenu

Langages réguliers et automates finis. Langages hors contexte et automates à pile. Grammaires contextuelles. Hiérarchie de Chomsky. Machines de Turing. Hypothèse de Church. Calculabilité et déterminisme. Classes de complexité. Problèmes indécidables. Introduction à la calculabilité quantique. Ce cours comporte des séances obligatoires de travaux dirigés (TD).

Préalables

Exigences de qualification pour l'enseignement

Diplôme(s)
Aucun
Expérience
Aucune
Corps professionnel
Aucun
Autre(s) exigence(s)
Aucune

CAFF

Aucun