\documentstyle[11pt]{article} \parindent 0pt \parskip 3pt % fullpage.sty \marginparwidth 0pt \oddsidemargin 0pt \evensidemargin 0pt \marginparsep 0pt \topmargin 0pt \textwidth 6.5in \textheight 8.5 in \begin{document} \begin{center}{\large\bf GDR ALP\\ Projet de Groupe de Travail ALEA \\ (Structures Al\'eatoires Finies et Algorithmes)}\\ {\em pr\'esent\'e par\/} {\sc Philippe Flajolet}\\ Le 15 mars 1998 (r\'evision du 20 mars 1998) \end{center} \begin{small} \renewcommand{\baselinestretch}{0.9} \parskip 0pt {\bf R\'esum\'e.} L'objectif de ce groupe de travail est un brassage d'approches scientifiques et m\'ethodologiques vari\'ees telles \begin{quote} combinatoire \'enum\'erative, combinatoire analytique, m\'ethodes probabilistes, mod\`eles stochastiques continus, m\'ethodes issues de la physique statistique, \end{quote} appliqu\'ees aux structures discr\`etes fondamentales de l'informatique, notamment, \begin{quote} {mots, arbres, permutations, graphes, configurations g\'eom\'etriques, formules bool\'eennes. } \end{quote} Ces objets sont pr\'esents dans de nombreux domaines de l'informatique fondamentale, tels, \begin{quote} structures de donn\'ees pour la recherche rapide de l'information, recherche de motifs (``pattern matching''), optimisation combinatoire et algorithmes d'approximation probabilistes, algorithmique g\'eom\'etrique et al\'eatoirisation, algorithmique r\'epartie et protocoles, etc. \end{quote} \end{small} \section{Th\`emes de travail} Ce document propose un Groupe de travail (GDT) au sein de la nouvelle structure de GDR/PRC {ALP} (Algorithmique, Langage et programmation). Son but est de regrouper l'ensemble des chercheurs travaillant dans le domaine des structures combinatoires finies, etudi\'ees pour leurs propri\'et\'es al\'eatoires (probabilistes, en moyenne, en distribution) et en liaison avec l'algorithmique s\'equentielle ou distribu\'ee ainsi qu'avec les structures de donn\'ees de base de l'infor\-ma\-tique. Les principales orientations m\'ethodologiques du GDT, en accord avec le r\'esum\'e, sont \begin{enumerate} \item Propri\'et\'es des structures discr\`etes de l'informatique en vue de leurs applications \`a l'analyse d'algorithmes s\'equentiels ou distribu\'es examin\'ees selon les aspects \begin{itemize} \item[---] \'enum\'eration exacte, \item[---] analyse asymptotique, \item[---] propri\'et\'es probabilistes. \end{itemize} \item Mod\`eles probabilistes discrets ou continus de l'\'evaluation de performances des principaux objets discrets de l'informatique. \item Algorithmique probabiliste fond\'ee sur des analyses math\'ematiques pr\'ecises et rigoureuses dans divers domaines tels \begin{itemize} \item[---] structures de donn\'ees fondamentales de l'informatique, \item[---] algorithmes dits ``randomis\'es'' notamment dans le contexte de l'algorithmique g\'eom\'etrique, \item[---] graphes al\'eatoires et optimisation combinatoire, \item[---] algorithmique arithm\'etique et ``semi-num\'erique'', \item[---] algorithmique de la manipulation symbolique et du calcul formel, \item[---] algorithmique distribu\'ee. \end{itemize} \item Formules bool\'eenes al\'eatoires, ph\'enom\`enes de seuil, et approches issues de la physique statistique. \item G\'en\'eration al\'eatoire et acc\'el\'eration des m\'ethodes de simulation dans le domaine des structures discr\`etes. \end{enumerate} Le but commun des \'equipes participantes est donc l'analyse fine des propri\'et\'es des structures discr\`etes de l'informatique (envisag\'ees sous l'aspect al\'eatoire) et l'exploitation de leur propri\'et\'es (\'enum\'eratives ou probabilistes) \`a fin d'\'evaluation et d'optimisation des algorithmes de base dans des domaines divers de l'informatique. Quelques exemples plus pr\'ecis de domaines auxquels le groupe de travail s'attachera: \begin{itemize} \item mots et suites al\'eatoires (possibilit\'e de jonction avec des travaux d'origine biologique notamment); \item arbres et permutations al\'eatoires avec application aux structures de donn\'ees, \`a l'algorithmique de la recherche en g\'en\'eral; \item graphes al\'eatoires et formules bool\'eennes al\'eatoires et algorithmes correspondants d'optimisation, de satisfiabilit\'e, etc. \item objets g\'eom\'etriques al\'eatoires (ensembles de points, de segments, etc) et algorithmes ``al\'eatoiris\'es'' (randomis\'es); \item algorithmique distribu\'ee et algorithmique de la communication (protocoles, routage). \end{itemize} \section{Fonctionnement} Il s'agit de f\'ed\'erer les \'equipes et individus travaillant en France sur ces th\`emes. Ceux-ci sont principalement (mais non exclusivement) membres de l'ex-GDR/PRC AMI. Le projet a vocation de regrouper des composantes repr\'esentant un \'eventail \`a la fois large par ses approches m\'ethodologiques, mais cibl\'e par son objet. Au cours de la periode ecoul\'ee, 1995-1998, le Groupe ALEA a soutenu un certain nombre de manifestations: \begin{itemize} \item[---] Journees ALEA de Grenoble (B. Ycart, P. Flajolet), mai 1996; \item[---] Journees GASCOM de Caen (J-G. Penaud, A. Denise), f\'evrier 1997; \item[---] Journees ALEA d'Asnelles (B. Vallee, B. Ycart); fevrier 1998 \end{itemize} La participation a \'et\'e de 25 \`a 45 personnes pour ces r\'eunions, la quasi-totalit\'e des \'equipes constituantes \'etant repr\'esent\'ees. {\bf 1.} Le groupement qui est propos\'ee est une structure transversale l\'eg\`ere d\'edi\'e en priorit\'e \`a l'organisation d'une {\sl rencontre annuelle} (environ 50 personnes, 5 jours) sur les th\`emes d\'ecrits ci--dessus. Il est demand\'e au GDR ALP de soutenir prioritairement cette r\'eunion g\'en\'eraliste, soit \begin{quote} Journ\'ees ALEA. 40 missions/invitations $\times$ 2000F = 80kF. \end{quote} La r\'eunion est pr\'evue en r\'egion bordelaise pour une dur\'ee de 5 jours en mars-avril 1999 (organisation Labri, responsable J.-G. Penaud) o\`u seront jumel\'ees \`a part \'egales les rencontres Al\'ea et les rencontres Gascom d\'edi\'ees plus sp\'ecialement \`a la g\'en\'eration al\'eatoire. {\bf 2.} {\sl Bourses d\'echanges de doctorants.} Il s'agit de bourses destin\'ees exclusivement \`a financer l'\'echange de doctorants ou de chercheurs postdoctoraux ($\le$ th\`ese+2) entre deux laboratoires g\'eographiquement distants. Le dossier est directement mont\'e par les deux jeunes chercheurs concern\'e qui d\'etaillent en deux pages maximum leur programme de travail (exploration d'une question, publication commune, etc). Il s'agit, apr\`es approbation du comit\'e A\'ea de soutenir deux s\'ejours crois\'es d'environ 10 jours chacun, \'etal\'es sur une p\'eriode maximale de 3 mois. \begin{quote} 5 bourses d'\'echanges $\times$ 6kF = 30 kF. \end{quote} {\bf Contribution totale demand\'ee}: 80+30 = \dotfill 110 kF. \section{Composition du groupe de travail} Le GDT Al\'ea regroupe environ 115 membres (dont un peu plus de la moiti\'e sont des ``permanents''), issus d'une dizaine d'\'equipes fortement structur\'ees, ainsi que des membres associ\'es. \begin{enumerate} \item {\bf \'Equipe Analyse d'algorithmes et calcul formel.}\\ INRIA Rocquencourt et Universit\'e Paris 6. {\em Membres:} P. Flajolet (DR), M. Soria (Pr); B. Salvy (CR), M. R\'egnier (DR), P. Robert (DR). Doctorants: F. Chyzak, C. Chabaud, J.-M. Waechter, J.F. Dantzer. {\em Th\`emes:} Structures de donn\'ees et analyse en moyenne: combinatoire analytique, m\'ethodes asymptotiques, calcul formel. M\'ethodes symboliques pour les d\'enombrements combinatoires, liens avec le calcul formel et l'analyse automatique de structures de donn\'ees et d'algorithmes combinatoires. M\'ethodes asymptotiques fond\'ees sur l'analyse complexe et lois limites en algorithmique et structures discr\`etes. Applications aux arbres de termes en calcul symbolique, aux arbres de recherche (par exemple multidimensionnels), aux mots al\'eatoires, \`a l'algorithmique distribu\'ee (protocoles) et probabiliste. G\'en\'eration al\'eatoire. {\em Publications.} Patterns in Random Binary Search Trees, P. Flajolet, X. Gourdon, C. Martinez. Random Structures and Algorithms, volume 11 (3), October 1997, pp. 223-244. Random Polynomials and Polynomial Factorization, P. Flajolet, X. Gourdon, and D. Panario. In Proc. 23rd ICALP Conference, Lect. Notes in Comp. Sc. vol. 1099, pp. 232-243. Non-commutative elimination in Ore algebras proves multivariate holonomic identities. Chyzak (F), Salvy (B). Journal of Symbolic Computation, 1998; in print. On pattern frequency occurrences in a markovian sequence. R\'egnier (M.) and Szpankowski (W.). In International Symposium on Information Theory, Ulm, Germany, 1997. An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet, Addison Wesley (1996), 512p. (French translation by C. Chabaud, published by International Thomson Publishing France 1996, 421p.) \item {\bf Equipe d'algorithmique du LIX.}\\ LIX, Ecole Polytechnique, 91128 Palaiseau Cedex.\\ Jean-Marc Steyaert, steyaert@lix.polytechnique.fr. {\em Membres:} Robert Cori, professeur a` l'X, Jean-Marc Steyaert, ma{\^\i}tre de confe'rences a` l'X, Doctorants: Michel Nguyen The', Dominique Rossin, Fabrice Torossian. {\em Th\`emes.} Trois the`mes sont e'tudie's: l'analyse d'algorithmes, la combinatoire des cartes et des graphes, des applications aux te'le'communications. Sur le premier point, on insistera sur les syste`mes de re'e'criture sur les mots et les arbres pour e'tudier les distributions des parame`tres de complexite'. Sur le second point on poursuivra des travaux sur les cartes, graphes et les me'thodes bijectives tout en s'inte'ressant au comportement asymptotique des quantite's e'nume're'ees. Sur le troisie`me point, qui de'marre, en principe par une convention CIFRE on devrait s'attaquer a` des questions d'attributions optimales de fre'quences, ce qui revient a` traiter des proble`mes d'optimisation combinatoire par des algorithmes probabilistes. \item {\bf Projet GASCOM-Equipe combinatoire du LABRI.} Responsable du Projet: Jean-Guy Penaud, labri, Universit\'e Bordeaux I 33405 Talence cedex penaud@labri.u-bordeaux.fr {\em Membres:} M. Bousquet-M\'elou R. Cori M. Delest S. Dulucq M. Mosbah M. Robson N. Saheb X. Viennot. Doctorants: G. Schaeffer J. P. Duchon {\em Th\`emes:} G\'en\'eration al\'eatoire: utilisation des m\'ethodes bijectives pour en\-gendrer des classes sp\'ecifiques d'objets de fa{\c c}on performante et de m\'ethodes r\'ecursives (les grammaires d'objets). Combinatoire: plus g\'en\'eralement l'approche bijective, pris\'ee dans l'\'equipe Cori-Viennot, conduit \`a la connaissance de la structure profonde des objets manipul\'es, et d\'ebouche sur l'\'enum\'eration et l'algoritmique (CALICO). Animaux dirig\'es et percolation. Etude approfondie de ces mod\`eles issus de la physique Graphes et marches al\'eatoires: application des automates et des langages reconnaissables \`a l'\'etude des marches avec des probabilit\'es non uniformes. {\em Publications:} DULUCQ S. et GUIBERT O. Stack words, standard tableaux and Baxter permutations. Discrete Math., vol.157, 1996, pp. 91--106. BOUSQUET-M\'ELOU M. Percolation models and animals. European J. Combin., vol. 17, 1996, pp. 343--369. BOUSQUET-M\'ELOU M. New enumerative results on two-dimensional directed animals, DISCRETE MATH., \`a para{\^\i}tre. DEL LUNGO A., DEL RISTORO F. et PENAUD J.-G. Left ternary trees and non separable rooted planar maps. Theoret. Comput. Sci., \`a para\^{\i}tre. DEVROYE L., ROBSON J. M, On the generation of random binary search trees, SIAM J. Computing, 24, 1995, 1151-1150. M. MOSBAH , N. SAHEB, A Syntactic Approach to Random Walks on Graphs,23rd International Workshop, WG'97, R. H. Mohring, 1997, 258--272, Lect. Notes. Comput. Sci.~1335, Berlin, Allemagne SCHAEFFER G., Bijective cursus and random generation of Eulerian planar maps with prescribed vertex degrees, Electronic J. Combinatorics 4 (1997) R20. {\em Commentaires:} Il est clair que les th\'emes propos\'es par ALEA d\'epassent le seul projet GASCOM et int\'eressent l'ensemble de l'\'equipe de combinatoire \'enum\'e\-rative du Labri, ainsi que des chercheurs d'autres \'equipes voisines du laboratoire comme R. Cori M. Robson et N. Saheb de l'\'equipe de combinatoire et algorithmique distribu\'ee (eq. Cori), d'une part, et M. Mosbah de l'\'equipe de Lagages formels et Graphes (eq Courcelle). Il s'agit donc l\`a d'une r\'eponse conjointe de participants au groupe de travail GASCOM et au groupe de travail de combinatoire \'enum\'erative. \item {\bf Algorithmique et Complexit\'e du LRI Orsay}. \\ Miklos Santha, santha@lri.fr {\em Membres':} Jean-Paul Allouche (DR CNRS) St\'ephane Boucheron (CR CNRS) Michel de Rougemont (Pr) Alain Denise (MC) Wenceslas Fernandez De La Vega (CR CNRS) Dominique Gouyou-Beauchamps (Pr) Claire Kenyon (Pr) Yannis Manoussakis (Pr) Miklos Santha (CR CNRS) Jean-Pierre Tillich (MC). Doctorants: Dalila Abdelkader Cristina Bazgan Khadidja Benabdellah Sylvie Corteel S\'ebastien Dhuime David Gross Huong L. Thanh Fr\'ed\'eric Magniez Fabrice Noilhan Kave Salamatian Julien Stern Yann Verhoeven. Post-doctorants: Abdelkrim Amoura Sophie Laplante Bernd Loescher Abraham Sharell {\em Th\`emes:} Complexit\'e probabiliste; graphes al\'eatoires, satisfaisabilit\'e des formules bool\'eennes al\'eatoires, algorithmes probabilistes et algorithmes d'approximation pour l'optimisation combinatoire, comptage approximatif randomis\'e. G\'en\'eration al\'eatoire et combinatoire : d\'e\-nom\-brement de structures combinatoires, conception et analyse d'algorithmes de g\'en\'eration uniforme, combinatoire des mots. {\em Publications:} A.K. Amoura, E. Bampis, C. Kenyon et Y. Manoussakis, Scheduling Multiprocessor Tasks on Dedicated Processors, European Symposium on Algorithms '97. S. Boucheron et D. Gardy, An Urn Model from Learning Theory, Random Structures and Algorithms, Vol. 11, 1997, pp 43--67. A. Denise et P. Zimmermann, Uniform Random Generation of Decomposable Structures Using Floating-Point Arithmetic, Rapport INRIA 3242, septembre 1997, \`a para{\^\i}tre dans Theoretical Computer Science. S. Ivanov et M. de Rougemont, Interactive proofs on the reals, Symposium on Theoretical Aspects of Computer Science, 1998, LNCS, pp 500--512. C. Kenyon, Y. Rabani et A. Sinclair, Biased Random Walks, Lyapunov Functions and Stochastic Analysis of Best Fit Bin Packing, \`a para{\^\i}tre dans Journal of Algorithms. H. L. Thanh, C. D\"urr et M. Santha, A decision procedure for well-formed linear quantum cellular automata, Random Structures and Algorithms, Vol. 11, No. 4, 1997, pp. 381--394. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%= %%%%%% \item {\bf Equipe caennaise d'algorithmique.} \\ Responsable: Brigitte Vallee, GREYC, Departement d'Informatique Universite de Caen, 14032 Caen. Brigitte.vallee@info.unicaen.fr {\em Membres:} Brigitte Vallee (Pr). Doctorants: Ali Akhavi, ali.akhavi@info.unicaen.fr Julien Clement, julien.clement@info.unicaen.fr Jean-Marie Le Bars, jean-marie.lebars@info.unicaen.fr {\em Th\`emes:} Analyse dynamique des algorithmes notamment en arithmetique et en theorie de l'information. Analyse en moyenne de l'algorithme LLL. Analyse en moyenne des parametres d'arbres digitaux hybrides. Probabilites asymptotiques dans les fragments de la logique du second ordre. {\em Publications:} {Brigitte Vall\'ee.}{\sl Op\'erateurs de Ruelle-Mayer g\'en\'eralis\'es et analyse en moyenne des algorithmes de Gauss et d'Euclide}, Acta Arithmetica LXXXI.2 (1997), pp 101--144. {Philippe Flajolet, Brigitte Vall\'ee, } {\sl Continued fraction algorithms, functional operators, and structure constants}, (en collaboration avec Philippe Flajolet), Theoretical Computer Science (1998), vol 194, 1--2, pp 1--34. {Brigitte Vall\'ee, } {\sl Dynamical systems and average--case analysis of general tries}, pr\'esent\'e au Congr\`es RALCOM'97 (Randomized algorithms and Computing, Ile Santorin, octobre 97), [16 p]. {Julien Cl\'ement, Philippe Flajolet, Brigitte Vall\'ee, } {\sl The analysis of hybrid trie structures}, (en collaboration avec Julien Cl\'ement et Philippe Flajolet), pr\'esent\'e au congr\`es SODA'98 (Symposium on Discrete Algorithms) (San Francisco, janvier 98), Comptes-Rendus de SODA'98, pp 531--540 {Brigitte Vall\'ee, } {\sl The complete analysis of the Binary Euclidean Algorithm}, ANTS'98 (Algorithmic Number Theory Symposium, Portland, USA, Juin 98), \`a para\^\i tre dans les actes (LNCS) {Jean-Marie Le Bars,} {\sl A kernel property to characterize $\Sigma _1^1 $ fragments for which the 0-1 law fails.}, LICS'98, (meilleur article \'etudiant) \item {\bf Formules bool\'eennes al\'eatoires, satisfiabilit\'e.} \\ Responsable: Olivier Dubois, Universit\'e Paris 6, Olivier.Dubois@lip6.fr {\em Th\`eme:} Recherche d'algorithmes complets ou incomplets, deterministes ou stochastiques pour le probleme de Satisfiabilite, analyse de la complexite en moyenne. Etude du phenomene de seuil de satisfiabilite. Reconstruction de polyominos donnes par leurs projections orthogonales. {\em Publications:} O. Dubois and Y. Boufkhad, a general upper bound for the satisfiability threshold of random r-SAT formulae, Journal of algorithms 24 (2), p. 395:420, 1997 \item {\bf Projet MAI/IMAG, Mod\`eles Al\'eatoires et Informatique.}\\ B. Ycart (Professeur UJF).\\ Laboratoire de Mod\'elisation et Calcul, IMAG, BP 53, 38041 GRENOBLE CEDEX.\\ Bernard.Ycart@imag.fr {\em Membres:} E. CRETOIS Ma\^\i tre de conf\'erences UMPF, O. FRAN\c{C}OIS Ma\^\i tre de conf\'erences ENSIMAG, O. GAUDOIN Ma\^\i tre de conf\'erences ENSIMAG, J.L. SOLER Professeur ENSIMAG, B. VAN CUTSEM Professeur \'em\'erite UJF, J.M. VINCENT Ma\^\i tre de conf\'erences UJF, M. VIOT Charg\'e de recherches CNRS, B. YCART Professeur UJF. Doctorants: C. LABBE, L.M. OULD MOHAMED ABDALLAHI, C. ZAHALCA {\em Th\`emes:} Mod\`eles probabilistes et informatique: Structures aleatoires discretes (graphes aleatoires, dissimilarites structures en logique de description); Algorithmes stochastiques (reseaux de neurones, algorithmes evolutionnaires, methodes MCMC, vitesse de convergence; G\'en\'eration al\'eatoire; Analyse probabiliste d'algorithmes; Fiabilite des logiciels. {\em Publications:} {\it Une pr\'esentation de MAI avec r\'esum\'es des rapports en ligne et acc\`es au texte int\'egral est disponible sur le r\'eseau} ({\tt http://www-lmc.imag.fr/MAI}). [1] VAN CUTSEM, B., YCART, B. Indexed dendrograms on random dissimilarities. {\em Rapport MAI 23 (mars 96). A para\^\i tre J. of Classification (1998).} [2] FRAN\c{C}OIS, O., An evolutionnary strategy for global minimization and its Markov chain analysis. {\em Rapport MAI 50 (d\'ecembre 97)}. [3] YCART, B. Cutoff for samples of Markov chains. {\em Rapport MAI 51 (f\'evrier 98). Soumis \`a ESAIM--PS.} [4] LE BRETON, A., SOLER, J.L. On the failure rate of components subjected to a diffuse stress environment. {\em Rapport MAI 52 (f\'evrier 98). A para\^\i tre dans Mathematical Methods in Reliability, Birkh\"auser (1998).} [5] ELHAIK, Q., ROUSSET, M.C., YCART, B. Generating random benchmarks for description logics. {\em Rapport MAI 54 (mars 98). Soumis \`a DL'98.} \item {\bf Polyn\^omes, Combinatoire, et Arithm\'etique (Polka).} \\ Responsable: Paul Zimmermann INRIA-Lorraine 615, rue du Jardin Botanique BP 101 54602 Villers-les Nancy Paul.Zimmermann@loria.fr {\em Membres:} Guillaume Hanrot (CR INRIA au 1/6/98) Gregory Kucherov (CR INRIA) Fabrice Rouillier (CR INRIA) Alain Giorgetti (PrAg UHP) Jean-Luc R\'emy (CR CNRS) Jocelyne Rouyer (MC UHP). Doctorants: Vladimir Grebinski (th\'esard INRIA) {\em Th\`emes:} Calcul num\'erique fiable Factorisation de polynomes G\'en\'eration al\'eatoire Algorithmes combinatoires d'analyse de s\'equences Algorithmes de recherche combinatoire {\em Publications:} Denise, A., and Zimmermann, P., Uniform random generation of decomposable structures using floating-point arithmetic, INRIA Rapport, n.3242, 1997. Grebinski, V. and Kucherov, G., Optimal Reconstruction of Graphs Under the Additive Model, Proceedings of ESA'97, Lectuer Notes in Computer Science, vol 1284, 1997. Kucherov, G., and Rusinowitch, M., Matching a set of strings with variable length don't cares, Theoretical Comput. Sci. 178, (1997), 129--154. Alonso, L., R\'emy, J.-L., and Schott, R., A linear-time algorithm for the generation of trees, Algorithmica 17, (1997), 162--182. Dubernard, J. and Dutour, I., Enum\'eration de polyominos convexes dirig\'es, Discrete Math. 157, (1996), 79--90. \item {\bf Analyse d'algorithmes distribue's (Paradis)} \\ Responsable: LAVAULT Christian LIPN, CNRS UPRES-A 7030 Universite' Paris-Nord avenue J.-B. Cle'ment 93430 Villetaneuse E-mail : christian.lavault@lipn.univ-paris13.fr {\em Membres:} Christian Lavault, Vassilis Zissimopoulos et Franck Butelle (LIPN, Paris 13). Ivan Lavalle'e (Paris 8). Jean-Frederic Myoupo, Vincent Villain, Franck Petit, Alain Bui, Vassilis Giakoumanis (LaRIA, Amiens). Marc Bui (Prao, Compiegne). Doctorants: Yacine Zehani (LIPN), Eric Angel (LRI). Olivier Flauzac, Jean-Marie Vanherpe (LaRIA). Fatima Belkouch, Tho N'guyen, Victor Larios (Prao). {\em Th\`emes:} De tr\`es nombreux algorithmes distribu\'es utilisent les propri\'et\'es et structures combinatoires de type al\'eatoires (syst\`emes "anonymes", algorithmes distribu\'es tol\'erants aux fautes transitoires: algorithmes "auto-stabilisants", etc.). Par ailleurs, l'analyse en moyenne de ces algorithmes et des structures de donn\'ees distribu\'ees fait \'evidemment intervenir des techniques probabilistes classiques. Structures ale'atoires discr'etes Algorithmes probabilistes et structures de donne'es Analyse d'algorithmes distribue's Me'thode de marches ale'atoires dans les graphes (complexite' en temps de stabilisation des algorithmes auto-stabilisants) {\em Publications:} F. Butelle, C. Lavault et M. Bui. "A uniform self-stabilizing minimum diameter spanning tree algorithm", WDAG'95, LNCS 972, S-V, p. 257-272. A. Calabrese et C. Lavault. "A simple distributed algorithm for the D+1 coloring of arbitrary networks", WDAG'96, LNCS 1151, S-V, p. 123-140. O. Flauzac et V. Villain, "An implemantable dynamic automatic self-stabilizing protocol", I-SPAN'97, p 91-97, 1997. A. Petit et V. Villain. "Color optimal self-stabilizing depth first token circulation for asynchronous message passing systems", PDCS-97, p 227-233. ISCA, 1997. \item {\bf Structures aleatoires discretes.}\\ Herv\'e Daud\'e, CMI universite de Provence. 39, rue Joliot Curie, Technopole de Chateau Gombert 13453 MARSEILLE cedex 13; daude@gyptis.univ-mrs.fr {\em Membres:} Belaid Benhamou (MC), Universite de Provence, Departement d'informatique, Laboratoire LIM, Nadia Creignou (MC), Universite de Caen, Departement de Mathematiques, Laboratoire SDAD, Herv'e Daud'e (MC), Universit\'e de Provence, Departement de Mathematiques, Laboratoire IML, Philippe Je'gou (MC), Universite de Provence, Departement d'informatique, LIM, Pierre Liardet (PR), Universit\'e de Provence, Departement de Mathematiques, Laboratoire IML, Pierre Siegel (PR), Universite de Provence, Departement d'informatique, LIM, Doctorants: (Universite de Provence) Gilles Audemard (LIM) Fabrice Bouquet (LIM) Lamiar Keddar (LIM) {\em Th\`emes:} L'alea discret federe les activites scientifiques de notre equipe autour de deux sujets principaux. Le premier concerne l'etude des algorithmes de resolution de problemes difficiles sur des instances aleatoires. Pour le probleme SAT, une approche statistique du comportement des algorithmes de resolution a revele l'existence d'un pic de difficulte; Belaid Benhamou et A. Chmeiss [1] ont distingue ce phenomene dans les problemes de satisfaction de contraintes (CSP) discrets \`a domaines finis et differentes heuristiques pour ameliorer la methode de resolution dite de Forward Checking ont ete proposees. Philippe Je'gou et A. Chmeiss travaillent actuellement sur des methodes de resolution de CSP basees sur des techniques de decomposition; les resultats experimentaux montrent une erosion significative du pic de difficulte: phenomene qui reste \`a elucider. Une explication du pic de difficulte pour SAT est l'existence d'un phenomene de seuil pour la satisfaisabilite des formules SAT aleatoires; le second sujet interessant notre equipe concerne l'etude des proprietes des instances aleatoires d'algorithmes. En utilisant la terminologie des graphes al\'eatoires, Nadia Creignou et Herve' Daude' [3] ont donn\'e la distribution limite qui decrit le phenomene de seuil pour le probleme XORSAT. Philippe Je'gou et A. Chmeiss [2], ont introduit des classes de graphes (CSG(k)) generalisations des graphes triangules, Lamia Keddar \'etudie actuellement la repartition des graphes aleatoires dans ces classes. Notre \'equipe propose ainsi d'aborder certains problemes algorithmiques \`a la fois par l'expe\-rimentation statistique et par l'analyse probabiliste. {\em Publications:} [1] Belaid Benhamou \& Assef Chmeiss, Some heuristics for forward checking method in CSP's, 7th International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA-96), Sozopol, IOS Press, pages 21-24, september 1996. [2] Assef Chmeiss \& Philippe Je'gou, A generalization of chordal graphs and the maximum clique problem, Information Processing Letters, Vol 62, pages 61-66, 1997. [3] Nadia Creignou \& Herve' Daude', Satisfiability threshold for random XOR-CNF formulae, rapport de recherche de l'I.M.L. UPR 9016, Prepublication 1996 - 20, 13 pages, Soumis \`a la revue Discrete Applied Math. \item {\bf Groupe de Versailles.} \\ Daniele Gardy Laboratoire PRISM, Universite de Versailles St Quentin 45 avenue des Etats-Unis, 78035 Versailles cedex tel: 01 39 25 43 31 fax: 01 39 25 40 57 e-mail: gardy@prism.uvsq.fr {\em Membres:} Brigitte CHAUVIN (professeur UVSQ) Serge COHEN (MC UVSQ) Daniele GARDY (Professeur UVSQ) Abdelkader MOKKADEM (professeur UVSQ) Mariane PELLETIER (MC UVSQ) Nihal PEKERGIN (MC Paris 1) Franck QUESSETTE (MC UVSQ) Alain ROUAULT (Professeur UVSQ). Doctorants: Jean JABBOUR Laurent NEMIROVSKI Alexis TROUBNIKOFF {\em Th\`emes:} Les themes abordes concernent l'etude probabiliste de structures issues de l'informatique. Plus precisement, le groupe travaille sur les sujets suivants : - traitement probabiliste des arbres et grandes deviations; - algorithmes stochastiques; - analyse d'algorithmes et de structures de donnees : allocations aleatoires, applications aux bases de donnees; - generation de structures aleatoires, dans une optique "chaines de Markov", et ordres stochastiques. {\em Publications:} S. Boucheron, D. Gardy. An urn model from learning theory. Random Structures and Algorithms, Vol. 10, 43-67, janvier 1997. B. Chauvin. Product martingales and stopping lines for branching brownian motion. Annals Probab. Vol. 19, 3, 1195-1205, 1991 J. M. Fourneau, L. Mokdad, N. Pekergin. Bounding the loss rates in a multistage ATM switch. Proceed. of Tools'97, St. Malo France, LNCS 1245 (eds. Marie et al.) Springer Verlag. 1997. Q. Liu, A. Rouault. On two measures defined on the boundary of a branching tree. In Classical and Modern Branching Processes. Eds Athreya, Jagers. IMA Proceedins 84, 187-201, 1997. M. Pelletier. Sur le comportement asymptotique des algorithmes stochastiques. These de doctorat, Universite Paris-Sud, 1996. \item {\bf Arithmetique aleatoire.}\\ Jean-Marc Deshouillers, Math\'ematiques Stochastiques, Universit'e Victor Segalen Bordeaux 2, 33 076 BORDEAUX Cedex; J-M.Deshouillers@u-bordeaux2.fr {\em Membres:} Francois HENNECART, Bernard LANDREAU, Guillaume HANROT. Doctorants: Alain PLAGNE. {\em Th\`emes:} Generation pseudo-aleatoire (liens avec les fonctions a sens uniques, tests statistiques sur les generateurs); Utilisation de methodes arithmetiques; Modelisation probabiliste en theorie des nombres; Valeurs extremes. {\em Publications:} J-M. DESHOUILLERS et G. HANROT, G\'en\'eration de nombres pseudo-al\'eatoires: recherche de nouveaux algorithmes, lien avec les fonctions \`a sens unique. Rapport DRET 93-1400/A000/DRET/DS/SR (1994). J-M. DESHOUILLERS , G.FREIMAN et W. MORAN, On sums of discrete random variables, 1 : real trinomial distributions with fixed probabilities, 16 p., Ast\'erisque (1998, \`a para{\^\i}tre). J-M. DESHOUILLERS , G. FREIMAN et A. YUDIN, On bounds for the concentration function, 2, 10 p., pr\'epublication de l'Unit\'e CNRS 9936. J-M. DESHOUILLERS , On some Connections between Probability and Number Theory, Contemp. Math. 210 (1998), 265-273. J-M. DESHOUILLERS , F. HENNECART et B. LANDREAU, Sums of powers: an arithmetic refinement to the probabilistic model of Erdos and R\'enyi , Acta Arithmetica (\`a para{\^\i}tre). J. ANTOCH, J-M. DESHOUILLERS et P. PURNABA, Pseudorandom number generator ran1 of the Numerical Recipes revisited, soumis \`a Computational Statistics and Data Analysis. \item {\bf Groupe de Physique Statistique des Systemes Desordonnes.} \\ Remi Monasson, Laboratoire de Physique Theorique de l'Ecole Normale Superieure 24 rue Lhomond 75231 Paris Cedex 05 tel: 01-44-32-38-48 fax: 01-43-36-76-66\\ email: monasson@physique.ens.fr {\em Membres:} Remi Monasson. Doctorants: Giulio Biroli {\em Th\`emes:} Utilisation des techniques et concepts de la physique statistique des systemes desordonnes au problemes d'informatique theorique et de combinatoire aleatoire. Probleme K-SAT aleatoire, transition de phase, fonctions de seuil, notion de complexite typique. {\em Publications:} [1] R. Monasson, R. Zecchina, Entropy of the K-satisfiability problem Phys. Rev. lett. 76, 3881 (1996). [2] R. Monasson, R. Zecchina, Statistical mechanics of the random K-SAT model Phys. Rev. E 56, 1357 (1997). [3] R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, L. Troyansky, Phase transition and search cost in the 2+p-sat problem Proceedings of PhysComp 96, T. Toffoli, M. Biafore, J. Leao eds., Boston (1996) \item {\bf Informatique Mathematique.}\\ Guy Louchard, ULB,CP212,Bvd du Triomphe,B 1050 Bruxelles. louchard@ulb.ac.be {\em Research activities:} during the last decade, we have used probabilistic techniques such as Brownian motion, random walks, diffusion processes in the analysis of algorithms. We have investigated distribution of costs which constitute an improvement over the classical average case or worst case analysis. Many applications have already been covered. Our next research concerns compression algorithms, convex polyominoes and other computer science random structures. {\em Publications:} [1] A probabilistic analysis of a string edit problem, with W. Szpankowski, Proc. 4th Int. Symp. Combin. Patt. Match '93, Padova, LNCS 684, 152-163; Full version: Comb. Prob. Comp. 4, 143-166, 1995. [2] Large finite population queueing systems: the finite server model. Stoch. Proc. Appl. 55, 117-145, 1994. [3] Probabilistic analysis of some (un)directed animals. Proceedings Gascom'94; Full version: T.C.S. 159, 1, 65-79, 1996. [4] Generalized Lempel-Ziv parsing scheme and its preliminary analysis of the average profile, with W. Szpankowski; Proc. DCC'95, 262-271, 1995. [5] Average profile and limiting distribution of a phrase size in the Lempel-Ziv parsing algorithm, with W. Szpankowski, IEEE Trans. Inf. Theor. 41, 478-488, 1995. \item {\bf Optimisation Combinatoire et Structures Al\'eatoires.} Bruce Reed (CR CNRS) Equipe Combinatoire, Case 189, Universit\'e Paris 6, 4 Place Iussien 75252 Paris Cedex 05 France.\\ reed@ecp6.jussieu.fr {\em Th\`emes:} Algorithmes Probabilistes, Methode Probabiliste, Graphes Aleatoires. {\em Publications:} [1] Molloy M. and Reed B., Further algorithmic aspects of the Local Lemma, To appear in the proceedings of STOC 1998. [2] Molloy M., and Reed B.: A bound on the strong chromatic index of a graph; {\em Journal of Combinatorial Theory(B), Vol. 69, 1997,103-109}. [3] Perkovic L., and Reed B.: Edge colouring regular graphs of high degree; {\em Discrete Mathematics Vol. 165/166, 1997, 567-578}. [4] Devroye L. and Reed B.: On the expected height of random binary search trees; {\em SIAM Journal of Computing Vol. 24, 1995, 1157-1163}. [5] Frieze A., Karp R., and Reed B.: When is the assignment bound tight for the asymetric TSP?, {\em SIAM Journal of Computing Vol. 24, 1995, 484-494}. [6] Frieze A., Reed B.,: Covering the edges of a random graph by cliques; {\em Combinatorica Vol. 15, 1995, 489-499}. \item {\bf Analyse probabiliste des algorithmes.} \\ Philippe Chassaing (MdC), Institut Elie Cartan, Laboratoire de mathematiques B.P. 239 54506 Vandoeuvre les Nancy Cedex chassain@iecn.u-nancy.fr {\em Membres:} Philippe Chassaing. Doctorants: Jean Francois Marckert {\em Th\`emes:} Analyse probabiliste des algorithmes Probabilit\'es. {\em Publications significatives:} Optimality of move-to-front for self-organizing data structures with locality of references. Annals of Applied Probability Vol. 3, No. 4, 1993, 1219-1240. Determining the majority: the biased case, Annals of Applied Probability Vol. 7, No. 2, 1997, 523-544. The average complexity of a coin-weighing problem (avec Alonso, L., \& Schott, R.), Random Structures Algorithmes 9 (1\&2), 1996, 1-14. How many probes are needed to compute the maximum of a random walk ? (accept\'e \`a Stochastic Process. Appl.). Slow diffusion for a Brownian motion with random reflecting barriers. Stochastic Process. Appl. 61 (1996), no. 1, 71-83. Processus associ\'es \`a l'\'equation des milieux poreux (avec S. Benachour, B. Roynette \& P. Vallois). Ann. Scuola Norm. Sup. Pisa Cl. Sci. 23 (4), 1997, 793-832. \end{enumerate} \section{Commentaire final} Il existe en France des \'ecoles de tres grande qualit\'e et visibilit\'e internationales en probabilit\'es, combinatoire \'enumerative, et analyse d'algorithmes. Par ailleurs, la s\'eparation entre recherche math\'ematique et informatique tend \`a \^etre bien moins accentu\'ee que dans les pays anglo-saxons. Il y a ainsi sur les th\`emes d'Al\'ea une situation favorable que les PRC-GDR MathInfo puis AMI ont su encourager. Il nous semble qu'il y a dans la poursuite de ces actions communes, \`a la fronti\`ere de plusieurs disciplines, une opportunit\'e scientifique v\'eritable. Au cours de la premi\`ere phase d'Al\'ea (1996--1998), on a assist\'e au d\'eveloppement d'une synergie tr\`es int\'eressante. Celle-ci s'est concr\'etis\'ee par l'organisation des trois rencontres de 1996, 1997, et 1998, donnant lieu, dans le cas des journ\'ees Gascom, \`a un num\'ero sp\'ecial de revue internationale ``primaire'' ({\em Theoretical Computer Science}, Elsevier). On notera que ce programme Al\'ea rassemble des \'equipes d'horizons tr\`es diverss, mais ayant r\'eussi \`a d\'evelopper un langage commun. Au plan m\'ethodologique, les convergences sont d\'esormais nombreuses entre m\'ethodes issues de la th\'eorie analytique des nombres, de l'analyse combinatoire, ou encore des processus stochastiques. De nouvelles directions li\'ees \`a l'analyse fonctionnelle, \`a la physique statistique, ou au calcul formel sont en cours d'exploration et sont extr\^emement prometteuses. Enfin, on observera dans la liste tr\`es partielle des publications des \'equipes une proportion sensible de travaux transverses aux fronti\`eres des d\'epartements et des organismes qui attestent de la vitalit\'e des \'echanges entre les \'equipes Al\'ea. Nous esp\'erons disposer d'un cadre et d'un soutien pour pouvoir poursuivre l'aventure! \begin{flushright} {\sc Philippe Flajolet} \\ INRIA-Rocquencourt \\ F-78153 Le Chesnay Cedex \\ Fax: 01.39.63.55.96\\ Tel: 01.39.63.56.26 ou 54.43 (secr.) \end{flushright} \clearpage \section*{Annexe 1: Programme des Journ\'ees AL\'EA, Asnelles 1998} Deuxiemes Journees ALEA Asnelles sur Mer Du mercredi midi 4 fevrier au vendredi 6 fevrier Organisateurs : Brigitte Vallee (GREYC, Caen), Bernard Ycart (IMAG, Grenoble) Programme Scientifique {\sc Mercredi 4 f\'evrier} 15h30-16h30: Philippe Robert Convergence a` l'e'quilibre de certaines chaines de Markov finies. 16H30-17h : Stephane Boucheron (LRI Orsay) Une approximation pour diffusion pour les allocations aleatoires 17h-17h30: Pause Cafe 17h30-18h: Bernard.Ycart Tests d'arret pour les methodes MCMC 18h-18h30 Marie Christine Rousset (en collaboration avec Bernard Ycart) Generation de benchmarks aleatoires pour les logiques de description {\sc Jeudi 5 f\'evrier} 9h15-10h15: Remi Monasson Expose de synthese sur les repliques 10h15-10h45: Pause Cafe 10h45-11h15: Guy Louchard "Analyse probabiliste d'animaux colonne-convexes et diriges diagonalement convexes.Trajectoires et formes" 11h15-11h45 : Philippe Chassaing (en collaboration avec Jean-Francois Marckert et Marc Yor) "Recherche des zeros d une fonction et arbres binaires" 11h45-12h15: Jean Francois Marckert (en collaboration Philippe Chassaing et Marc Yor) "Sur un algorithme de recherche du maximum optimal pour l'ordre stochastique" 15h30-16h30: Philippe Flajolet "Analyse du hachage avec essais lineaires" 16h30-17h: Michele Soria "Expression des coefficients de series algebriques sous forme de somme finie de multinomiaux" 17h-17h30: Pause Cafe 17h30-18h: Isabelle Dutour (en collaboration avec Paul.Zimmermann) "CS : ge'ne'ration ale'atoire en temps quasi-line'aire de structures combinatoires de'composables" 18h- 18h30: Julien Clement (en collaboration avec Philippe Flajolet et Brigitte Vallee) Etude des tries hybrides. {\sc Vendredi 6 fevrier} 9h15-10h15: Herve Daude "Des graphes aleatoires au probleme SAT." 10h15-10h45: Pause Cafe 10h45-11h45: Brigitte Vallee "Analyse en moyenne du pgcd binaire" 14h30-15h: Ali Akhavi "Comportement des algorithmes de reduction sur des reseaux euclidiens aleatoires" 15h-15h30: Jean-Marie Le Bars "Graphes aleatoires, logique et lois 0-1" 15h30-16h : Gilles Schaeffer "Une methode bijective simple et directe pour la generation aleatoire lineaire de cartes planaires" \clearpage \section*{Annexe 2: Liste de diffusion.} \begin{verbatim} alias gdt-alea \ Philippe.Flajolet@inria.fr soria@litp.ibp.fr \ Philippe.Robert@inria.fr Mireille.Regnier@inria.fr \ steyaert@lix.polytechnique.fr \ Dominique.Gouyou-Beauchamps@lri.fr \ Miklos.Santha@ens.fr bouchero@lri.fr \ lalo@lri.fr cori@labri.u-bordeaux.fr Daniele.Gardy@prism.uvsq.fr \ Yannis.Manoussakis@lri.fr morain@lix.polytechnique.fr \ penaud@labri.u-bordeaux.fr Serge.Dulucq@labri.u-bordeaux.fr \ Jean-Daniel.Boissonnat@sophia.inria.fr \ Francois.Baccelli@inria.fr nain@sophia.inria.fr \ ajm@sophia.inria.fr gaujal@sophia.inria.fr \ francois.baccelli@inria.fr \ philippe.mussi@inria.fr \ Brigitte.Vallee@info.unicaen.fr Ali.Akhavi@info.unicaen.fr \ dubois@laforia.ibp.fr \ Bernard.Ycart@imag.fr Bernard.Van-Cutsem@imag.fr \ Jean-Louis.Soler@imag.fr Jean-Marc.Vincent@imag.fr \ Olivier.Francois@imag.fr Olivier.Gaudoin@imag.fr \ Brigitte.Chauvin@prism.uvsq.fr Alain.Rouault@prism.uvsq.fr \ Gregory.Kucherov@loria.fr Paul.Zimmermann@loria.fr \ Christian.Lavault@ura1507.univ-paris13.fr \ myoupo@elc3.crihan.fr villain@elc3.crihan.fr \ Claude.Puech@imag.fr \ lacoste@gyptis.univ-mrs.fr \ cassaign@clipper.ens.fr berstel@dmi.ens.fr \ dezou@u-bordeaux2.fr \ Philippe.Chassaing@antares.iecn.u-nancy.fr \ MARCKERT@iecn.u-nancy.fr \ mosbah@labri.u-bordeaux.fr Nasser.Saheb@labri.u-bordeaux.fr \ denise@lri.fr daude@gyptis.univ-mrs.fr \ durr@lri.fr huong@lri.fr \ olivier.goldschmidt@imag.fr Paulo.Fernandes@imag.fr \ Remi.Monasson@lpt.ens.fr \ huillet@limhp.univ-paris13.fr \ nemir@prism.uvsq.fr Julien.Clement@info.unicaen.fr \ Claire.Kenyon@lri.fr \ Frederic.Cazals@inria.fr \end{verbatim} \end{document}