Outils formels de l'informatique

Initiation à l'étude des fondements théoriques de l'informatique.

Description

Ce cours est une initiation au formalisme et aux méthodes utilisées couramment en sciences informatiques. Le monde de l’informatique est discret, hiérarchisé et symbolique donc le cours débute par la présentation des notions de dénombrabilité, de relations d’ordre et de mots sur un alphabet. Le cours présente ensuite les principes d’induction afin d’étudier les comportements récursifs des algorithmes ou la génération récursive des structures de données. L’informatique touche également à la mécanisation du raisonnement, d’où l’introduction de la logique des propositions et de celle des prédicats, puis des algorithmes afférents. Une première façon de distinguer la syntaxe de la sémantique. Le cours présente ensuite les propriétés des modèles statiques que sont les arbres et les graphes, ainsi que des modèles dynamiques comme les automates. Enfin, le cours sensibilise aux performances des algorithmes. On commence par présenter les suites récurrentes et la résolution des équations de récurrence en vue de leurs applications au calcul de la complexité d’un algorithme.