Site WWW de Laurent Bloch

Thèses et recherches

2010-08-31T07:58:17Z

Cet article publie les thèses et travaux de recherche de quelques amis qui ont bien voulu me les confier.

La thèse de Francis Dupont, Langages fonctionnels et parallélisme — Une réalisation pour le système CAML :


Thèse de Francis Dupont: Parallel CAML

La thèse de Manuel Serrano, Vers une compilation portable et performante des langages fonctionnels :


Thèse de Manuel Serrano

La HDR de Manuel Serrano, Vers une programmation fonctionnelle praticable :


HDR de Manuel Serrano

L'algorithme de Liang pour la division des mots par ordinateur

2010-07-13T21:06:10Z

#Sommaire

Le problème de la division des mots est compliqué

« Il y a des problèmes dont on trouve tout de suite une solution simple mais approchée, voire naïve et pour lesquels une solution complète nécessite une approche autrement plus sérieuse. La division des mots, c'est-à-dire la coupure des mots en fin de ligne d'un texte, est de ceux-là. C'est tellement vrai que lorsque l'on parle de ce problème à un enseignant d'informatique en université, la réplique est presque invariablement la même : Où est le problème ? Mes étudiants de DEUG, ou de licence, font ça en TP ».

Ces lignes de Jacques André introduisaient en 1986 l'article de Jacques Désarménien La division par ordinateur des mots français : application à TeX, (Technique et Science Informatiques 1986/04). L'article, en ma possession mais malheureusement toujours pas disponible en ligne librement, expliquait toute la difficulté du sujet et en exposait la solution, basée sur un mystérieux « algorithme de Liang », dont je ne trouvai pas le moyen de consulter la documentation, sauf à me rendre à la bibliothèque de l'Université Stanford pour y emprunter la thèse de Ph.D. soutenue en 1983 par Frank Liang, Word Hy-phen-a-tion by Com-put-er ; les tirets à l'intérieur des mots de ce titre y indiquent les positions légitimes de césure, nous utiliserons cette notation dans la suite.

Depuis 2004, mais je ne m'en suis avisé que récemment, Frank Liang a autorisé la mise en ligne d'une photocopie de sa thèse, de piètre qualité mais lisible. Il était d'ailleurs déjà possible d'en lire un résumé dans le TeXbook de Donald Knuth, à l'annexe H (page 515 de la traduction française de Jean-Côme Charpentier). J'ai donc lu récemment le texte intégral, pour constater que la substance relative à la division des mots m'en avait déjà été délivrée par l'article de Désarménien.

Ranger efficacement des mots (ou des motifs)

En fait, les trois quarts des 44 pages de texte de la thèse (sans compter les annexes qui incluent le programme de génération des motifs de césure et la table des motifs) sont consacrés à des trésors d'ingéniosité algorithmique destinés à gagner quelques milliers d'octets en mémoire, efforts dont l'auteur se dispenserait sans doute en grande partie s'il devait recommencer ce travail sur un ordinateur contemporain. Aussi le lecteur impatient des aspects linguistiques et typographiques peut-il sans dommage passer directement à la section suivante.

Pour stocker des mots ou des motifs (fragments de mots, patterns), Liang utilise les arbres de recherche (digital search trees), ou tries, une structure de données qui peut être envisagée comme un arbre m-aire, où m est le nombre de lettres de l'alphabet sur lequel sont définis les mots. Les recherches sont effectuées caractère par caractère, avec à chaque nœud une alternative à m branches.

Comme les informaticiens préfèrent les arbres binaires, Liang passe ensuite du trie m-aire au trie chaîné implanté par un arbre binaire, où l'alternative à m branches est réalisée par une séquence de comparaisons, à chaque nœud si le caractère qui s'y trouve est « bon » on passe au fils droit, au fils gauche sinon.

Liang implante son trie chaîné dans un tableau à m colonnes, une par lettre de l'alphabet. La première ligne du tableau contient, dans chaque case qui correspond à une lettre qui est l'initiale d'un ou de plusieurs mots, le numéro d'une ligne dont les cases qui correspondent aux secondes lettres de chacun de ces mots indiqueront des numéros de ligne où se trouveront des pointeurs vers les lignes correspondant aux troisièmes lettres, et ainsi de suite. Une marque spéciale indique qu'ue case correspond à la dernière lettre du mot considéré.

Le tableau ainsi obtenu est plein de cases vides : pour gagner de la place Liang regroupe les lignes dont les cases occupées sont dans des colonnes différentes, ce qui lui impose d'indexer chaque case avec la lettre précédente du mot auquel elle correspond. Enfin on peut encore gagner de la place en remarquant que beaucoup de mots partagent un suffixe commun, et qu'en remontant dans le trie en partant des feuilles on doit pouvoir fusionner les subtries communs, non sans identifier, dans une table associative, les nœuds équivalents. Bref, ces trésors d'ingéniosité algorithmique récursive permettent à Frank Liang de faire tenir son algorithme et sa table de classement des mots ou des motifs, qui sont loin d'être simples, en très peu de place. L'originalité des méthodes employées justifie pleinement la présence de cet exposé dans une thèse de Ph.D.

Césure

Après ce long préambule consacré aux structures de données propres à stocker les mots et les motifs, l'opération de césure elle-même (hyphenation en anglais) fait l'objet d'un exposé assez laconique. Deux méthodes sont envisageables : définir et appliquer des règles, ou constituer un dictionnaire exhaustif où chaque mot, accompagné de ses différentes formes dérivées, figurera annoté des points de césure autorisés. Notons que le problème des formes dérivées, s'il est simple en anglais moderne, débarrassé de la plupart des flexions et variations des formes verbales, est nettement plus complexe en français.

Nous avons appris à l'école les règles de césure des mots français, et d'ailleurs ce sont elles que l'on retrouve dans le programme de césure du premier système de typographie informatique conçu dès 1954 par une équipe française menée par F.H. Raymond et G. Bafour. Un programme qui repose uniquement sur ces règles aura l'avantage de la simplicité, et il permettra de diviser correctement la plupart des mots.

Néanmoins, ces règles acceptent un certain nombre d'exceptions, qui produiront autant d'erreurs, inacceptables pour un système de typographie professionnel. Ainsi, nous explique Jacques Désarménien, après avoir compilé tous les manuels typographiques et grammaticaux qu'il a pu trouver, épis-copal sera divisé selon une règle phonétique, cependant qu'épi-scope, plus moderne, sera divisé selon une règle étymologique. Le groupe ill est insécable lorsqu'il représente un son mouillé comme dans grillage, mais pas dans vil-lage. De même pour le groupe gn, insécable sauf dans stag-nant où le g et le n sont prononcés séparément. Encore les manuels ne sont-ils pas unanimes sur ces points délicats.

L'idée, géniale, de Frank Liang fut de combiner la méthode des règles avec celle du dictionnaire, en constituant non pas un dictionnaire des mots à diviser, mais un dictionnaire des sous-mots, qui sont enregistrés sous forme de motifs. Ce dictionnaire comportera un petit nombre de motifs correspondant aux règles, et un plus grand nombre de motifs correspondant aux exceptions et aux exceptions des exceptions. Comment le motif de l'exception pourra-t-il prendre le pas sur le motif de la règle, c'est ce que nous allons voir.

Ainsi, pour reprendre l'exposé de Désarménien, pour diviser un mot on extraiera tous ses sous-mots, qui seront confrontés au dictionnaire des motifs, constitué préalablement. Les lettres d'un groupe qui constitue un motif sont séparées par des coefficients entiers de 0 à 9 qui indiquent la désirabilité ou la non-désirabilité d'une coupure à cet endroit. En fait 0, qui indique « pas de coupure », sera omis. Les nombres impairs indiquent les coupures autorisées, les nombres pairs (dont 0, omis) les coupures interdites. Lorsque plusieurs coefficients fournis par différents motifs sont en concurrence pour une même position de césure éventuelle, le plus grand l'emporte. Ainsi, la présence dans le dictionnaire des motifs vil3l et avil4l permet la césure de vil-lage et interdit celle de gravil/lon. Le e ouvert non accentué de té-les-cope le distingue de mi-cro-scope, qui ne se coupera pas non plus comme dis-co-phile, ce qu'indiquent 1s2cop, e2s3cop, di2s3cop.

