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).
Exigences de qualification pour l'enseignement
Corps professionnel
Aucun
Autre(s) exigence(s)
Aucune
CAFF
6402 - Informatique théorique