Fondements de l'informatique 4

Mettre en avant deux aspects complémentaires et fondamentaux de la modélisation, de la mise en œuvre du calcul au premier ordre et de la caractérisation du résultat attendu selon deux points de vue :
(i) fonctionnel (fonctions récursives primitives, point fixe...)
(ii) systèmes à base de règles (terminaison, convergence, forme normale...)
Ces deux points de vue permettent de mieux appréhender les concepts fondamentaux du calcul et d’en aborder les
propriétés essentielles (correction, complétude et terminaison).

Notions et contenus
Fondements 1,2,3
Mathématiques discrètes
Ordres, ensembles, fonctions, logique propositionnelle, logique du premier ordre.

Compétences
- Comprendre, Analyser, Modéliser, Formaliser,
- Raisonner

Ressource en ligne disponibles
Numéro de cours sur Moodle - 10529

Modéliser et formaliser un processus de calcul

- Term Rewriting and All That, Franz Baader, Tobias Nipkow, Cambridge University Press, 1999
- Logique, réduction, résolution, R. Lalement, Masson 1990
- Résolution d’équations dans les langages d’ordre 1, 2, ..., omega, G. Huet, 1976 http://gallium.inria.fr/~huet/PUBLIC/Huet1976.pdf      - Term Rewriting Systems and Algebra,P. Lescanne, 7th International Conference on Automated Deduction, Lecture Notes in Computer Science 170, pp 166—174, Springer, 1984.