Next:
Introduction
DEUG 1
e
re
année - MIAS 1 et MASS 1
UE4 - Informatique 2
PROGRAMMATION FONCTIONNELLE EN SCHEME
NOTES DE COURS
Introduction
Syntaxe et expressions
1. Expressions
2. La syntaxe de Scheme
2.1 Les expressions atomiques
2.2 Les expressions composées
3. Évaluation des expressions
3.1 Les constantes
3.2 Les symboles
3.2.1 Définition de variables
3.2.2 Évaluation
3.3 Les expressions composées
3.4 Blocage de l'évaluation
Fonctions - Environnements
4. Les fonctions
4.1 Notion de type
4.1.1 Le type
Booléen
4.1.2 Le type
Entier
4.1.3 Le type
Rationnel
4.1.4 Le type
Réel
4.1.5 Le type
Chaîne
4.2 Spécification d'une fonction
4.3 Représentation d'une fonction
4.4 Évaluation de l'appel d'une lambda-expression
4.5 Nomage d'une lambda-expression
5. Définition, évaluation et environnement
5.1 Définition d'un environnement local
5.2 Évaluation d'un
let
5.3 La forme spéciale
let*
5.4 Définition locale de fonction
6. Structures de contrôle conditionnelles
6.1 Prédicats
6.2 Opérateurs booléens
6.3 Expressions conditionnelles
6.3.1 Le
if
6.3.2 Le
cond
, expression conditionnelle multiple
Les listes
7. Paires pointées et listes
7.1 le Type
Paire
7.2 Le type
Liste
7.3 Liens entre les paires pointées et les listes
7.4 Représentation graphique des listes :
Récursivité
8. Récursivité et récurrence
8.1 Un exemple en mathématiques
8.2 Traduction en scheme
9. Fonction récursives
9.1 Questions à se poser avant d'écrire une fonction récursive :
9.2 Fonctions récursives sur les listes
9.3 Vérifications minimum à faire lorsqu'on écrit une fonction récursive
Notion de complexité
10. Un exemple de comparaison d'algorithmes
10.1 Une première version
10.2 Une autre version
10.3 Comparons l'exécution des deux fonctions
11. Notation pour la complexité
12. Un exemple de récursivité quadratique
13. Un exemple de récursivité arborescente
Abstraction des données
14. Types abstraits de données
14.1 Comment définit-on un TAD ?
14.2 Utilisation d'un TAD
14.3 Un exemple : le TAD doublet
14.4 Deux TAD classiques : les piles et les files
14.4.1 Les piles d'entiers
14.4.2 Les files d'entiers
Programmation d'ordre supérieur
15. Des fonctions en arguments
15.1 Exemples
15.2 Abstraction
15.3 La fonction
map
16. Des fonctions comme résultat
Preuves de programme
17. Principe général
18. Étude d'un cas
18.1 Preuve de l'arrêt
18.2 Preuve de la correction
19. Indécidabilité du problème de l'arrêt
Annexe
Regis Girard
2000-02-23
