Outils formels de l'informatique

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

Parcours : tronc commun (parcours général et parcours I.A.).

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.

Objectifs

À la fin de ce cours, l’étudiant doit être capable de :

• faire un raisonnement par induction simple ou structurelle ;
• résoudre des équations de récurrence linéaires et certaines classes d’équations non linéaires, et faire le lien avec la complexité des algorithmes ;
• traduire un énoncé en langage naturel en logique du premier ordre, et comprendre les notions de modèle, de sémantique et de conséquence logique ;
• faire une démonstration élémentaire.

Plan du cours

1. Ensembles, dénombrabilité, mots
2. Relations, fonctions et ordres
3. Induction
4. Dénombrement
5. Récurrence ; récurrence et séries formelles
6. Logique des propositions
7. Logique des prédicats
8. Automates finis et expressions régulières

Modalités de contrôle des connaissances

Un contrôle intermédiaire compte pour 50 % de la note finale.