Exercices de programmation fonctionnelle en OCaml : une approche pédagogique par l'algorythmique, la preuve et la complexité

Auteur(s) :

Carrier, Fabienne Découvrir l'auteur

Résumé

Une quarantaine d'exercices classés en plusieurs catégories en fonction de la nature des données manipulées (entiers, listes, arborescences). Plusieurs solutions sont systématiquement proposées avec, pour chacune, une analyse des temps de calcul.

Autre(s) auteur(s)
- Mounier, Laurent
- Lafourcade, Pascal
Éditeur(s)
- Ellipses
Date
- DL 2014
Notes
- Avant-titre : "Programmation". - Niveau A : IUT, BTS, 1er cycle
- Contient un "flashcode" permettant d'accéder à un contenu via Internet
Langues
- Français
Description matérielle
- 1 vol. (260 p.) : couv. ill. ; 26 cm
Collections
- Technosup (Paris)
Sujet(s)
ISBN
- 978-2-7298-8788-9
Indice
- 681.25(07) Autres langages informatiques. Manuels
Quatrième de couverture
- L'ouvrage : niveau A (IUT - BTS - 1^er cycle)
  Ce livre d'exercices corrigés est destiné aussi bien aux étudiants de premier cycle en informatique qu'aux enseignants intéressés par la programmation fonctionnelle.
  L'ouvrage aborde notamment les notions de correction, de complexité et d'efficacité d'un algorithme fonctionnel, à travers les solutions détaillées d'une quarantaine d'exercices. Pour chacun de ces exercices, plusieurs solutions sont systématiquement proposées. Pour chaque solution, une analyse des temps de calcul et une preuve de correction sont entièrement rédigées.
  Les exercices traités sont classés en plusieurs catégories en fonction de la nature des données qu'ils manipulent : entiers, listes, arborescences. Cette distinction permet de mettre en avant un mode de programmation et de raisonnement guidé par la structure des données, si naturel en programmation fonctionnelle.
  Si les exercices proposés peuvent sembler simples et classiques au premier abord, ils ont été choisis pour permettre, par l'étude de leurs solutions, une découverte en profondeur de la programmation fonctionnelle, ce qui constitue l'originalité du livre.
Tables des matières
- - Programmation
  - Exercices de programmation fonctionnelle en OCaml
  - Une approche pédagogique par l'algorithmique, la preuve et la complexité
  - Fabienne Carrier
  - Pascal Lafourcade
  - Laurent Mounier
  - ellipses
  - I Définitions et notations9
  - 1 Notations et rappels en OCaml9
  - 2 Preuve de terminaison et de correction12
  - 3 Complexité d'une fonction15
  - 4 Notation des fonctions26
  - II Fonctions sur des entiers27
  - Exercice 1 Somme des n premiers entiers27
  - Exercice 2 Somme des n premiers entiers impairs27
  - Exercice 3 Somme des entiers entre p et q27
  - Exercice 4 Dernier chiffre de 2ⁿ27
  - Exercice 5 Y a-t-il un 0 dans la représentation binaire d'un entier ?28
  - Exercice 6 Division euclidienne28
  - Exercice 7 Factorielle28
  - Exercice 8 Coefficients binomiaux28
  - Exercice 9 Puissance d'un entier28
  - Exercice 10 Puissance d'une fonction28
  - Exercice 11 Suite de Fibonacci29
  - Exercice 12 Suite des nombres de Catalan29
  - Exercice 13 Pgcd de deux entiers29
  - Exercice 14 Suite de Syracuse29
  - Solution 1 Somme des n premiers entiers30
  - Solution 2 Somme des n premiers entiers impairs34
  - Solution 3 Somme des entiers entre p et q38
  - Solution 4 Dernier chiffre de 2ⁿ43
  - Solution 5 Y a-t-il un 0 dans la représentation binaire d'un entier ?46
  - Solution 6 Division euclidienne49
  - Solution 7 Factorielle51
  - Solution 8 Coefficients binomiaux53
  - Solution 9 Puissance d'un entier60
  - Solution 10 Puissance d'une fonction67
  - Solution 11 Suite de Fibonacci73
  - Solution 12 Suite des nombres de Catalan86
  - Solution 13 Pgcd de deux entiers93
  - Solution 14 Suite de Syracuse97
  - III Fonctions sur des listes99
  - Exercice 15 Longueur d'une liste99
  - Exercice 16 Somme des entiers d'une liste99
  - Exercice 17 La fonction fold99
  - Exercice 18 La fonction map100
  - Exercice 19 La fonction find100
  - Exercice 20 Maximum d'une liste non vide d'entiers100
  - Exercice 21 Nombre d'occurrences d'un élément dans une liste100
  - Exercice 22 Y a-t-il plus de 0 que de 1 dans une liste ?100
  - Exercice 23 Concaténer deux listes101
  - Exercice 24 Renverser une liste101
  - Exercice 25 Une liste d'entiers est-elle croissante ?101
  - Exercice 26 Plus longue sous-suite croissante101
  - Exercice 27 Égalité de séquences101
  - Exercice 28 Une liste est-elle un palindrome ?101
  - Exercice 29 Tri par insertion d'une liste102
  - Exercice 30 Tri par sélection d'une liste102
  - Exercice 31 Tri rapide d'une liste (Quicksort)102
  - Exercice 32 Tri fusion d'une liste102
  - Solution 15 Longueur d'une liste103
  - Solution 16 Somme des entiers d'une liste105
  - Solution 17 La fonction fold108
  - Solution 18 La fonction map115
  - Solution 19 La fonction find118
  - Solution 20 Maximum d'une liste non vide d'entiers121
  - Solution 21 Nombres d'occurrences d'un élément dans une liste125
  - Solution 22 Y a-t-il plus de 0 que de 1 dans une liste ?130
  - Solution 23 Concaténer deux listes135
  - Solution 24 Renverser une liste142
  - Solution 25 Une liste d'entiers est-elle croissante ?147
  - Solution 26 Plus longue sous-suite croissante156
  - Solution 27 Égalité de séquences163
  - Solution 28 Une liste est-elle un palindrome ?167
  - Solution 29 Tri par insertion d'une liste175
  - Solution 30 Tri par sélection d'une liste181
  - Solution 31 Tri rapide d'une liste (Quicksort)188
  - Solution 32 Tri fusion d'une liste198
  - IV Fonctions sur des arbres binaires211
  - Exercice 35 Nombre de noeuds d'un arbre binaire211
  - Exercice 36 Hauteur d'un arbre binaire ?211
  - Exercice 37 Un élément est-il présent dans un arbre binaire ?211
  - Exercice 38 Nombre de noeuds d'un niveau donné212
  - Exercice 39 Un arbre binaire est-il équilibré ?212
  - Exercice 40 Construire le symétrique d'un arbre212
  - Exercice 41 Ordre supérieur et arbres212
  - Solution 35 Nombre de noeuds d'un arbre binaire214
  - Solution 36 Un élément est-il présent dans un arbre binaire ?220
  - Solution 37 Hauteur d'un arbre binaire ?226
  - Solution 38 Nombre de noeuds d'un niveau donné231
  - Solution 39 Un arbre binaire est-il équilibré ?237
  - Solution 40 Construire le symétrique d'un arbre243
  - Solution 41 Ordre supérieur et arbres245
  - Bibliographie257
  - Index258
Origine de la notice:
- FR-751131015