Abstract FR:

Nous etudions dans cette these la maniere dont un algorithme ecrit sur sa sortie en fonction de ce qu'il a deja lu sur ses entrees (ce qu'on appelle comportement intentionnel). Ce travail complete des travaux inities par l. Colson et t. Coquand qui ont etudie certains systemes fonctionnels. Nous etudions le comportement intentionnel des algorithmes definissables dans differents langages: le langage de la recursion primitive (pr), le langage de la recursion avec substitution de parametres (prv) et le langage de la recursion sur les listes (prl). Nous donnons une caracterisation complete de la classe des fonctions qui sont le comportement intentionnel d'algorithmes pr et nous montrons que l'on obtient toutes les fonctions primitives recursives (p. R) unaires croissantes ainsi qu'une large classe de fonctions p. R. Sequentielles comme comportements intentionnels de prv et prl. Nous donnons enfin, differentes inclusions concernant les comportements de ces langages. Ce travail a ete mene en etudiant la semantique denotationnelle de ces differents langages et en implantant les differents algorithmes dans le langage fonctionnel haskell