Initiation à la programmation et aux algorithmes : Scheme

Auteur(s) :

Bloch, Laurent (1947-....) Découvrir l'auteur

Résumé

Cours de programmation destiné aux scientifiques, économistes et gestionnaires non informaticiens. ©Electre 2020

Contributeur(s)
- Queinnec, Christian (1951-....). Préfacier, etc.
Éditeur(s)
- Éditions Technip
Date
- 2020
Notes
- Notes bibliogr. Bibliogr. et webliogr p. 429-435. Index
Langues
- Français
Description matérielle
- 1 vol. (VIII-435 p.) : ill. ; 25 cm
Collections
- Informatique
Sujet(s)
- Manuels d'enseignement supérieur
- Scheme (langage de programmation)
ISBN
- 978-2-7108-1190-9
Indice
- 681.25 Autres langages informatiques
Quatrième de couverture
- Initiation à la programmation et aux algorithmes avec Scheme
  L'informatique et les algorithmes sont aujourd'hui présents dans tous les domaines. La programmation des ordinateurs est matière d'enseignement obligatoire au lycée. La biologie, les sciences sociales ne se conçoivent plus désormais sans un appui informatique, et sur le marché de l'emploi la préférence va aux spécialistes qui ont une double compétence en informatique.
  Cette double compétence ne saurait se limiter au mode d'emploi des logiciels disponibles dans leur domaine : ce serait les utiliser sans les comprendre, pratique peut-être admissible pour un travail de routine, mais sûrement pas pour un ingénieur ou un chercheur.
  Le présent ouvrage propose une initiation à la programmation initialement pensée pour des biologistes, avec des exemples empruntés à la biologie tels que les algorithmes d'analyse de séquences biologiques, mais les méthodes utilisées sont largement transposables aux sciences sociales.
  Pour cette initiation nous avons choisi Scheme, langage de la famille Lisp, pour sa facilité d'apprentissage. Nous introduisons les principaux algorithmes du texte et plusieurs problèmes d'informatique fondamentale.
  Ce livre s'adresse en priorité aux étudiants de biologie et aux élèves des classes préparatoires de la filière BCPST, mais il concerne également les étudiants en sciences sociales, ainsi que tous les professionnels de ces domaines qui souhaitent élargir leur horizon technique et scientifique.
