Apprendre à programmer avec OCaml

-

Livres
443 pages
Lire un extrait
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description


Un langage de programmation moderne



La connaissance de l'algorithmique (dont le but est de choisir l'algorithme le plus élégant et le plus efficace en toute cir-constance) est ce qui distingue en premier lieu le programmeur avancé de celui qui débute. Cet ouvrage d'algorithmique fondamentale choisit le langage de programmation moderne OCaml, pris comme modèle par Microsoft pour concevoir F#, afin d'initier le lecteur à cet outil puissant alliant expressivité, performance et sûreté. OCaml est également l'un des fers de lance de l'institut de recherche public Inria depuis une vingtaine d'années.



Un livre incontournable pour débuter avec OCaml



C'est pourquoi cet ouvrage propose une véritable initiation à ce langage, à la fois aux débutants en programmation et aux programmeurs plus expérimentés qui ne le connaissent pas. À travers plus de 100 petits programmes et près de 200 exercices associés, le lecteur découvrira également les concepts fondamentaux de la programmation et du langage OCaml.



À qui s'adresse ce livre ?



Ce livre peut également servir de manuel d'initiation à la programmation OCaml pour les élèves des classes préparatoires aux grandes écoles qui ont choisi de se spécialiser en informatique - voies MPSI, MP ou MPx -, et les étudiants en informatique à l'université. En plus des passionnés d'algorithmique, il intéressera tous les développeurs avancés souhaitant se tourner vers un langage de programmation fonctionnel, tel que Scala, F#, Scheme, Lisp, etc.




  • Programmation avec OCaml


    • Environnement de travail


    • Débuter avec OCaml en programmant


    • Approfondir les concepts d'OCaml




  • Structures de données


    • Tableaux


    • Ensembles et dictionnaires


    • Files


    • Graphes


    • Classes disjointes


    • Le zipper




  • Techniques algorithmiques et applications


    • Arithmétique


    • Programmation dynamique et mémorisation


    • Algorithmes de tri


    • Algorithmes de graphes




Sujets

Informations

Publié par
Date de parution 09 octobre 2014
Nombre de visites sur la page 186
EAN13 9782212272291
Langue Français

