Stage de Luminy 2001

Compte rendu général

Depuis une quinzaine d'années, le colloque "Algorithmique et Programmation" constitue un lieu de rencontre privilégié entre des enseignants de classes préparatoires aux grandes écoles, dispensant leur enseignement dans l'option informatique de la filière MP, et des chercheurs du CNRS, de l'INRIA et de l'Université. Cette année encore une trentaine de professeurs de classes préparatoires et une dizaine de chercheurs ont participé à cette rencontre, à la grande satisfaction de tout le monde.

Cette année, le colloque s'est tout particulièrement intéressé à deux sujets. En ce qui concerne l'algorithmique du génome, trois exposés ont montré les difficiles problèmes algorithmiques qui ont été résolus ou qui doivent encore être résolus dans le cadre du séquençage du génome. Trois autres conférences ont concerné l'éternel problème de l'enseignement informatique, le choix du langage d'apprentissage. Un exposé de Pierre Weis a montré comment on pouvait développer des interfaces utilisateurs en utilisant une surcouche du langage CAML, le plus utilisé pour l'enseignement en classes préparatoires. Deux autres exposés se sont intéressés au langage "à la mode" que constitue Java et ont montré qu'il pouvait aussi constituer un bon langagfe d'apprentissage de l'algorithmique et de la programmation.

Mais ce colloque tire aussi son intérêt de la diversité des sujets abordés, et trois autres conférences ont attiré l'attention des participants sur les nouvelles méthodes de résolution d'équations symboliques, les automates communicants par réseaux non fiables ou le domaine en pleine extension de la morphologie mathématique et des ses applications à de nouveaux algorithmes de décomposition et de traitement des images numériques.

Que tous ceux qui ont contribué à la réussite de ce colloque en soient vivement remercié, conférenciers mais aussi administration du CIRM qui nous a reservé son accueil habituel, c'est à dire remarquable tant par sa gentillesse que par son efficacité, sans oublier bien entendu la Société Mathématique de France.

Denis Monasse


Nicolas Sendrier: présentation de Java

Dans cet exposé les principaux attributs du langage Java ont été présentés. Tout d'abord les principaux éléments de la syntaxe ont été examinés puis certaines particularités du langage. Le point de vue adopté a été celui de l'enseignement. Après une brève discussion sur les avantage pédagogique du langage Java (syntaxe confortable, motivation des élèves, ...), les principaux composant du langages (mots-clés, opérateurs) ont été passés en revue. Dans une seconde partie, des aspects plus spécialisé du langage, comme les objets ou encore la gestion des exception ont été évoqués à partir d'exemples simples.

Documents:

Laurent Chéno: algorithmique du génome : automate des suffixes

Nous présentons ici l'automate des suffixes d'une chaîne : nous démontrons en particulier qu'il s'agit de l'automate minimal des suffixes, et décrivons une construction en temps linéaire de cet automate.

Nous proposons deux applications à la recherche d'un motif dans une chaîne de caractères : l'algorithme FDM \textit{(forward dawg matching)} qui repose sur une lecture de gauche à droite du texte et l'algorithme BDM \textit{(backward dawg matching)} qui déplace une fenêtre de gauche à droite, mais utilise l'automate des suffixes du miroir du motif en parcourant la fenêtre de droite à gauche.