Tables des matières
- - Initiation a la programmation et aux algorithmes
  - Scheme
  - Laurent Bloch
  - Christian Queinnec
  - Éditions Technip
  - Table des matièresi
  - Préface 1
  - Avant-propos3
  - 1 Fondations 11
  - 1.1 Calcul automatique11
  - 1.2 Machine12
  - 1.3 Information14
  - 1.3.1 Codage14
  - 1.3.2 Codage de l'écriture15
  - 1.3.3 L'information sous l'angle formel17
  - 1.3.4 Information et probabilités17
  - 1.4 Algorithme19
  - 1.5 Programme21
  - 1.6 Langage22
  - 2 Premiers éléments de Scheme 25
  - 2.1 Notions élémentaires26
  - 2.2 Expressions simples27
  - 2.2.1 Nombres28
  - 2.2.2 Caractères et chaînes de caractères29
  - 2.2.3 Booléens29
  - 2.2.4 Identifiants et symboles30
  - 2.2.5 Commentaires31
  - 2.3 Expressions composées31
  - 2.3.1 Combinaisons31
  - 2.3.2 Listes33
  - 2.4 Nommer, remémorer, définir : variable34
  - 2.4.1 Notions de variable et de liaison34
  - 2.4.2 Définition, environnement35
  - 2.5 Créer des procédures avec define39
  - 2.5.1 Forme d'une définition de procédure39
  - 2.5.2 Modèle d'évaluation par substitution40
  - 2.6 Prédicats et alternative41
  - 2.6.1 Usage des prédicats41
  - 2.6.2 Une conditionnelle41
  - 2.6.3 Opérations booléennes43
  - 2.7 Citation43
  - 2.8 Communiquer avec l'extérieur45
  - 2.9 Enchaîner des actions : begin47
  - 2.10 Une autre conditionnelle : cond48
  - 2.11 let, let*49
  - 2.12 Programmation interactive et let nommé51
  - 2.13 Procédure, arguments, variables53
  - 3 Créer, manipuler des programmes 55
  - 3.1 Interprétation d'un programme contenu dans un fichier56
  - 3.2 Charger un programme depuis un fichier57
  - 3.2.1 La procédure load57
  - 3.2.2 Exemple d'usage de load57
  - 3.2.3 Les limites des avantages de load58
  - 3.3 Compilation de programmes Scheme58
  - 3.3.1 Position de la question58
  - 3.3.2 Présentation du compilateur Bigloo59
  - 3.3.3 Compiler un programme avec Bigloo60
  - 4 Formes et types 65
  - 4.1 Une notation grammaticale65
  - 4.2 Des expressions aux données : notion de type67
  - 4.2.1 Typage et justesse des programmes67
  - 4.2.2 Définitions du type de données68
  - 4.2.3 Types de données scalaires en Scheme : nombres70
  - 4.2.4 Types scalaires en Scheme, suite : booléens73
  - 4.2.5 Types scalaires, encore : symboles73
  - 4.2.6 Caractères74
  - 4.2.7 Chaînes de caractères74
  - 5 Processus de calcul 77
  - 5.1 Notion d'évaluation récursive77
  - 5.2 Variables libres ou liées, variables globales79
  - 5.3 Construction de procédures82
  - 5.3.1 Définition de procédure récursive82
  - 5.3.2 Mécanisme effectif de la récursion83
  - 5.3.3 Procédures itératives84
  - 5.3.4 Processus récursif en arbre : Fibonacci89
  - 6 Construire des données 93
  - 6.1 Doublets94
  - 6.1.1 Définition et représentation94
  - 6.1.2 Utilisation des doublets, constructeurs, sélecteurs97
  - 6.2 Représentation et manipulation des listes98
  - 6.2.1 Description et représentation externe98
  - 6.2.2 Les listes sont des doublets101
  - 6.2.3 Manipulation de listes102
  - 6.2.4 Représentation interne des listes105
  - 6.3 Exemples d'opérations sur les listes107
  - 6.3.1 append107
  - 6.3.2 reverse108
  - 6.3.3 map108
  - 6.3.4 for-each109
  - 6.3.5 apply110
  - 6.3.6 Encore une combinaison de map et apply111
  - 6.3.7 Transposition de matrice avec map et apply112
  - 6.4 Procédures avec un nombre variable d'arguments114
  - 6.5 Prédicats d'équivalence114
  - 6.5.1 eqv ?115
  - 6.5.2 eq ?116
  - 6.5.3 equal ?116
  - 6.5.4 Comparaison de listes116
  - 6.5.5 case117
  - 6.6 Listes d'associations (a-listes)118
  - 6.7 Citation encore : quasiquote, unquote et unquote-splicing119
  - 7 Autres formes pour les procédures 121
  - 7.1 A122
  - 7.1.1 λ-expression122
  - 7.1.2 Nommer une λ-expression122
  - 7.1.3 let et lambda124
  - 7.2 Portée, environnements, fermetures126
  - 7.2.1 Portée lexicale126
  - 7.2.2 Plus sur les environnements128
  - 7.2.3 Modèle d'évaluation avec environnement131
  - 7.2.4 eval132
  - 7.3 Des λ-expressions comme valeurs134
  - 7.3.1 Procédures comme valeurs134
  - 7.3.2 Exemple : tri135
  - 7.3.3 let nommé140
  - 7.3.4 Itération avec do141
  - 7.3.5 λ-expressions à plusieurs paramètres : Curry144
  - 7.4 Traitement des erreurs, notion d'exception145
  - 7.4.1 Les erreurs existent145
  - 7.4.2 Exceptions146
  - 8 Quelques pas vers le monde réel 151
  - 8.1 Entrées-sorties : notions générales151
  - 8.2 Traitement de fichier : préliminaires152
  - 8.2.1 La banque de séquences de protéines Swiss-Prot153
  - 8.2.2 Ouverture de fichier155
  - 8.2.3 Dissection d'une protéine156
  - 8.2.4 Les programmes156
  - 8.3 Lecture d'un banque entière158
  - 8.3.1 Assurer l'intégrité des fichiers159
  - 8.4 Lire un fichier séquentiel159
  - 8.4.1 Lire des séquences160
  - 8.4.2 Lire des lignes161
  - 8.4.3 Traitement d'une séquence162
  - 8.4.4 Test de fin de fichier163
  - 8.5 Hiérarchie de mémoire : données numériques 2018164
  - 9 Vecteurs et états de mémoire 167
  - 9.1 Vecteurs168
  - 9.1.1 Accéder aux données en temps constant168
  - 9.1.2 Le type vecteur en Scheme169
  - 9.1.3 Vecteurs homogènes175
  - 9.2 Environnement et mémoire177
  - 9.2.1 Affectation177
  - 9.2.2 Encapsulation et passage de message178
  - 9.2.3 Sous l'environnement, la mémoire181
  - 9.2.4 Conseils de programmation183
  - 9.3 Usage des vecteurs : annuaire électronique183
  - 9.3.1 Le problème et sa solution naïve184
  - 9.3.2 Des alternatives, mais avec leurs défauts185
  - 9.3.3 L'adressage dispersé187
  - 9.4 Gérer la mémoire physique : GC et pile193
  - 9.4.1 Le glaneur de cellules193
  - 9.4.2 Notion d'adresse196
  - 9.4.3 Pile d'exécution197
  - 10 Un langage pour décrire des algorithmes : le pseudocode 201
  - 10.1 La syntaxe201
  - 10.2 Traduction en Scheme203
  - 10.3 Exemple : recherche linéaire dans une liste204
  - 10.3.1 L'algorithme204
  - 10.3.2 Exemple204
  - 10.3.3 En Scheme ?205
  - 11 Algorithmes de tri, application aux vecteurs 207
  - 11.1 Recherche dichotomique208
  - 11.1.1 Peut-on accélérer la recherche d'un élément dans une liste ?208
  - 11.1.2 Algorithme dichotomique208
  - 11.2 Tri par insertion210
  - 11.2.1 Complexité213
  - 11.3 Tri par sélection213
  - 11.4 Tri fusion de vecteur216
  - 11.5 Tri fusion de liste219
  - 11.6 Tri rapide (Quicksort)221
  - 11.7 Tri linéaire223
  - 11.8 Tri dans le tas227
  - 12 Programmation modulaire 235
  - 12.1 Position de la question236
  - 12.2 Notion de module237
  - 12.2.1 Les modules de Bigloo238
  - 12.2.2 Construction d'un programme modulaire241
  - 12.3 Module pour le type de donnée pile243
  - 12.3.1 Structure de pile, définition243
  - 12.3.2 Implémentation244
  - 12.3.3 Application : traitement de tableau247
  - 12.3.4 Un module pour le type de données « pile »247
  - 12.4 make et Makefile250
  - 12.4.1 Systèmes de configuration250
  - 12.4.2 Un Makefile simple pour construire un programme251
  - 12.5 Une petite banque de protéines255
  - 12.5.1 Créer la banque et la stocker256
  - 12.5.2 Consulter la banque260
  - 12.5.3 Le Makefile pour construire l'ensemble260
  - 12.6 Disposer de plusieurs versions d'un programme260
  - 12.6.1 Le problème à résoudre260
  - 12.6.2 Systèmes de gestion de versions263
  - 12.6.3 Vocabulaire de la gestion de versions267
  - 12.6.4 Précautions pour la gestion des fichiers269
  - 12.6.5 Un RCS décentralisé : Mercurial269
  - 12.6.6 Un RCS centralisé : Subversion272
  - 13 Programmer pour le WWW 275
  - 13.1 CGI en Scheme275
  - 13.1.1 Le formulaire276
  - 13.1.2 Le programme CGI277
  - 13.1.3 Le Makefile281
  - 13.1.4 Ranger les fichiers282
  - 13.2 Annuaire associatif en CGI283
  - 14 Vitesse, calculs 291
  - 14.1 Analyse de programmes291
  - 14.1.1 Difficultés de l'étude expérimentale292
  - 14.1.2 Prédiction asymptotique295
  - 14.2 Données comparatives pour quelques algorithmes307
  - 14.3 Calcul de moyennes et variances, traitement de flots de données308
  - 14.3.1 Moyenne par la méthode naïve308
  - 14.3.2 Calcul itératif par un algorithme de B. P. Welford309
  - 14.3.3 Calcul avec un flux de données312
  - 15 Recherche de mots dans un texte 315
  - 15.1 Algorithme force brute315
  - 15.2 Algorithme de Knuth-Morris-Pratt (KMP)317
  - 15.2.1 Description317
  - 15.2.2 Application de cet algorithme318
  - 15.2.3 Construction de la table des préfixes319
  - 15.2.4 Programme principal325
  - 15.2.5 Efficacité de l'algorithme de recherche325
  - 15.2.6 En Scheme326
  - 15.2.7 En style récursif326
  - 16 Programmation dynamique 329
  - 16.1 Programmation dynamique : triangle de Pascal329
  - 16.1.1 Mémorisation330
  - 16.1.2 Un exemple de programmation dynamique330
  - 16.2 L'algorithme de Needleman et Wunsch333
  - 16.3 Calculer un alignement par retour sur trace344
  - 17 Automates finis 351
  - 17.1 Automate fini déterministe351
  - 17.1.1 Homme, loup, chèvre, salade353
  - 17.1.2 01, puis ad libitum355
  - 17.1.3 Compter les 0 et les 1356
  - 17.2 Automate fini non déterministe358
  - 17.3 Équivalence NFA - DFA, exposé d'un exemple361
  - 17.3.1 Construction informelle des sous-ensembles d'états361
  - 17.3.2 Calcul des sous-ensembles pour un exemple363
  - 17.4 Le théorème d'équivalence DFA-NFA364
  - 18 Langages réguliers 367
  - 18.1 Définitions et références367
  - 18.2 Premier exemple368
  - 18.3 Autres règles369
  - 18.4 Premiers repères théoriques371
  - 18.4.1 Opérations sur les langages371
  - 18.4.2 Les bases des expressions régulières372
  - 18.5 Exemples commentés373
  - 18.5.1 Analyser et décomposer un URL373
  - 18.5.2 Parenthèses : grouper, capturer377
  - 18.5.3 Signaler les doublons378
  - 18.6 Équivalence expression régulière-NFA-DFA380
  - 18.6.1 De l'automate à l'expression régulière380
  - 18.6.2 De l'expression régulière à l'automate382
  - 18.7 Au delà des langages réguliers385
  - Conclusion : l'avenir de la programmation387
  - A La machine de Turing 391
  - B Les nombres des ordinateurs 395
  - B.1 Définitions395
  - B.2 Petits exemples binaires397
  - B.3 Conversion entre bases quelconques397
  - B.4 Bases puissance l'une de l'autre400
  - B.4.1 B^' = B^k400
  - B.4.2 B = B^'k402
  - B.5 Nombre de chiffres d'un nombre403
  - B.6 Numération unaire404
  - B.7 Représentation informatique des nombres entiers404
  - B.7.1 Principe de représentation404
  - B.7.2 Notation hexadécimale406
  - B.8 Types fractionnaires407
  - B.8.1 Les « réels »407
  - B.8.2 Principe de représentation407
  - B. 8.3 Exemple409
  - C Algèbre de Boole 413
  - D Du nombre au calcul 415
  - D.1 Définition des entiers naturels415
  - D.2 Addition, multiplication416
  - E Quel fut le premier ordinateur ? 419
  - Index423
  - Bibliographie429
Origine de la notice:
- Electre