Désarménien s'est rangé à l'avis du Memento typographique de C. Gouriou, « qu'il est préférable, surtout dans les ouvrages destinés aux élèves, d'éviter de conserver en fin de ligne des syllabes malsonnantes ou prêtant à des interprétations regrettables », et il a introduit les motifs +con4 et +cons4 à cet effet.

Régularité comparée des différentes langues

Pour engendrer le dictionnaire de motifs, Frank Liang a écrit le programme Patgen, auquel il faut fournir une liste de mots préalablement divisés, dont il inférera un dictionnaire de motifs apte à les reproduire. Les bons dictionnaires anglais ou américains mentionnent pour chaque mot les points de césure acceptables, mais pas les dictionnaires français. En outre, un tel dictionnaire existât-il, qu'il ne fournirait sans doute pas les césures des formes dérivées, dont la langue française est riche. Bref, Jacques Désarménien a préféré écrire directement les motifs nécessaire à la production du dictionnaire désiré. Ce travail (de romain) est décrit en détail dans l'article, il a fait alterner essais de programmes et compilation manuelle de motifs au fur et à mesure qu'apparaissaient les césures inattendues.

Une fois tout ce travail fait et que l'on croit toucher au but, surgit un autre problème : avec TeX, la césure dépend de la police de caractères ! En effet le traitement des ligatures et des crénages n'est pas sans effet, Désarménien a dû adapter les polices.

Aucun programme de division des mots ne peut prétendre à la perfection, puisqu'aussi bien les langues humaines sont d'une flexilbilité infinie, qu'en outre elles varient dans le temps et dans l'espace et que leurs différents locuteurs ne sont pas forcément d'accord entre eux sur les usages. Certains sont carrément non-programmables : en anglais record se coupe re-cord s'il s'agit du nom et rec-ord s'il s'agit du verbe. Donc il s'agira, pour chaque langue, d'établir un dictionnaire de motifs de taille raisonnable et qui ne laissera subsister qu'un tout petit nombre d'exceptions résiduelles, la plupart des logiciels de composition donnant la possibilité de diviser « à la main » les mots trop rétifs.

À la fin de son article Jacques Désarménien nous livre une comparaison intéressante. On peut estimer que le nombre de motifs qu'il faut introduire dans le dictionnaire, pour traiter des cas d'exception par exemple, est une mesure de l'irrégularité de l'orthographe de la langue considérée. La diffusion de TeX/LaTeX a conduit de nombreux chercheurs à construire des dictionnaires adaptés à d'autres langues que l'anglais, et ils se sont réunis à Côme en 1985 pour comparer leurs résultats.

Le dictionnaire de Désarménien pour le français comporte 804 motifs, dont 412 pour les césures étymologiques. Pour l'anglais il en faut 4 447, près de 10 000 pour l'allemand, mais seulement 88 pour l'italien, langue dont l'orthographe a été fixée au XIX^e siècle seulement, selon des principes sans doute plus rationnels.

Ce n'est que si l'on ne s'est jamais posé la question que cette question de la division des mots peut sembler ancillaire. Comme Bernard Gaulle nous le rappelait, par exemple dans son article de 1994 dans les Cahiers GUTenberg n° 18, Commentaires sur la portabilité des documents (LA)TEX, la méthode et les choix de division des mots ont une importance primordiale pour la qualité typographique d'un texte, ainsi que pour l'adaptation d'un système de composition à une langue particulière.

Les programmes de Liang ont été traduits dans à peu près tous les langages de programmation et utilisés pour d'autres systèmes de composition que TeX et LaTeX, en voici une version dans mon langage préféré.

La Renaissance du parallélisme

2010-07-08T20:07:23Z

#Sommaire-

Beautés et décadence du calcul parallèle

De 1960 à la fin des années 1980 le calcul parallèle fut un domaine de recherche actif, avec des débouchés industriels remarquables qui culminèrent avec les Connection Machines de Thinking Machines Corporation dont le premier modèle comptait 65 536 processeurs !

L'essor de ces développements passionnants fut brisé par les progrès de la micro-électronique : l'amélioration rapide des performances et de l'efficacité des microprocesseurs, au rythme prévu par la loi de Moore, assurait la croissance de l'industrie et le développement des usages de l'informatique sans remettre en cause ni les logiciels existants ni les méthodes de programmation, alors que se convertir au calcul parallèle aurait exigé, outre des investissements matériels significatifs, des remises en cause intellectuelles et techniques considérables du côté de la programmation.

Année après année, les progrès des processeurs procuraient gratuitement les mêmes gains de performance que le dur labeur de parallélisation des programmes. Si paralléliser un programme prenait deux ans, ce délai procurait conformément à la loi de Moore un doublement de la densité des circuits, et les gains qui en résultaient.

Dans le numéro de juin des Communications of the ACM Peter J. Denning et Jack B. Dennis consacrent un point de vue dense et profond à la Renaissance du parallélisme. En effet les progrès techniques dont la loi de Moore rend compte commencent à atteindre des limites fixées par la physique : quand l'épaisseur du diélectrique des transistors se mesure en dizaines d'atomes, on comprend bien qu'il va falloir trouver un autre moyen pour continuer à accroître la puissance de calcul. D'ailleurs les fréquences d'horloge n'augmentent plus guère.

Parmi les autres moyens envisageables pour accroître les performances, utiliser plusieurs processeurs (ou des processeurs multi-cœurs, ce qui revient au même) au lieu d'un semble une idée prometteuse. Il est aussi possible d'utiliser plusieurs ordinateurs qui se répartissent le travail, cela s'appelle une grappe (cluster), la liaison entre les unités de calcul est moins intime que dans un multiprocesseur, les problèmes à résoudre sont différents mais pas trop. Répartir une charge de travail entre plusieurs processeurs pose des problèmes de synchronisation et de coordination qui ne sont pas triviaux : cela s'appelle le calcul parallèle.

Idées nouvelles, idées anciennes

L'apparition des multiprocesseurs, des multi-cœurs et des clusters, et leur corollaire, la réapparition du parallélisme, tombent dans un océan d'oubli, et les ingénieurs et chercheurs de la nouvelle génération redécouvrent des problèmes qu'ils croient nouveaux. L'article de Denning et Dennis propose une brillante synthèse des acquis du premier parallélisme, directement réutilisables avec les nouveaux processeurs.

La première architecture multiprocesseurs fut celle du Burroughs B5000, lancé en 1961 par une équipe sous la direction de Robert S. Barton. Le B5000 comportait de nombreuses innovations significatives qui lui donnaient 20 ans d'avance sur le reste de l'industrie :

premier système d'exploitation écrit en langage évolué, Algol en l'occurrence ;
multiprocesseur à mémoire partagée et commutation crossbar ;
architecture à pile ;
jeu d'instructions réduit ;
code automatiquement ré-entrant, etc.

L'apparition d'un multiprocesseur tel que le B5000 stimula la recherche en parallélisme : en 1971 un groupe de chercheurs de Brown University et de General Electric mirent au point un modèle d'environnement d'exécution parallèle qui serait parfaitement apte à résoudre des problèmes considérés aujourd'hui comme des défis pour la recherche.

Déterminisme du calcul parallèle

Le problème théorique central du calcul parallèle est celui du déterminisme, qui demande qu'un réseau de tâches parallèles en mémoire partagée produise toujours le même résultat à partir des mêmes données, indépendamment des vitesses d'exécution respectives des tâches. Un résultat majeur de la recherche dans ce domaine est le théorème du déterminisme, qui donne une condition suffisante pour garantir le résultat. En voici l'énoncé :

une tâche est un calcul élémentaire qui réalise l'application d'une fonction à des arguments pour produire un résultat ;
deux tâches sont dites en conflit si l'une d'elles modifie une cellule de mémoire utilisée par l'autre ;
dans un système de tâches concurrentes, des situations de compétition (race conditions) peuvent survenir qui feraient que le résultat du calcul dépende des vitesses d'exécution relatives des différentes tâches ;
le déterminisme du calcul est garanti si le système est soumis à la contrainte que, pour chaque couple de tâches en conflit, l'ordre d'exécution soit toujours le même pour tout calcul du système.

Programmation fonctionnelle et composition de programmes parallèles

