Foundation of computing

Foundation of computing

8KUAEN50

ECTS

2

SEMESTRE

S8

CM

TD

TP

EI

Travail personnel

7h

14h

0h

Langues d'enseignement

Français

Responsable(s)

Jean-Yves MARION

Mots clefs

Automates, grammaire, calculabilité, compilation

Prérequis

Mathématiques

Objectif pédagogique

Ce cours présente les concepts de base de la théorie des langages, de la programmation et de la compilation, et permet à la fois de comprendre sur quoi reposent les techniques développées aujourd’hui et à la fois de comprendre leurs limites.

Organisation et contenus

Ce cours s’articule autour de trois notions-clés :

1/ Les langages réguliers et les automates

2/ Les langages algébriques et les grammaires

3/ Les langages décidables et indécidables

Compétences

Niveaux

Description et verbes opérationnels

Connaître

Les concepts fondamentaux de l'informatique comme les langages, les modèles de calcul, les automates, les grammaires, la calculabilité, l'indécidabilité, le théorème de Rice.

Comprendre

Le lien entre langages et automates, déterminisme vs non-déterminisme, automate minimale.
La notion de grammaire et de systèmes de production (réécriture).
La notion de modèle de calcul, et comprendre ce qui est calculable et ce qui ne l’est pas.

Appliquer

Informatique, automatique, linguistique et tous les systèmes à états et à transitions.

Analyser

Synthétiser

Évaluer

Contributions aux Objectifs de Développement Durable des Nations Unies