Résumé.
L'objectif de ce groupe de travail est un brassage d'approches scientifiques
et méthodologiques variées telles
combinatoire énumérative, combinatoire analytique,
méthodes probabilistes, modèles stochastiques
continus, méthodes issues de la physique statistique,
appliquées aux structures discrètes fondamentales
de l'informatique, notamment,
mots, arbres, permutations, graphes, configurations
géométriques, formules booléennes.
Ces objets sont
présents dans de nombreux domaines de l'informatique fondamentale,
tels,
structures de données pour la recherche rapide de l'information,
recherche de motifs (``pattern matching''), optimisation combinatoire
et algorithmes d'approximation probabilistes, algorithmique
géométrique et aléatoirisation,
algorithmique répartie et protocoles, etc.
Les principales orientations méthodologiques du GDT, en accord avec le résumé, sont
Le but commun des équipes participantes est donc l'analyse fine des propriétés des structures discrètes de l'informatique (envisagées sous l'aspect aléatoire) et l'exploitation de leur propriétés (énumératives ou probabilistes) à fin d'évaluation et d'optimisation des algorithmes de base dans des domaines divers de l'informatique.
Quelques exemples plus précis de domaines auxquels le groupe de travail s'attachera:
Il s'agit de fédérer les équipes et individus travaillant en France sur ces thèmes. Ceux-ci sont principalement (mais non exclusivement) membres de l'ex-GDR/PRC AMI. Le projet a vocation de regrouper des composantes représentant un éventail à la fois large par ses approches méthodologiques, mais ciblé par son objet.
Au cours de la periode ecoulée, 1995-1998, le Groupe ALEA a soutenu un certain nombre de manifestations:
1. Le groupement qui est proposée est une structure transversale légère dédié en priorité à l'organisation d'une rencontre annuelle (environ 50 personnes, 5 jours) sur les thèmes décrits ci-dessus. Il est demandé au GDR ALP de soutenir prioritairement cette réunion généraliste, soit
Journées ALEA. 40 missions/invitations 2000F = 80kF.La réunion est prévue en région bordelaise pour une durée de 5 jours en mars-avril 1999 (organisation Labri, responsable J.-G. Penaud) où seront jumelées à part égales les rencontres Aléa et les rencontres Gascom dédiées plus spécialement à la génération aléatoire.
2. Bourses déchanges de doctorants. Il s'agit de bourses destinées exclusivement à financer l'échange de doctorants ou de chercheurs postdoctoraux (thèse+2) entre deux laboratoires géographiquement distants. Le dossier est directement monté par les deux jeunes chercheurs concerné qui détaillent en deux pages maximum leur programme de travail (exploration d'une question, publication commune, etc). Il s'agit, après approbation du comité Aéa de soutenir deux séjours croisés d'environ 10 jours chacun, étalés sur une période maximale de 3 mois.
5 bourses d'échanges 6kF = 30 kF.
Contribution totale demandée: 80+30 = 110 kF.
Le GDT Aléa regroupe environ 115 membres (dont un peu plus de la moitié sont des ``permanents''), issus d'une dizaine d'équipes fortement structurées, ainsi que des membres associés.
Thèmes: Structures de données et analyse en moyenne: combinatoire analytique, méthodes asymptotiques, calcul formel. Méthodes symboliques pour les dénombrements combinatoires, liens avec le calcul formel et l'analyse automatique de structures de données et d'algorithmes combinatoires. Méthodes asymptotiques fondées sur l'analyse complexe et lois limites en algorithmique et structures discrètes. Applications aux arbres de termes en calcul symbolique, aux arbres de recherche (par exemple multidimensionnels), aux mots aléatoires, à l'algorithmique distribuée (protocoles) et probabiliste. Génération aléatoire.
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égnier (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.)
Membres: Robert Cori, professeur a` l'X, Jean-Marc Steyaert, maître de confe'rences a` l'X, Doctorants: Michel Nguyen The', Dominique Rossin, Fabrice Torossian.
Thèmes. 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.
Membres: M. Bousquet-Mélou R. Cori M. Delest S. Dulucq M. Mosbah M. Robson N. Saheb X. Viennot. Doctorants: G. Schaeffer J. P. Duchon
Thèmes: Génération aléatoire: utilisation des méthodes bijectives pour engendrer des classes spécifiques d'objets de façon performante et de méthodes récursives (les grammaires d'objets). Combinatoire: plus généralement l'approche bijective, prisée dans l'équipe Cori-Viennot, conduit à la connaissance de la structure profonde des objets manipulés, et débouche sur l'énumération et l'algoritmique (CALICO). Animaux dirigés et percolation. Etude approfondie de ces modèles issus de la physique Graphes et marches aléatoires: application des automates et des langages reconnaissables à l'étude des marches avec des probabilités non uniformes.
Publications: DULUCQ S. et GUIBERT O. Stack words, standard tableaux and Baxter permutations. Discrete Math., vol.157, 1996, pp. 91-106. BOUSQUET-MÉLOU M. Percolation models and animals. European J. Combin., vol. 17, 1996, pp. 343-369. BOUSQUET-MÉLOU M. New enumerative results on two-dimensional directed animals, DISCRETE MATH., à paraître. DEL LUNGO A., DEL RISTORO F. et PENAUD J.-G. Left ternary trees and non separable rooted planar maps. Theoret. Comput. Sci., à paraî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.
Commentaires: Il est clair que les thémes proposés par ALEA dépassent le seul projet GASCOM et intéressent l'ensemble de l'équipe de combinatoire énumérative du Labri, ainsi que des chercheurs d'autres équipes voisines du laboratoire comme R. Cori M. Robson et N. Saheb de l'équipe de combinatoire et algorithmique distribuée (eq. Cori), d'une part, et M. Mosbah de l'équipe de Lagages formels et Graphes (eq Courcelle). Il s'agit donc là d'une réponse conjointe de participants au groupe de travail GASCOM et au groupe de travail de combinatoire énumérative.
Membres': Jean-Paul Allouche (DR CNRS) Stéphane 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ébastien Dhuime David Gross Huong L. Thanh Frédéric Magniez Fabrice Noilhan Kave Salamatian Julien Stern Yann Verhoeven. Post-doctorants: Abdelkrim Amoura Sophie Laplante Bernd Loescher Abraham Sharell
Thèmes: Complexité probabiliste; graphes aléatoires, satisfaisabilité des formules booléennes aléatoires, algorithmes probabilistes et algorithmes d'approximation pour l'optimisation combinatoire, comptage approximatif randomisé. Génération aléatoire et combinatoire : dénombrement de structures combinatoires, conception et analyse d'algorithmes de génération uniforme, combinatoire des mots.
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, à paraî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, à paraître dans Journal of Algorithms. H. L. Thanh, C. Dürr 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.
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
Thèmes: 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.
Publications: Brigitte Vallée.Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes de Gauss et d'Euclide, Acta Arithmetica LXXXI.2 (1997), pp 101-144. Philippe Flajolet, Brigitte Vallée, 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ée, Dynamical systems and average-case analysis of general tries, présenté au Congrès RALCOM'97 (Randomized algorithms and Computing, Ile Santorin, octobre 97), [16 p]. Julien Clément, Philippe Flajolet, Brigitte Vallée, The analysis of hybrid trie structures, (en collaboration avec Julien Clément et Philippe Flajolet), présenté au congrès SODA'98 (Symposium on Discrete Algorithms) (San Francisco, janvier 98), Comptes-Rendus de SODA'98, pp 531-540 Brigitte Vallée, The complete analysis of the Binary Euclidean Algorithm, ANTS'98 (Algorithmic Number Theory Symposium, Portland, USA, Juin 98), à paraître dans les actes (LNCS) Jean-Marie Le Bars, A kernel property to characterize fragments for which the 0-1 law fails., LICS'98, (meilleur article étudiant)
Thème: 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.
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
Membres: E. CRETOIS Maître de conférences UMPF, O. FRANÇOIS Maître de conférences ENSIMAG, O. GAUDOIN Maître de conférences ENSIMAG, J.L. SOLER Professeur ENSIMAG, B. VAN CUTSEM Professeur émérite UJF, J.M. VINCENT Maître de conférences UJF, M. VIOT Chargé de recherches CNRS, B. YCART Professeur UJF. Doctorants: C. LABBE, L.M. OULD MOHAMED ABDALLAHI, C. ZAHALCA
Thèmes: Modèles 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énération aléatoire; Analyse probabiliste d'algorithmes; Fiabilite des logiciels.
Publications: Une présentation de MAI avec résumés des rapports en ligne et accès au texte intégral est disponible sur le réseau ( http://www-lmc.imag.fr/MAI).
[1] VAN CUTSEM, B., YCART, B. Indexed dendrograms on random dissimilarities. Rapport MAI 23 (mars 96). A paraître J. of Classification (1998). [2] FRANÇOIS, O., An evolutionnary strategy for global minimization and its Markov chain analysis. Rapport MAI 50 (décembre 97). [3] YCART, B. Cutoff for samples of Markov chains. Rapport MAI 51 (février 98). Soumis à ESAIM-PS. [4] LE BRETON, A., SOLER, J.L. On the failure rate of components subjected to a diffuse stress environment. Rapport MAI 52 (février 98). A paraître dans Mathematical Methods in Reliability, Birkhäuser (1998). [5] ELHAIK, Q., ROUSSET, M.C., YCART, B. Generating random benchmarks for description logics. Rapport MAI 54 (mars 98). Soumis à DL'98.
Membres: Guillaume Hanrot (CR INRIA au 1/6/98) Gregory Kucherov (CR INRIA) Fabrice Rouillier (CR INRIA) Alain Giorgetti (PrAg UHP) Jean-Luc Rémy (CR CNRS) Jocelyne Rouyer (MC UHP). Doctorants: Vladimir Grebinski (thésard INRIA)
Thèmes: Calcul numérique fiable Factorisation de polynomes Génération aléatoire Algorithmes combinatoires d'analyse de séquences Algorithmes de recherche combinatoire
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émy, 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ération de polyominos convexes dirigés, Discrete Math. 157, (1996), 79-90.
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).
Thèmes: De très nombreux algorithmes distribués utilisent les propriétés et structures combinatoires de type aléatoires (systèmes "anonymes", algorithmes distribués tolérants aux fautes transitoires: algorithmes "auto-stabilisants", etc.). Par ailleurs, l'analyse en moyenne de ces algorithmes et des structures de données distribuées fait évidemment 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)
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.
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é de Provence, Departement de Mathematiques, Laboratoire IML, Philippe Je'gou (MC), Universite de Provence, Departement d'informatique, LIM, Pierre Liardet (PR), Université 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)
Thèmes: 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 à 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 à 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éatoires, Nadia Creignou et Herve' Daude' [3] ont donné 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 étudie actuellement la repartition des graphes aleatoires dans ces classes.
Notre équipe propose ainsi d'aborder certains problemes algorithmiques à la fois par l'experimentation statistique et par l'analyse probabiliste.
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 à la revue Discrete Applied Math.
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
Thèmes: 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.
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.
Membres: Francois HENNECART, Bernard LANDREAU, Guillaume HANROT. Doctorants: Alain PLAGNE.
Thèmes: 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.
Publications: J-M. DESHOUILLERS et G. HANROT, Génération de nombres pseudo-aléatoires: recherche de nouveaux algorithmes, lien avec les fonctions à 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érisque (1998, à paraître). J-M. DESHOUILLERS , G. FREIMAN et A. YUDIN, On bounds for the concentration function, 2, 10 p., prépublication de l'Unité 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ényi , Acta Arithmetica (à paraître). J. ANTOCH, J-M. DESHOUILLERS et P. PURNABA, Pseudorandom number generator ran1 of the Numerical Recipes revisited, soumis à Computational Statistics and Data Analysis.
Membres: Remi Monasson. Doctorants: Giulio Biroli
Thèmes: 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.
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)
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.
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.
Thèmes: Algorithmes Probabilistes, Methode Probabiliste, Graphes Aleatoires.
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; Journal of Combinatorial Theory(B), Vol. 69, 1997,103-109. [3] Perkovic L., and Reed B.: Edge colouring regular graphs of high degree; Discrete Mathematics Vol. 165/166, 1997, 567-578. [4] Devroye L. and Reed B.: On the expected height of random binary search trees; 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?, SIAM Journal of Computing Vol. 24, 1995, 484-494. [6] Frieze A., Reed B.,: Covering the edges of a random graph by cliques; Combinatorica Vol. 15, 1995, 489-499.
Membres: Philippe Chassaing. Doctorants: Jean Francois Marckert
Thèmes: Analyse probabiliste des algorithmes Probabilités.
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é à Stochastic Process. Appl.). Slow diffusion for a Brownian motion with random reflecting barriers. Stochastic Process. Appl. 61 (1996), no. 1, 71-83. Processus associés à l'équation des milieux poreux (avec S. Benachour, B. Roynette & P. Vallois). Ann. Scuola Norm. Sup. Pisa Cl. Sci. 23 (4), 1997, 793-832.
Il existe en France des écoles de tres grande qualité et visibilité internationales en probabilités, combinatoire énumerative, et analyse d'algorithmes. Par ailleurs, la séparation entre recherche mathématique et informatique tend à être bien moins accentuée que dans les pays anglo-saxons. Il y a ainsi sur les thèmes d'Aléa 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, à la frontière de plusieurs disciplines, une opportunité scientifique véritable.
Au cours de la première phase d'Aléa (1996-1998), on a assisté au développement d'une synergie très intéressante. Celle-ci s'est concrétisée par l'organisation des trois rencontres de 1996, 1997, et 1998, donnant lieu, dans le cas des journées Gascom, à un numéro spécial de revue internationale ``primaire'' ( Theoretical Computer Science, Elsevier).
On notera que ce programme Aléa rassemble des équipes d'horizons très diverss, mais ayant réussi à développer un langage commun. Au plan méthodologique, les convergences sont désormais nombreuses entre méthodes issues de la théorie analytique des nombres, de l'analyse combinatoire, ou encore des processus stochastiques. De nouvelles directions liées à l'analyse fonctionnelle, à la physique statistique, ou au calcul formel sont en cours d'exploration et sont extrêmement prometteuses. Enfin, on observera dans la liste très partielle des publications des équipes une proportion sensible de travaux transverses aux frontières des départements et des organismes qui attestent de la vitalité des échanges entre les équipes Aléa. Nous espérons disposer d'un cadre et d'un soutien pour pouvoir poursuivre l'aventure!
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
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
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.
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"
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
This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 gdt2.
The translation was initiated by Philippe Flajolet on 3/20/1998