Il résulte du théorème du déterminisme exposé ci-dessus un corollaire selon lequel un programme constitué de tâches concurrentes implanté sans recours à l'opération d'affectation au moyen d'un langage de programmation fonctionnel sera, de façon inhérente (« gratuitement »), déterministe, puisque chaque tâche délivre son résultat à son successeur sans interférence entre leurs zones mémoire respectives.

On consultera avec profit la thèse que Francis Dupont a consacrée à une implantation parallèle du langage fonctionnel CAML, disponible sur ce site ici :


Thèse de Francis Dupont: Parallel CAML

Les chercheurs en systèmes parallèles avaient un autre sommet à atteindre : la composition de programmes parallèles, c'est-à-dire l'établissement des conditions auxquelles un programme parallèle peut être incorporé, sans modification, à un programme parallèle plus grand. Il faut pour cela satisfaire trois principes :

masquage de l'information : l'état interne d'une tâche ne doit pas être accessible à une autre tâche ;
indépendance du contexte : une tâche ne doit pas dépendre de valeurs extérieures à sa mémoire locale ;
non-interférence des arguments : si deux tâches concurrentes accèdent à la même donnée, aucune des deux ne doit la modifier.

Les langages de programmation fonctionnels satisfont automatiquement ces trois principes ; leurs modules sont donc, de façon inhérente, composables.

Tous les problèmes ne relèvent pas de solutions déterministes ; les systèmes transactionnels en sont l'illustration : une place dans un avion ne peut être réservée qu'une fois, et ce sera par la tâche la plus rapide. Comment construire des systèmes parallèles par composition de modules dont certains ne sont pas déterministes, voilà une question ouverte.

Mémoire virtuelle et abandon des fichiers

La mémoire virtuelle n'est pas juste une astuce technique pour faciliter le rangement des objets : en découplant la programmation de la gestion de la mémoire, elle procure un écran d'abstraction et un mécanisme centralisé d'accès aux données qui débarrasse les modules des lourdeurs qui seraient des obstacles à leur composition parallèle.

Le système Multics a démontré, dans les années 1960, qu'il était possible, de façon efficace, d'implanter toutes les données, tant persistantes que temporaires, dans un espace-adresse unique. Chaque donnée y a une adresse, et la persistance est un attribut facultatif. Cette conception ouvre la voie à la disparition des fichiers, cette plaie de l'informatique, héritée de la mécanographie, et qui rend tout incompréhensible au profane.

Multics est venu trop tôt pour réussir, il coûtait trop cher sur des ordinateurs trop gros et pas assez puissants. Aujourd'hui la voie est ouverte aux systèmes parallèles persistants sans fichiers, qui formeront l'informatique de demain.

Make et Makefile

Laurent Bloch — 2010-07-08T12:10:01Z

#Sommaire-

make

Le système Unix (comme d'autres) possède un système de construction de programmes (on dit aussi un configurateur) nommé make. Au moyen de ce système on peut décrire les fichiers source et autres nécessaires à la construction d'un programme, les dépendances entre fichiers, les commandes nécessaires à la compilation des sources et à la construction des exécutables, ainsi que beaucoup d'autres choses.

L'usage habituel de make consiste à déterminer automatiquement quelles parties d'un grand programme (ou d'un texte composé avec LaTeX) doivent être recompilées après que certains fichiers source aient été modifiés, et à lancer les commandes appropriées pour ce faire.

Make est en fait un système plus général que seulement un configurateur de programmes. C'est un langage de programmation adapté à la résolution de systèmes de contraintes. Un programme make (généralement contenu dans un fichier nommé Makefile) comporte essentiellement deux types d'instructions : des règles et des commandes.

Une règle énonce le nom d'une cible à atteindre (par exemple le nom d'un fichier exécutable) suivi des noms des cibles préliminaires dont elle dépend et qu'il faudra avoir atteintes avant d'espérer atteindre la cible courante. Cela s'écrit par exemple ainsi, le nom de la cible est en début de ligne suivi de :, les noms des cibles intermédiaires sont dans la suite de la ligne :

all: mon_livre
mon_livre: chapitre1 chapitre2
chapitre1: figures-chap1
chapitre2: figures-chap2

Télécharger

Une ligne qui contient une instruction de type règle est suivie de lignes d'instructions de type commande qui formulent les actions à effectuer pour atteindre la cible de la règle :

objet1: source1
<tabulation> bigloo -c source1 -o objet1

Télécharger

Attention une ligne de commande commence toujours par le caractère tabulation, c'est un des moindres pièges de make que de donner une signification syntaxique à un caractère invisible.

Il y a aussi des définitions de variables et des lignes de commentaires :

# il est souvent préférable de définir les outils
# par des variables comme ceci :
BIGLOO = bigloo
# et de les utiliser ainsi, pour des raisons expliquées plus bas :
<tabulation> $(BIGLOO) -c source1 -o objet1

Télécharger

Make peut être utilisé pour configurer d'autres objets que des programmes : toute situation où certains fichiers-cibles doivent être mis à jour automatiquement à partir de fichiers-origines à chaque modification de ces derniers et selon certaines règles est susceptible d'être automatisée au moyen de make. Une cible n'est d'ailleurs pas nécessairement un fichier, il peut s'agir plus généralement d'un ensemble de tâches à réaliser désigné par un nom symbolique.

Le langage de make est loin d'être simple et sa description complète excéderait les limites de ce document [1]. Nous nous contenterons d'indiquer quelques moyens propres à rédiger un programme make simple.

Un Makefile simple pour construire un programme

Un programme make est contenu dans un fichier nommé par convention Makefile. En général on place dans un même répertoire les fichiers qui servent à la construction du programme et le Makefile qui indique comment le construire. Les exemples ci-dessous supposent cette condition remplie, et que ce répertoire est le répertoire courant quand on tape la commande make.

Nous prendrons comme exemple la construction d'un programme en Scheme compilé avec le compilateur Bigloo. Notre Makefile va comporter des lignes de texte essentiellement de deux sortes, décrites par les deux alinéas suivants.

Lignes de règles

Des lignes de règles, ou lignes de dépendance, énumèrent, pour une cible à produire, les cibles préalables (souvent des fichiers) dont elle dépend. Si un des fichiers dont dépend la cible est modifié depuis sa dernière construction [2], il faudra la reconstruire. Ainsi, la règle de dépendance pour lire-outils.o est très simple :

lire-outils.o: lire-outils.scm

Le fichier-objet lire-outils.o dépend du fichier-source lire-outils.scm. Si ce dernier est modifié (la création est un cas particulier de modification) il faut reconstruire l'objet.

Une ligne de règle se reconnaît au fait qu'elle comporte le signe « : », qui sépare la cible à sa gauche des pré-requis à sa droite :

lire-swissprot: lire-outils.o lire-swiss-seq.o choix-fichier.o

La première règle du Makefile joue un rôle particulier, elle mentionne une cible toujours visée. Il convient de mettre en tête soit la règle qui déclenche la construction du programme résultant, soit une règle qui se contente d'énumérer les exécutables souhaités :

all: lire-swissprot

Lignes de commandes

Des lignes de commandes énumèrent les actions à effectuer pour produire la cible. Dans le cas simple que nous allons décrire ce seront des compilations et des éditions de liens, mais toute commande Unix serait acceptable.

Attention, chaque ligne de commande s'exécute dans un environnement propre au sens Unix du terme ; si par exemple nous voulons visiter des sous-répertoires où des commandes make déclencheront d'autres actions, et ainsi de suite récursivement, placer la commande cd appropriée sur une ligne et passer à la ligne suivante pour décrire les actions ne produira pas le résultat escompté. Il faut utiliser la syntaxe du shell pour la composition séquentielle des processus :

(cd <mon repertoire> ; ${MAKE} [<ma cible>])

${MAKE} est une variable standard de make qui désigne make. À cet endroit nous voulons exécuter make, mais si nous écrivons simplement make nous n'aurons la garantie ni que nous invoquons bien la même version de make que celle qui a lancé le Makefile, ni surtout qu'elle va s'exécuter avec les mêmes paramètres. ${MAKE} nous donne ces garanties [3].

Une ligne de commande commence par un caractère de tabulation. Comme make reconnaît les lignes de commande à ce caractère, il faut prendre garde à ne pas l'oublier pour les lignes de commande et à ne pas en mettre ailleurs. Et avoir remarqué que le « copier-coller » à la souris de votre interface graphique préférée transforme parfois les tabulations en espaces blancs.

La ligne de commande pour la cible lire-outils.o sera :

 bigloo -afile access-file.scm -c lire-outils.scm

Voici la ligne de commande pour l'édition de liens qui construit le programme (la règle pour le programme complet est plus longue, pour aller à la ligne il faut placer un caractère « \ » à la fin, immédiatement suivi d'un retour-chariot) :

 bigloo lire-outils.o lire-swiss-seq.o choix-fichier.o \
 -o lire-swissprot