Nous terminons par la mise en oeuvre effective des trois algorithmes (construction de l'automate, FDM et BDM), en utilisant le langage CamlLight.

Voir l'exposé complet ici

Philippe Schnoebelen : Automates communicant par canaux non fiables

On considère des systèmes d'automates finis qui communiquent de façon asynchrone en s'échangeant des messages le long de canaux fifo non-bornés. Ce modèle a la puissance des machines de Turing. Paradoxalement, si l'on suppose que les canaux peuvent perdre les messages de façon arbitraire, certaines propriétés d'analyse deviennent décidables, p.ex. la terminaison et l'accessibilité (deux résultats positifs reposant sur le Lemme de Higman). Toutefois, de nombreuses propriétés restent indécidables, p.ex. le caractère borné des canaux, ou bien l'atteignabilité répétée (= une infinité de fois) d'un état de contrôle. De même, il est impossible de calculer l'ensemble des configurations atteignables même si l'on sait qu'il s'agit d'un ensemble reconnaissable (car fermé vers le bas pour l'ordre de sous-mot). Notons que les propriétés décidables mentionnées plus haut ne peuvent pas être décidées en temps primitif récursif, ce qui les place d'emblée parmi les plus complexes des problèmes de vérification.

Biblio:


Pascal Monasse: Représentation morphologique d'images numériques et applications

Cette présentation sur le traitement des images se compose de deux parties. Dans un premier temps, je parle du filtrage itératif des images. Le seul filtre linéaire et isotrope est régi de façon infinitésimale par l'équation de la chaleur, ce qui détruit toute information utilisable dans l'image. En se restreignant à des filtres morphologiques, c'est-à-dire invariants par changement de contraste, le filtre le plus invariant géométriquement est invariant affine, les lignes de niveau se déplaçant suivant leur normale à la vitesse racine cubique de leur courbure. Malheureusement, ce filtrage détruit les jonctions en T, qui sont des indices forts d'occlusion.

La deuxième partie propose une nouvelle manière de représenter les images, un arbre de formes, les formes étant construites de façon simple à partir des composantes connexes des ensembles de niveau. Un algorithme, rapide en pratique, permet de décomposer toute image en son arbre de formes. Des manipulations simples de l'arbre permettent de simplifier considérablement la structure de l'image tout en préservant les jonctions en T. Enfin, je montre que les formes en question peuvent servir à recaler des images de façon plus robuste que les méthodes classiques, à base de corrélation.


Brigitte Mossé : Sequences genetiques et automate des suffixes

Apres une introduction aux sequences genetiques, nous avons presente un outil efficace pour la recherche d'un mot p dans une sequence : l'automate des suffixes, automate deterministe minimal reconnaissant les suffixes du mot p. Nous avons montre que la taille de cet automate est lineaire en la longueur de p. Une deuxieme partie algorithmique concernant cet automate est constituee par l'expose de Laurent Cheno.


Denis Monasse : structures de données: de Caml à Java, exemple de l'analyse syntaxique

Le langage Caml est le langage le plus utilisé dans l'enseignement de l'option informatique en classes préparatoires aux grandes écoles, de par ses grandes qualités pédagogiques résultant d'un typage fort et automatique et du mécanisme performant du filtrage. Il souffre cependant encore à l'heure actuelle de certains manques comme la portabilité du code compilé d'une machine à l'autre, l'absence de compilateurs sur certaines plate formes ou le peu d'outils disponibles pour développer des interfaces utilisateurs (même si le développement de Caml/Tk devrait remédier dans l'avenir à ce problème crucial, comme l'a montré par ailleurs Pierre Weis dans une autre conférence). Nous avons voulu présenter ici une sorte de dictionnaire entre les structures de données de Caml et les structures de données de Java, permettant dans certaines limites une traduction presque automatique de programmes Caml utilisant les types somme et le mécanisme du filtrage en des programmes Caml utilisant les classes abstraites (voire les interfaces) et le polymorphisme. Ce dictionnaire est illustré par l'exemple d'un analyseur syntaxique écrit en Java.

Programmes en Java (archive compressée, 360Ko)

B. Petazzoni: quelques problèmes et algorithmes liés à l'exploration du génome

L'exposé présente seize idées de problèmes d'informatique, qui pourraient être développés puis proposés aux étudiants de l'option informatique. La plupart sont accompagnées de références bibliographiques conséquentes.

Les trois dernières idées présentent des algorithmes liés au séquençage du génôme:

- la recherche d'une plus courte sur-chaîne (shortest super-string): elle intervient lorsque l'on veut "recoller" de courts fragments d'ADN (longueur de l'ordre de 400 bp) qui ont été séquencés par des méthodes biochimiques (électrophorèse sur gel). L'algorithme glouton a été intensivement étudié depuis 1990.

- les (0,1)-matrices ayant la propriété des 1 consécutifs: une fois que l'on a obtenu, avec les méthodes précédentes, des fragments longs (de l'ordre de 10000 bp) on va les placer les us par rapport aux autres, en utiisant la présence dans certains d'entre eux de "sites marqués". Algorithmiquement, ceci revient à trouver une permutation des colonnes d'une matrice à coefficients 0 ou 1, telle que la matrice permutée possède la propriété des 1 consécutifs. Booth et Lueker ont présenté en 1976 un algorithme efficace pour résoudre ce problème.

- les arbres PQ: il s'agit de la structure de données proposée par Booth et Lueker. Ce sont des arbres ayant deux types de noeuds: les fils d'un noeud P peuvent être permutés arbitrairement; les fils d'un noeud Q peuvent subir la permutation "miroir".

L'exposé de ces trois algorithmes est l'occasion de présenter quelques éléments culturels en biochimie et génomique.


Denis Lugiez: Resolution d'equations symboliques

Cet expose est consacre a la resolution d'equations entre arbres et plus generalement de formules generales du premier ordre sur le predicat d'egalite, les variables etant interpretees comme des termes clos (arbres sans variables).

Dans un premier temps nous decrivons les regles d'unification donnees par Martelli et Montanari en montrant comment un probleme d'unification se resoud par application de ces regles pour donner un systeme resolu (si les deux termes sont unifiables) ou echec dans le cas contraire. Il est alors aise de montrer que le systeme resolu est en fait une substitution qui est un unificateur le plus general (tout autre unificateur en est une instance). La terminaison de l'algorithme se montre par une mesure de terminaison simple que chaque regle fait decroitre et la correction est immediate compte tenu de la forme des regles d'unification.

Dans un deuxieme temps nous montrons que l'algorithme d'unification de Robinson qui correspond a une strategie d'application particuliere des regle peut avoir un cout polynomial en utilisant une structure de donnee partagee et en fusionnant a la fois noeud variable et noeuds fonctionnels quand ils ont ete identifies par unification. Cette technique est celle proposee par Corbin et Bidoit.

Pour finir nous montrons comment definir des formules egalitaires generales et comment leur donner une semantique. Puis nous indiquons des regles de transformation des problemes equationnels (dues a Comon et Lescanne) qui terminent (avec une bonne strategie), sont correctes et conservent l'ensemble des solutions. Quelques exemples lies a la programmation fonctionnelle illustrent l'application de ces regles.


Pierre Weis : Présentation de Ocaml/TK


Yves Lemaire