Licence S&T

Algorithmique et Programmation Fonctionnelle

Janvier 2004-Juin 2004

Cours

Dernière mise à jour : 15 janvier 2004

Livre de référence : "Cours d'informatique, langages et programmation" - Masson 93 (chap. 1 à 5)
13 séances de cours de 1h30.

4h30 (C1, C2, C3) Chapitres 1 et 2 du livre

1.0. Exemples introductifs
- a) moyenne olympique
- b) maximum de trois valeurs
1.1. Types et valeurs
- a) notion de type
- b) valeurs et types de base
1.2. Expressions, fonctions
- a) expressions arithmétiques
- b) expressions algébriques
- c) calcul de la valeur d'une expression
- d) calcul du type d'une expression
- e) fonctions
1.3. Composition conditionnelle
- a) la construction SELON
- b) autres formes
1.4. Nommer une expression
- a) noms locaux
- b) la construction SOIT ... DANS
- b) structure de blocs et portée des noms
1.5. Types construits
- a) terminologie
- b) le type texte
- c) produit de types
1.6. Expressions à valeurs booléennes
- a) identités remarquables
- b) opérateurs "et puis", "ou alors"
- c) expressions "selon" à valeur booléenne

6h (C4, C5, C6, C7) Chapitres 3 et 4 du livre

2.1. Notion de définition récursive
- a) définition récursive d'une entité
- b) définition récursive d'un ensemble d'entités
- c) définition récursive d'une fonction
2.2. Réalisation récursive d'une fonction
- a) méthode de développement d'une fonction récursive
- b) exemple : factorielle
- c) exemple : calcul du quotient
- d) observation de l'évaluation
- e) examen de propriétés
2.3. Entiers naturels, modèles d'analyse
- a) définitions récursives de l'ensemble des naturels
- b) exemple de fonction : l'addition
- c) modèles d'analyse
- d) exemple de fonction : la multiplication
- e) récursivité portant sur plusieurs paramètres
2.4. Séquences, modèles d'analyse
- a) le constructeur de type "séquence de"
- b) modèle d'analyse récursive
- c) récursivité sur plusieurs paramètres
2.5. Découpage d'une séquence selon une propriété
- a) principe
- b) exemple : "premier mot d'une phrase"
- c) exemple : "les mots d'une phrase"
- d) modèle de découpage selon une propriété
2.6. Séquences ordonnées
- a) principe
- b) exemples
- c) a propos de tris
- d) interclassement

4h30 (C8, C9, C10) Chapitres 5 du livre

3.1. Structure en arbre
- a) arbres n-aires
- b) différentes représentations
- c) cas des arbres binaires
- d) terminologie
3.2. Traitement d'arbres binaires
- a) définitions
- b) constructeur de type "arbre binaire de"
- c) arbres binaires non vides
- d) analyse récursive
- e) examen de propriétés
- f) parcours d'arbres
- g) recherche en arbres
- h) chemins dans un arbre

3h (C11, C12) Chapitres 9 du livre

1h30