Télécharger

sans oublier la tabulation.

Notre Makefile complet peut donc s'écrire comme suit :

all: lire-swissprot 
choix-fichier.o : choix-fichier.scm 
 bigloo -afile access-file.scm -c choix-fichier.scm 
lire-swiss-seq.o : lire-swiss-seq.scm 
 bigloo -afile access-file.scm -c lire-swiss-seq.scm 
lire-outils.o : lire-outils.scm 
 bigloo -afile access-file.scm -c lire-outils.scm 
lire-swissprot: lire-outils.o lire-swiss-seq.o choix-fichier.o 
 bigloo lire-swiss-seq.o lire-outils.o choix-fichier.o -o lire-swissprot

Télécharger

Généraliser et factoriser

Règles génériques

Les trois règles de construction des objets sont extrêmement similaires. L'esprit de la programmation rechigne devant l'inélégance de cette répétition. Make nous offre la possibilité d'écrire des règles génériques :

%.o: %.scm
 bigloo -afile access-file.scm -c $< -o $@

Télécharger

ce qui signifie : pour tout fichier-cible avec un nom de la forme %.o, % étant un préfixe quelconque, le fichier %.scm s'il existe est un bon prérequis, et alors l'action décrite par la ligne de commande suivante est exécutée (si quelque-chose a été modifié dans le prérequis). $< est une variable dont la valeur est la liste des prérequis qui ont déclenché la règle (ici le fichier %.scm), $@ est une variable qui désigne la cible courante. Nous obtenons donc le Makefile suivant :

all: lire-swissprot 
%.o: %.scm 
 bigloo -afile access-file.scm -c $< -o $@ 
lire-swissprot: lire-outils.o lire-swiss-seq.o choix-fichier.o 
 bigloo lire-swiss-seq.o choix-fichier.o lire-outils.o -o lire-swissprot

Télécharger

Ceci rédigé il nous suffit de nous placer dans un répertoire contenant les fichiers suivants :

Makefile choix-fichier.scm lire-swiss-seq.scm
access-file.scm lire-outils.scm 

Télécharger

et taper la commande make suffira à construire notre programme lire-swissprot.

Règles de suffixes

Une autre façon d'écrire pour make des règles plus générales (et donc moins nombreuses) est d'utiliser les suffixes des noms de fichiers pour déterminer les règles à leur appliquer. En général sous Unix les fichiers source sont suffixés par .scm pour les programmes Bigloo, .c pour les programmes C, .cc pour les programmes C++, .f pour les programmes Fortran, etc. Les compilateurs produisent des fichiers objet suffixés par .o. Ceci nous permet d'écrire des règles selon une syntaxe que nous allons illustrer par un exemple.

Supposons que nous voulions construire un programme nommé iter-os à partir de fichiers source Bigloo, C et C++. C'est l'objet du Makefile ci-dessous :

.SUFFIXES : .o .c .cc .scm
BGL_SOURCES = peuple-iter.scm call-os.scm
BGL_OBJECTS = peuple-iter.o call-os.o
SOURCES = $(BGL_SOURCES) create_db.cc read_db.cc \
 write_db.cc copy_seq.cc \
 xalloc.c liste_db.cc query_db.cc stub.cc
CXX_OBJECTS = read_db.o create_db.o write_db.o \
 copy_seq.o liste_db.o query_db.o stub.o
C_OBJECTS = xalloc.o
OBJECTS = $(CXX_OBJECTS) $(C_OBJECTS) $(BGL_OBJECTS)
EXECUTABLE = iter-os
CCC =/usr/ucb/cxx
BIGLOO = bigloo
CFLAGS = -O3
CPPFLAGS =
BGL_FLAGS = -Obench -farithmetic -rm
BGL_LDFLAGS = -lstatic-bigloo
CC=gcc
all: $(EXECUTABLE) Makefile
.cc.o:
 $(CCC) $(CPPFLAGS) -c $< -o $@
.c.o:
 $(CC) $(CFLAGS) -c $< -o $@
.scm.o:
 $(BIGLOO) -afile access - file.scm $(BGL_FLAGS) -c $< -o $@
$(EXECUTABLE): $(OBJECTS)
 $(BIGLOO) $(BGL_LDFLAGS) -o $@ $(OBJECTS)
clean :
 rm -f $(EXECUTABLE) $(OBJECTS)

Télécharger

Ce Makefile commence à ressembler à du travail professionnel. La première ligne définit les suffixes que nous allons utiliser (en fait cette ligne n'est indispensable que pour définir le suffixe des fichiers Bigloo, les autres sont définis par défaut). Les listes de fichiers objet sont définis par des variables pour éviter les définitions multiples qui aboutissent à des incohérences. La variable définie par BGL_OBJECTS = ... est invoquée ultérieurement sous le nom ${BGL_OBJECTS}. Les accolades { et } peuvent être remplacées (sauf cas particulier) par des parenthèses ( et ).

Les drapeaux des compilateurs sont définis par des variables vides par méfiance à l'égard de make, qui souvent prévoit des valeurs par défaut. Les noms des compilateurs sont définis par des variables pour les mêmes raisons que nous utilisions $MAKE ci-dessus pour désigner make.

La règle .cc.o décrit comment faire un fichier objet .o à partir d'un fichier source .cc. La variable $< désigne le fichier prérequis à partir duquel on construit la cible. $@ est comme ci-dessus une variable qui désigne la cible courante.

La règle clean permet de détruire les fichiers intermédiaires et finals pour repartir des sources quand on a fait des bêtises. make clean sera la façon de l'invoquer.

Ces quelques paragraphes sont loin d'épuiser le sujet make. Ils devraient vous permettre d'écrire des Makefiles simples et de lire ceux que vous trouverez dans les distributions de logiciels récupérées sur le réseau. Pour de plus amples détails, voir le manuel d'Oram. make

Références

[1] Andrew Oram Steve Talbott. Managing Projects with make. O'Reilly, Sebastopol, USA, 1991.

[1] Voir le manuel d'Oram [1]. Des outils similaires à make sont disponibles pour d'autres systèmes. Certains sont dotés d'une interface graphique, mais ils ont l'inconvénient de ne pas être aussi programmables que make. Les systèmes de programmation destinés au langage Java utilisent des outils spécifiques, notamment Maven et Ant, qui réalisent des fonctions analogues.

[2] L'enregistrement de répertoire qui permet d'accéder à un fichier pointe sur une structure de données appelée i-nœud qui contient les caractéristiques statiques du fichier, notamment sa date de création, sa date de dernière modification et sa date de dernière consultation. Le fonctionnement de make repose sur ces informations.

[3] Notons que le signe $ a, ici et en d'autres circonstances, une valeur syntaxique pour make. Or il a aussi une valeur syntaxique pour le shell Unix, par exemple nous pouvons désigner notre répertoire racine par $HOME, ce qui peut être utile notamment dans un Makefile. Pour éviter une ambiguïté dans ce cas, et par convention, dans un Makefile tout emploi du signe $ pour une commande du shell se fera en écrivant $$ (deux signes $).

La bulle universitaire — Faut-il poursuivre le rêve américain ?

Laurent Bloch — 2010-05-17T18:54:10Z

Dans ce petit livre publié à Lausanne par les Éditions d'En bas, Libero Zuppiroli, professeur de physique à la très réputée École polytechnique fédérale de Lausanne (EPFL), narre l'adoption, irréfléchie à son avis, par les universités européennes, de ce qu'elles auraient supposé être le modèle américain. Plus précisément, il s'agit de la transformation, au cours des quinze dernières années, de la vénérable et respectée EPFL pour qu'elle adopte ce modèle, transformation accomplie avec un succès qui, aux dires du professeur Zuppiroli, confirmés par la position de l'école dans les classements du Times et de Shangaï, a excédé toutes les espérances : « L'opération est parfaitement réussie et l'École est définitivement engagée dans une course vers l'excellence, alimentée par les recrutements de professeurs jeunes, ambitieux, acquis aux valeurs de la compétition et du leadership et opérant sur des sujets de recherche à la mode... » (p. 62). Le recrutement aux postes stratégiques de professeurs formés aux États-Unis a grandement contribué au résultat.

Quelle est la teneur de cette transformation ? le passage d'une pratique universitaire tournée vers la science à l'ère du management scientifique et de la recherche à haut débit (à flux tendus ?). Zuppiroli cite (p. 30) le CV de 53 pages d'un tel « professeur manager », classé par la base de données ISI Web of knowledge au 163^e rang des 1120 scientifiques de sa discipline : coauteur d'à peu près 630 articles et 9 livres, il a pendant les années 1995-1996 été invité à une trentaine de conférences internationales où il a présenté ses résultats, de la Corée au Canada et du Japon à la Suède, cependant qu'il publiait 57 articles dans des revues internationales à comité de lecture, tout en enseignant à l'EPFL, en y dirigeant un institut, en dirigeant un grand laboratoire à 700 km de Lausanne, sans compter de nombreuses autres fonctions de conseiller dans différents organismes publics et privés.

Si l'on évalue l'activité de ce professeur-manager à l'aune de la science d'hier, le constat risque bien de s'imposer qu'il n'a guère eu de temps pour une activité intellectuelle à l'ancienne mode, que pour lui l'action a pris le pas sur la pensée, que le pouvoir l'a plus intéressé que le savoir (qui ennuie tout le monde), et que pendant les trajets en avion entre les conférences il a surtout travaillé ses présentations Powerpoint, outil principal de la science new style.

Arrivé là, le lecteur de Zuppiroli risque fort de conclure que tout cela relève de l'imposture intellectuelle ; c'est qu'il n'aura pas compris ce que sont les quatre piliers de la science contemporaine, qui ne peuvent être nommés que dans la nouvelle langue scientifique dérivée de l'anglais, le globbish (p. 31) :

Networking : l'art de construire des réseaux de chercheurs de portée internationale. Ainsi, les 57 articles du professeur cité par Zuppiroli pour la période 1995-1996 sont cosignés par 197 auteurs.
Fundraising : l'art de ramasser de l'argent.
Marketing : l'art de faire savoir que l'on est le meilleur.
Management : pour faire prospérer une entreprise aussi importante il faut maîtriser la gestion tant des finances que des hommes.

Fort bien, dira-t-on alors à Libero Zuppiroli, mais qui fait le vrai travail ? parce que malgré tout il y en a, et même on peut dire que la production scientifique n'a jamais été aussi importante qu'aujourd'hui, au moins en volume. Or pour faire ce travail de recherche il ne faut en tout cas pas trop compter sur les étudiants solvables des pays riches, qui ont parfois déjà payé des droits d'inscription faramineux pour accéder aux meilleurs instituts de la nouvelle science, et qui pensent de toute façon qu'à partir du moment où ils ont été admis on ne va pas en plus leur demander de travailler pour obtenir leur diplôme.

D'ailleurs, nous explique Zuppiroli (p. 84), l'offre de formation s'adapte à la clientèle : cela s'appelle les accords de Bologne, conclus en 1999 par les ministres de l'enseignement supérieur européens, hors de toute concertation avec les milieux universitaires concernés, pour uniformiser les cursus des universités européennes selon le format anglo-saxon. La version française du cursus en question s'appelle LMD : licence en trois ans, master en deux ans, doctorat en trois ans. Grâce à ce système, « l'université européenne devrait prendre l'aspect d'une gigantesque chaîne de supermarchés où les nouveaux étudiants, clients consommateurs de savoir, pourraient partout accéder aux mêmes produits et acquérir des diplômes voisins...

L'uniformité produit les mêmes effets pour les diplômes universitaires que pour les légumes vendus en supermarché : c'est le triomphe de la tomate bien calibrée insipide et hors sol que l'on appelle abusivement tomate hollandaise, car de nos jours elle est produite partout. » Partout triomphent les études les plus courtes et les moins originales, assorties de la baisse des exigences pour obtenir les diplômes. Quant aux ambitieux professeurs experts en leadership et en communication, ils considèrent l'enseignement comme une perte de temps dont il convient de se débarrasser dans toute la mesure du possible, par exemple en le sous-traitant à des chargés de cours recrutés pour de petits boulots.

Cela dit, « la mobilité des étudiants à travers l'Europe n'a pas beaucoup crû avec les accords de Bologne. En fait, la mobilité est surtout une affaire d'argent pour des voyages et des logements. Seuls les parents et les établissements les plus riches peuvent offrir des possibilités réelles de mobilité aux étudiants.

Le vrai but de cette opération universitaire est à terme la baisse du salaire des diplômés. Quand règne l'uniformité, celui qui est embauché, c'est celui qui a le moins d'exigences... Dans les années 1970, les revenus du travail représentaient les 2/3 des revenus mondiaux alors que dans les années 2000, les revenus du travail n'en représentent plus qu'un tiers. » (p. 85).

Mais alors, qui réalise vraiment le travail de recherche, qui produit la substance des trente articles annuels du professeur-manager et de ses « pauvres points » ? Parce qu'il s'agit d'un vrai travail, qui exige de nombreuses nuits blanches et ne rapporte pas grand-chose. Si j'en juge par les signatures des articles des revues à comité de lecture du domaine informatique qui me tombent sous les yeux, les sources de thésards et de stagiaires post-doctoraux qui acceptent de travailler jour et nuit comme des forçats pour des rémunérations misérables se trouvent, de plus en plus, en Chine, en Inde, dans quelques pays arabes et orientaux et en Russie. C'est la même chose en biologie et en bioinformatique, pour ce que j'en ai vu. Mes observations personnelles rejoignent celles de Zuppiroli (pp. 37-38).

Libero Zuppiroli, dans une interview au journal helvète Le Temps, n'exprime pas un grand enthousiasme pour cette évolution et ses brillants résultats : « Disons que je vis une histoire d'amour contrariée : quand je suis arrivé, je suis tombé amoureux de l'EPFL. C'était une femme en pleine maturité, ayant beaucoup de classe, d'humanité, de pudeur aussi – les chercheurs ne s'affichaient pas spécialement. Un accent mis sur l'enseignement, la formation des élites locales… Et tout à coup, à cause des politiques, on l'a surmaquillée, on a raccourci ses jupes… Je ne me sens plus chez moi, mais j'ai continué mon travail, j'ai dirigé mon laboratoire, et écrit mes traités… »

Mais, pourra-t-on objecter à Zuppiroli, vous critiquez l'application en Europe du modèle universitaire américain, mais vous ne pouvez pas nier que Harvard, Stanford, le MIT et Caltech soient de formidables pépinières de prix Nobel, des antres de savoir ? Certes, répond l'auteur (pp. 89-91), et d'ailleurs un professeur à Stanford a sans doute plus de liberté intellectuelle que son collègue européen. Comme la quinzaine d'universités américaines qui occupent le dessus du panier croulent sous des monceaux de dollars et jouissent d'une réputation telle qu'aucun chercheur au monde ne peut résister à une offre qui en émane, et qu'en outre les comités de lecture des meilleurs journaux scientifiques et les différentes instances de financement sont à leurs pieds, ne serait-ce que parce qu'ils en sont issus, leur succès est assuré. Et de surcroît, l'enseignement n'y est plus un problème, « car dans ces établissements d'élite les étudiants du premier et du second cycles (undergraduates) sont relativement peu nombreux (un à trois étudiants par membre du corps enseignant toutes catégories confondues). » (p. 90).

Qu'est-ce qui empêche les universités européennes d'en faire autant ? « La réponse est simple : l'École et l'Université sont encore conçues en Europe comme des services publics destinés à augmenter les capacités culturelles des populations locales. » (p. 91).

Créée en 1853 sur le modèle de l'École centrale de Paris, puis rattachée à l'université de Lausanne, l'EPFL a été formée par une inspiration que ses créateurs ont puisée à deux sources : l'université allemande, conçue par Humboldt comme une république des professeurs, et dont on peut rappeler qu'elle a servi de modèle aux meilleures universités américaines, et l'école d'ingénieurs française, incorporée au modèle républicain pour mettre l'enseignement scientifique au service de la nation.

Les derniers chapitres du livre de Libero Zuppiroli sont consacrés à un projet utopique : la fondation d'une institution universitaire d'enseignement et de recherche, baptisée Utopia, où seraient mises à nouveau au premier plan les exigences de l'esprit, la pensée plutôt que l'action, la liberté de la recherche plutôt que de rejoindre les « hordes de fourmis qui suivent tristement, en longues files, les chemins balisés des nanosciences, des biotechnologies et des sciences cognitives. » (p. 127). Utopia restera « attachée aux accords de Bologne », mais pas ceux de 1999, ceux de 1230, « qui établirent l'Université médiévale de Bologne dans son autonomie et ses structures démocratiques. » (p. 112).

Bref, ce livre est un pamphlet salubre qui invite à soumettre à la « disputatio médiévale » (p. 119) certaines des idées peut-être un peu trop vite considérées comme évidentes au sujet de la nécessaire (de toute façon nécessaire) réforme du système universitaire français.

Avoir des leaders dans la compétition universitaire mondiale

2010-04-15T17:49:17Z

- Lectures

L'informatique en France de la seconde guerre mondiale au Plan Calcul

2010-04-07T19:30:36Z

Observer la naissance d'une nouvelle science n'est pas une occasion qui se présente tous les jours : Pierre-Éric Mounier-Kuhn a su la saisir. À dire vrai, s'il a fait preuve d'à-propos, il y a mis aussi de la persévérance, parce que c'est depuis bientôt vingt-cinq ans que cet historien de formation et de métier consacre tout son temps aux archives des laboratoires et des industriels, quand il ne recueille pas les témoignages des acteurs, à qui il n'a pas manqué de faire lire et relire ses chapitres avant publication.

Ce volume de sept cents pages décrit la gestation de l'informatique à l'université et dans les laboratoires de recherche publics : deux autres volumes nous sont promis, respectivement dévolus aux rôles des entreprises et de l'État.

La recherche française ne peut guère se targuer d'avoir été à l'avant-garde de la création de l'informatique, et le désastre militaire de 1940 ne suffit pas à expliquer ce rôle effacé, puisque les Pays-Bas, le Danemark ou l'Italie ont été plus présents dans cette aventure.

C'est justement là que le livre de Pierre-Éric Mounier-Kuhn est passionnant : au-delà des péripéties parfois cocasses de la résistance du mandarinat scientifique aux idées nouvelles et de l'incapacité à profiter des expériences étrangères qui pourtant s'offraient à la coopération, c'est tout un paysage intellectuel français que nous décrit l'auteur, avec des effets qui vont bien au-delà de la seule informatique. L'impression générale qui se dégage de ces récits croisés ou affrontés, c'est que le principal handicap rencontré par les chercheurs français dans cette aventure fut l'absence de modestie.

La tradition nationale de l'allégeance ne fut pas pour rien non plus dans ce qu'il faut bien appeler un échec. Des chercheurs qui s'enferraient dans des voies qui de plus en plus évidemment ne menaient nulle part, mais qui jouissaient d'appuis politiques en haut lieu, comme Louis Couffignal, ont pu pendant des années accaparer les crédits et écarter les rivaux potentiels. Des potentats vieillissants regardaient avec morgue de jeunes chercheurs en mal de moyens, qui dans bien des cas n'ont eu comme ressource que l'émigration sous des climats plus accueillants. Les mathématiciens établis écrasaient de leur mépris ceux qu'ils voyaient comme des tâcherons.

Bien que non informaticien de formation, Pierre-Éric Mounier-Kuhn a réussi à saisir avec une grande finesse non seulement quantité d'aspects intellectuels de la science et de la technique informatiques, mais aussi ses aspects psychologiques et sociaux. Ainsi, c'est avec nostalgie que j'ai lu les pages qu'il consacre au centre de calcul (pp. 572 ett sq.), emplacement central imposé par l'unicité et l'encombrement de l'ordinateur et par l'inexistence de réseau, où se retrouvaient par la force des choses tous ceux qui avaient à faire avec l'informatique, et qui de ce fait était un lieu d'échanges d'expériences, de transmissions de savoirs, et aussi de camaraderie. Maintenant chacun est seul à son bureau devant son ordinateur individuel, c'est techniquement bien mieux mais humainement on y a perdu, ainsi qu'en échanges directs, que ne supplée pas la communication électronique.

Le chapitre VII, L'informatique, une discipline ? De la contestation à l'institutionnalisation (1966—1976), contient des pages quasi-tragiques, où l'on voit des esprits aussi brillants qu'André Lichnerowicz et Pierre Lelong faire passer à la trappe, le 30 mars 1965, (p. 478) le projet de créer une section d'informatique au CNRS, ou bien le gâchis du projet Cyclades (p. 533), dirigé par Louis Pouzin à partir de 1971, qui aurait pu placer une équipe française parmi les créateurs de l'Internet si les télécommunicants n'avaient pas eu sa peau au profit du modèle à circuits virtuels, plus commode pour la facturation détaillée des communications téléphoniques, mais totalement fermé et inapte à la prolifération spontanée qui a fait le miracle de l'Internet.

René de Possel (p. 474), bien que muni d'une forte légitimité mathématique de par sa participation à la fondation du groupe Bourbaki, sera en quelque sorte banni de la science à cause de son engagement informatique. À la tête de l'Institut Blaise Pascal en 1957 (p.278), il fut un grand semeur d'idées et initiateur de vocations. J'ai appris dans ce livre qu'il était le professeur de Maurice Audin, disparu, probablement mort sous la torture à Alger en 1957, dont il soutint la thèse in absentia. L'Institut Blaise Pascal fut le berceau parisien de la science informatique française, à côté des berceaux grenoblois (animé par Jean Kuntzmann et Louis Bolliet), toulousain et nancéen (Claude Pair).

Il y a aussi d'heureux événements : ainsi « Claude Pair considère l'appartition à Nancy en 1964 du cours de “Théorie des langages et compilation” comme le faire-part de naissance d'une science informatique en France. » (p. 511)

Jacques Arsac est bien sûr un personnage qui apparaît souvent dans le livre, ainsi p. 515 pour signaler l'époque où il se consacre à l'étude des systèmes d'exploitation, et les réflexions qu'ils lui inspirent : « Si l'analyse numérique est évidemment une branche des mathématiques, si la recherche en langages de programmation relève de la linguistique et de la logique, le développement des systèmes n'est l'application d'aucune science préexistante : il n'emprunte pas grand-chose aux mathématiques, il n'a pas encore de théorie propre — et ce n'est pas non plus une technique établie avec ses procédés sûrs et éprouvés. » C'est peut-être cette singularité qui a fait naître l'idée que puisqu'aucune science établie ne suffisait à embrasser l'informatique, il lui en fallait une propre.

Mounier-Kuhn en infère une idée, que je serais tenté d'adopter : « Avançons l'hypothèse que la diffusion de la gamme universelle IBM/360, ainsi nommée parce qu'elle couvre aussi bien les applications de gestion que le calcul scientifique, tandis que jusque-là ces domaines étaient équipés de types différents d'ordinateurs, a contribué à faire prendre conscience d'une unité fondamentale de l'informatique. » (note p. 515).

Nous ne saurions évoquer ces pionniers sans nommer Marcel-Paul Schützenberger, théoricien reconnu internationalement pour ses travaux sur les automates et les langages, un des inventeurs du concept de pile, au demeurant personnage fantasque et hors du commun à tous points de vue, qui a mis le pied à l'étrier de toute une génération.

Dès les premières pages du livre (pp. 49 et sq.) Pierre-Éric Mounier-Kuhn campe le sujet avec un rare mélange de précision, de concision et d'élégance ; quiconque cherche une définition des notions centrales de l'informatique et des ordinateurs, ainsi qu'un exposé lapidaire des circonstances de leur apparition, fera bien de s'y reporter.

Bref, une lecture indispensable. D'autant plus que pour un ouvrage sur papier glacé abondamment illustré de photos, de diagrammes et même de dessins humoristiques, le prix demandé par les Presses de l'université Paris-Sorbonne, plus ancien éditeur et imprimeur de France, est franchement un cadeau.

L'informatique dans l'enseignement secondaire

2010-03-22T20:25:06Z

Les résultats de l'informatisation en France sont médiocres à l'aune des comparaisons internationales. C'est d'eux que dépend la prospérité future de notre économie. Leur amélioration demande des actions dans plusieurs domaines, l'introduction de l'informatique dans l'enseignement secondaire n'est pas des moindres.

Il s'agit de l'informatique, pas des soit-disant TICE. L'informatique est une science constituée autour de quatre concepts :

algorithme ;
information ;
machine ;
langage.

La programmation des ordinateurs en est la discipline centrale. C'est elle que les élèves, de la seconde à la terminale au moins, doivent apprendre, à raison de trois heures par semaine. C'est comme ça. Parce que si l'on n'est pas passé par là, ce sont toutes sortes d'aspects du monde contemporain qui sont incompréhensibles. Parce que si l'on n'a pas acquis une compréhension sérieuse de ce qu'est la programmation d'un ordinateur, on ne sera pas en mesure de contribuer à l'informatisation de son entreprise, plus tard.

Lorsque l'on propose le programme énoncé ci-dessus à quelqu'un de raisonnable, il objecte : « vous n'y pensez pas ! Apprendre à programmer pour comprendre le monde : cet argument n'est pas recevable pour la plupart des élèves ».

J'emprunterai une réponse à la préface que Christian Queinnec a bien voulu consacrer à mon livre de système :

« “Pourquoi l'informatique est-elle si compliquée ?” J'entends, je lis, souvent, cette question. Elle dénote à la fois une incompréhension de ce que recouvre réellement l'informatique (manipuler une feuille de calcul dans un tableur ressortit-il à l'informatique ?), un effroi devant une révélation a priori déplaisante (l'informatique est complexe) enfin, un découragement devant l'effort supposé immense qu'il faudrait déployer pour dominer cette science.

Si l'on reprend les termes de cette question en les adaptant aux mathématiques, son inanité saute aux yeux car qui s'exclamerait “pourquoi les mathématiques sont-elles si compliquées ?”. Il est de notoriété publique que les mathématiques sont compliquées : un long apprentissage, comptant de nombreuses années d'étude et accompagné d'un discours approprié, nous en ont finalement persuadés. Tapoter une calculette, nous en sommes sûrs, ne s'apparente pas à faire des mathématiques et se tromper dans les touches n'est pas vécu comme une insuffisance en mathématiques. »

Filons ce parrallèlle, assez explicatif, entre les attitudes intellectuelles vis-à-vis des mathématiques d'une part, de l'informatique d'autre part : l'école, le collège, le lycée proposent à tous les élèves d'apprendre à faire des règles de trois. Beaucoup finissent par y arriver tant bien que mal. Un peu plus tard le programme comporte la résolution des équations du second degré, et un nombre non négligeable de bacheliers y parviennent.

Il n'est pas douteux que la maîtrise de la règle de trois soit très utile dans la vie pratique, mais que celle de l'équation du second degré soit rigoureusement sans usage pratique pour l'immense majorité de la population. Pourquoi l'enseigner alors ? Eh bien parce qu'en comprenant ce problème malgré tout assez simple, le lycéen entr'ouvre une porte qui lui permettra de comprendre l'activité des ingénieurs et des chercheurs, et par là une grande partie de ce qui se passe dans notre monde.

Une grande partie des élèves de l'enseignement secondaire considère comme irrecevable la prétention de leur faire apprendre les mathématiques pour comprendre le monde. Cette déclaration d'irrecevabilité n'a jamais été acceptée comme un argument recevable pour retirer les mathématiques des programmes de l'enseignement secondaire.

Informatique et informatisation III

Laurent Bloch — 2010-03-18T13:31:19Z

#Sommaire-

Science informatique et art de l'informatisation

Renversement sémantique

Le mot informatique, nous dit Michel Volle, désignerait tout autre chose que la science et la technique que avons pris l'habitude de désigner par ce terme : « La dialectique que recouvre selon moi le mot “informatique” réside dans l'alliage du cerveau humain et de l'automate : cerveau de l'utilisateur certes, mais aussi du programmeur... Cet alliage introduit dans la nature un être nouveau, dont il fait émerger les propriétés (tout comme l'alliage du cuivre et de l'étain a introduit un être nouveau, le bronze). Ces propriétés (possibilités et risques) concernent les individus, les ménages, les institutions. Dans le cas des institutions (et notamment des entreprises), l'APU (Automate programmable universel et ubiquitaire) s'allie à l'organisation des cerveaux humains, EHO (Être humain organisé), et l'alliage prend une forme spécifique, organisée. Sa mise en œuvre, c'est l'informatisation (de la société, de l'institution, de la vie personnelle). »

Cette nouvelle acception du terme informatique recouvre les concepts, les méthodes et les outils qui permettent de réaliser ce que l'on nomme communément un Système d'information (SI).

Ainsi, par ce rétablissement sémantique, l'informatique reviendrait à son origine étymologique : l'information est ce qui donne une forme (ce qui in-forme), que ce soit à l'être humain individuel ou, dans le cas qui nous intéresse, à l'être collectif qu'est l'entreprise. L'informatique est alors l'art de constituer ce squelette de l'entreprise, qui lui permet d'avoir une forme, et que l'on appellera système d'information.

Notez que dans le paragraphe qui précède j'ai parlé d'art et non pas de science ; l'exercice de constitution du système d'information est en effet plus proche de l'activité du médecin que de celle du mathématicien, et la médecine est un art plutôt qu'une science, même si, comme l'informatique au sens de Volle, elle emprunte beaucoup à diverses sciences : biologie, chimie, physique, statistique pour la médecine, mathématiques, logique, sociologie, économie pour l'informatique. L'informatique ainsi redéfinie, l'informatisation devient le processus par lequel les humains et les entreprises qu'ils ont créées acquièrent l'art de l'informatique, qui leur permet de construire les systèmes d'information qui les animeront. L'inconvénient de cette réforme sémantique est qu'elle laisse sans nom ce que nous appelions informatique jusqu'alors. Michel Volle propose plate-forme technique de l'informatique ou technique de l'informatique : l'informaticien que je suis ne saurait se résoudre à un telle réduction de la discipline qui est en train de transformer le monde et l'humanité. Il y a certes de la technique dans l'informatique au sens pré-vollien, mais cette technique est informée par la science qui lui donne, donc, sa forme.

Cette question de terminologie est-elle oiseuse ? Oui et non : le jour où le directeur de la recherche de l'Institut Pasteur, sous l'égide de qui je travaillais, m'a expliqué que l'apport de l'informatique à la biologie se comparait à celui de l'électrophorèse, j'ai compris que la question de l'informatisation de la science pasteurienne était en mauvaise voie et que nous ne rattraperions pas le retard pris sur les chercheurs d'autres pays, parce que là précisément la réduction de l'informatique à une simple technique de laboratoire avait des implications épistémologiques catastrophiques.

Rétablissement sémantique

Regardons autour de nous ce que donne la terminologie des autres cultures : justement, le numéro de février des Communications of the ACM (CACM) plaide pour la création de diplômes en Informatics, et explique que ce terme, récent outre-Atlantique, désigne là-bas plutôt l'enseignement de ce que l'on y appelle computing dans le contexte d'un autre domaine, donc ce que nous appellerions ici informatique appliquée, par exemple bioinformatique, alors que dans les universités européennes informatique traduit Computer Science, que l'on peut opposer à Information Technology (IT), de plus en plus à la mode pour désigner tout ce qui a trait à la plate-forme technique de l'informatique de Michel Volle.

Bref, tout cela n'est ni très simple ni très clair, alors je propose de conserver la terminologie en vigueur aujourd'hui : l'informatique désigne à la fois la science informatique (Computer Science) et les techniques qui en relèvent (Information Technology, IT). La réalisation d'un Système d'information (SI) mobilise des connaissances et des compétences en informatique, en logique, en économie, en sociologie, c'est un domaine qui possède une certaine autonomie.

L'informatisation peut s'entendre selon deux acceptions : au sens factitif ou volontariste elle désigne la réalisation du SI, c'est l'informatisation voulue ; en un sens plus passif elle évoque l'invasion de tous les domaines de la vie par les artefacts informatiques, c'est l'informatisation immanente.

L'informatisation immanente a lieu, volens nolens : cela ne saurait empêcher l'informatisation voulue d'échouer en tout ou en partie. Et c'est bien ce qui arrive, à tel point que les SI des entreprises peuvent être supplantés par l'informatique ambiante. Dans les universités par exemple Facebook et Twitter font concurrence aux Espaces numériques de travail (ENT), aux didacticiels et aux systèmes de gestion d'emplois du temps mis en place par les DSI.

Facteurs de succès (ou d'échec) de l'informatisation

Dans une entreprise, réaliser le SI nécessite des connaissances, des compétences, de la constance et une organisation adéquate basée sur le dialogue et la coopération. Le défaut de l'une ou plusieurs de ces qualités peut provoquer l'échec de l'entreprise.

Connaissances et compétences

La réussite de la construction du SI exige donc des des connaissances et des compétences dans les différents domaines évoqués plus haut, mais, malgré qu'on en ait, ce sont les compétences en informatique qui sont déterminantes, parce que ce sont celles qui seront le plus mises à contribution et qui sont les plus difficiles à se procurer.

C'est l'acquisition de ces connaissances et compétences qui représentera la part principale de l'effort d'informatisation. La réussite de toute l'entreprise exige un effort d'apprentissage qui concerne une large part de la population, sur une longue période, c'est-à-dire qu'il doit commencer au sein du système éducatif pour se poursuivre au long de la vie professionnelle.

Ce projet rencontre une difficulté (parmi d'autres) : l'incertitude qui règne quant à la nature exacte des connaissances et compétences en question. De nombreuses décennies ont établi et consolidé des corpus de connaissances qui permettent d'énoncer ce que doit savoir un ingénieur en mécanique automobile ou en génie chimique, tandis que rien de tel n'existe pour l'informatique. Comme chacun l'utilise, on croit souvent que la dextérité dans son usage est le signe d'une compétence pour construire des systèmes à base d'informatique. Et même dans le système éducatif la formation à la bureautique tient souvent lieu d'enseignement informatique. Cette confusion est source de grandes déconvenues et de qualifications inadaptées sur le marché du travail.

Il y a une autre confusion, plus insidieuse et donc plus dangereuse : la prolifération des méthodes de conduite de projet, des normes de qualité, des systèmes de management et autres modèles de maturité ont entraîné la multiplication des chefs de projet qui n'ont jamais maîtrisé autre chose qu'Excel pour établir des budgets et des plannings, des ingénieurs en génie logiciel qui n'ont jamais écrit une ligne de programme et des architectes de système qui ne sont que des utilisateurs de systèmes dont ils n'ont aucune idée de la structure interne.

L'existence de ces vastes populations mal formées, qui croient posséder des compétences qu'elles n'ont pas et qui occupent dans les organisations des postes de responsabilité technique, est une source de coûts dans les entreprises et d'échecs dans les projets. Pour chaque projet qui commence, il faut commencer avec un consultant qui va expliquer de quoi il s'agit, puis une assistance à maîtrise d'ouvrage qui va expliquer et écrire ce dont on a besoin : dans une entreprise dotée d'une DSI, ceci devrait être l'aboutissement d'une démarche interne.

La présence de l'informatique dans les programmes de l'enseignement secondaire est un bon indicateur de l'aptitude d'un pays à faire face aux évolutions exigées par l'informatisation, et de ce point de vue la France est fort mal placée : cf. par exemple sur le site de l'EPI. De façon générale, la France est assez mal placée du point de vue de la formation

Constance

L'informatique est un domaine où l'investissement demande des efforts soutenus et prolongés, parce que mener un projet à bien y prend beaucoup de temps. Cela n'est possible que si la direction de l'entreprise, munie d'une perception suffisamment claire des enjeux et des moyens à y consacrer, s'implique dans le projet.

L'investissement dans l'informatisation du SI est particulèrement complexe, lourd et incertain, parce qu'il est difficile de répondre à deux questions :

que faut-il faire ?
que peut-on faire ?

L'ingénieur qui conçoit un objet matériel dispose d'un ensemble d'outils conceptuels bien établis, notamment les lois de la physique et de la chimie, sur lesquels il peut s'appuyer pour élaborer son projet, l'expliquer à ses collègues et à son employeur, éventuellement par des dessins ou des maquettes, etc.

L'architecte de système d'information ne dispose de rien de tel, la matière dont il doit tirer la substance de son projet est mouvante, floue, variable. La complexité du processus d'informatisation est sous-estimée par les responsables à la formation insuffisante. Une cause récurrente d'échec de l'informatisation réside dans la difficulté éprouvée par beaucoup de dirigeants à se faire une idée raisonnable de ce qu'ils peuvent attendre de l'informatique, de ce que cela va coûter, et surtout de l'implication personnelle exigible de chacun pour que cela réussisse.

Dialogue et coopération

Tout projet d'informatisation est par nature un projet de collaboration. On a souvent tendance à percevoir cette collaboration comme une relation entre le commanditaire du projet, qui donne des ordres sous forme de cahier des charges, et un maître d'oeuvre, qui réalise. Cette vision inspirée du monde du bâtiment et des travaux publics a des limites qui découlent de différences évidentes entre les deux mondes :

visible – invisible ;
matériel – immatériel ;
irréversible – réversible.

La logique cahier des charges – maître d'oeuvre conduit au cycle de développement en V, qui présente l'avantage (fallacieux) d'une division du travail claire, mais l'inconvénient d'être inadapté à la réalité de la construction du SI.

Plan du cours d'algorithmes pour la biologie (BNF 103)

2010-03-07T17:19:00Z

Le cours suivra le plan suivant :

Définitions, notations, pseudocode

Exemple, Pseudo-code, pseudo-code->scheme, recherche dans une liste, complexité, notations asymptotiques.

Données et information

Quelques notions de base.

Graphes et arbres

Encores des notions de base...

Automates et machines de Turing

À l'attaque des vrais fondements.

Automates II : non-déterminisme

Après les automates à états finis déterministes, les automates non-déterministes, qui sont d'ailleurs équivalents.

Expressions régulières

La suite logique des automates, auxquels elles sont équivalentes.

Accélération d'un algorithme

Recherche du maximum d'un ensemble de valeurs, memoization de Fibonacci, recherche de segments maximaux O(n³), O(n²), O(n). On attaque l'algorithmique proprement dite.

Accélération de l'algorithme de Fibonacci

Un exemple.

Tris

Algorithmes de tri par insertion, recherche de maximum dans une liste, tri fusion, tri rapide, tri linéaire.

Structures de données élémentaires

Les pile, les files, le tas et tris par tas, les arbres, arbres binaires de recherche, tables de hashage.

Recherche de mots dans un texte

Force brute, Knuth-Morris-Pratt (KMP), Karp Rabin.

Le précédent en style récursif

Instrumentation d'un programme pour l'observer : KMP

Une variation autour du précédent.

Recherche de mots dans un texte (suite)

Structures de données Les arbres de mot-clés (keyword trees), les arbres de suffixes (suffix trees).

Recherche d'un motif dans un texte

Prosite, les expressions régulières, grep, les automates à état fini, expression régulières -> automates à état finis indéterministes, déterminisation d'un automate à état fini, minimisation d'automates à état finis.

Algorithmes sur les graphes

Le métabolisme, représentation de graphe, recherche de plus court chemin, recherche d'arbre couvrant minimal.

Algorithme de Needleman et Wunsch

Alignement de séquences.

Programmation dynamique

Recherche de séquences hydrophobes, comparaison de séquence par l'algorithme de Needleman et Wunsch, par l'algorithme de Smith et Waterman, optimisation de Gotoh, multiplication de matrices : minimisation des calculs.

Recherche dans des banques de données

Blast, Fasta, les matrices PAM.

Chaines de Markov

Prédiction de modèles de gènes, prédiction de structure, représentation de motifs fonctionnels.

Des problèmes difficiles : NP-complétude

Problème de la clique, Sat, voyageur de commerce.

Solution presque optimales

Simulated anealing, algorithmes génétiques...