Informations légales : prix de location à la page 0,0165 €. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Signaler un problème
Sylvain Conchon et Jean-Christophe Filliâtre
Apprendre programmer à avec OCaml
Algorithmes et structures de données
Sylvain Conchon est professeur d’informatique à l’université Paris-Sud où il enseigne la programmation et l’algorithmique avec OCaml.Jean-Christophe Filliâtreest chercheur au CNRS. Il donne par ailleurs des cours d’algorithmique à l’École polytechnique et de compilation avec OCaml à l’ENC (Ulm). Tous deux sont programmeurs OCaml depuis plus de vingt ans et ont développé de nombreux logiciels avec ce langage. Ils sont très actifs au sein de la communauté francophone des langages applicatifs et ont organisé, entre autres, les « Journées francophones des langages applicatifs ».
Un langage de programmation moderne La connaissance de l’algorithmique (dont le but est de choisir l’algorithme le plus élégant et le plus efîcace en toute cir-constance) est ce qui distingue en premier lieu le programmeur avancé de celui qui débute. Cet ouvrage d’algorithmique fondamentale choisit le langage de programmation moderne OCaml, pris comme modèle par Microsoft pour concevoir F#, aîn d’initier le lecteur à cet outil puissant alliant expressivité, performance et sûreté. OCaml est également l’un des fers de lance de l’institut de recherche public Inria depuis une vingtaine d’années.
Un livre incontournable pour débuter avec OCaml C’est pourquoi cet ouvrage propose une véritable initiation à ce langage, à la fois aux débutants en programmation et aux programmeurs plus expérimentés qui ne le connaissent pas. À travers plus de 100 petits programmes et près de 200 exercices associés, le lecteur découvrira également les concepts fondamentaux de la programmation et du langage OCaml.
À qui s’adresse ce livre ? Ce livre peut également servir de manuel d’initiation à la programmation OCaml pour les élèves des classes préparatoires aux grandes écoles qui ont choisi de se spécialiser en informatique – voies MPSI, MP ou MPx –, et les étudiants en infor-matique à l’université. En plus des passionnés d’algorithmique, il intéressera tous les développeurs avancés souhaitant se tourner vers un langage de programmation fonctionnel, tel que Scala, F#, Scheme, Lisp, etc.
Au sommaire Programmation avec Ocaml.Environnements de travail.Compilateur et interprète • Premier programme avec OCaml • Environnements de programmation • Installation de bibliothèques OCaml.Débuter avec OCaml en programmant.Années bissextiles • Méthode de Monte-Carlo • Dessin d’une cardioïde • Ensemble de Mandel-brot • Crible d’Ératosthène • Tracé de courbe • Copie d’un îchier • Renverser les lignes d’un texte • Conversion d’entiers en base quelconque • Un casse-briques sans briques • Tortue Logo • Jouer une partition de musique • Arbres quaternaires • Résoudre le problème des N reines.Approfondir les concepts d’OCaml.Algorithme de typage • Modèle d’exécution • Analyser le temps d’exécution d’un programme.Structures de données. Ta-bleaux.Tableaux redimensionnables • Tableaux de bits • Cordes • Tableaux persistants.Ensembles et diction-naires.Arbres binaires de recherche • AVL • Tables de hachage • Arbres de préîxes • Arbres de Patricia.Files.Files impératives • Files persistantes • Files de priorité impératives • Files de priorité persistantes.Graphes.Matrice d’adjacence • Listes d’adjacence • Dictionnaire d’adjacence • Comparatif.Classes disjointes.Principe • Réalisation.Le zipper.Zipper pour les listes • Zipper pour les arbres • Curseurs.Techniques algorithmiques et applications. Arithmétique.Algorithme d’Euclide • Exponentiation rapide • Calcul modulo • Calcul matriciel. Programmation dynamique et mémoïsation.Principe • Mémoïsation systématique • Différences entre mé-moïsation et programmation dynamique • Hash-consing.Algorithmes de tri.Tri par insertion • Tri rapide • Tri fusion • Tri par tas • Complexité optimale • Évaluation expérimentale.Algorithmes sur les graphes.Parcours en largeur • Parcours en profondeur • Plus court chemin • Arbre couvrant de poids minimal.
Tous les programmes de ce livre sont disponibles sur le site compagnon : http://programmer-avec-ocaml.lri.fr/
Apprendre àprogrammer avec OCaml
Chezlemêmeéditeur
Danslamêmecollection
DanslacollectionBlanche
DanslacollectionDesignweB
autresouvrages
Retrouvez aussi nos livres numériques sur http://izibook.eyrolles.com
Sylvain Conchon et Jean-Chistophe Filliâtre
Apprendre àprogrammer avec OCaml
Algorithmes et structures de données
ÉDITIONS EYROLLES 61, bd Saint-Germain 75240 Paris Cedex 05 www.editions-eyrolles.com
En application de la loi du 11 mars 1957, il est interdit de reproduire intégralement ou partiellement le présent ouvrage, sur quelque support que ce soit, sans l’autorisation de l’Éditeur ou du Centre Français d’exploitation du droit de copie, 20, rue des Grands Augustins, 75006 Paris. © Groupe Eyrolles, 2014, ISBN : 978-2-212-13678-4
À nos épouses et nos filles
Sommaire
Avant-propos. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . XI
Pģģ ģĥ Programmation avec OCaml. . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . . . . . . . . . .
ĥģ Ǻ Environnements de travail. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 1.1 Compilateur et interprète. . . . . . . . . . . . . . . . . . . . . 1.2 Premier programme avec OCaml. . . . . . . . . . . . . . . . . 1.3 Environnements de programmation. . . . . . . . . . . . . . . 1.4 Installation de bibliothèques OCaml. . . . . . . . . . . . . . .
ĥģ ǻ Débuter avec OCaml en programmant. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Années bissextiles. . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Méthode de Monte-Carlo. . . . . . . . . . . . . . . . . . . . 2.3 Dessin d’une cardioïde. . . . . . . . . . . . . . . . . . . . . . 2.4 Ensemble de Mandelbrot. . . . . . . . . . . . . . . . . . . . . 2.5 Crible d’Ératosthène. . . . . . . . . . . . . . . . . . . . . . . 2.6 Tracé de courbe. . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Copie d’un fichier. . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Renverser les lignes d’un texte. . . . . . . . . . . . . . . . . . . 2.9 Conversion d’entiers en base quelconque. . . . . . . . . . . . . 2.10 Un casse-briques sans briques. . . . . . . . . . . . . . . . . . .
1
3 3 4 5 6
7 7 15 25 29 36 42 53 60 67 76
VIII
Apprendre à programmer avec OCaml
2.11 Tortue Logo. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.12 Jouer une partition de musique. . . . . . . . . . . . . . . . . . 2.13 Arbres quaternaires. . . . . . . . . . . . . . . . . . . . . . . . 2.14 Résoudre le problème des N reines. . . . . . . . . . . . . . . . 2.15 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87 95 105 110 122
ĥģ Ǽ Approfondir les concepts d’OCaml. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .135 3.1 Algorithme de typage. . . . . . . . . . . . . . . . . . . . . . .135 3.2 Modèle d’exécution. . . . . . . . . . . . . . . . . . . . . . . .139 3.3 Analyser le temps d’exécution d’un programme. . . . . . . . . . . . . . . . . . . . . . . . . .146 3.4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .150
Ħ ģĥ Structures de données. . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
ĥģ ǽ Tableaux. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 4.1 Tableaux redimensionnables. . . . . . . . . . . . . . . . . . .153 4.2 Tableaux de bits. . . . . . . . . . . . . . . . . . . . . . . . . .159 4.3 Cordes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .168 4.4 Tableaux persistants. . . . . . . . . . . . . . . . . . . . . . . .184 4.5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .189
ĥģ Ǿ Ensembles et dictionnaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .195 5.1 Arbres binaires de recherche. . . . . . . . . . . . . . . . . . .196 5.2 AVL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203 5.3 Tables de hachage. . . . . . . . . . . . . . . . . . . . . . . . .214 5.4 Arbres de préfixes. . . . . . . . . . . . . . . . . . . . . . . . .224 5.5 Arbres de Patricia. . . . . . . . . . . . . . . . . . . . . . . . .233 5.6 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .245