Analyse d'algorithmes de manipulation d'arbres et de fichiers

Philippe Flajolet

Cahiers du Bureau universitaire de recherche opérationnelle Série Recherche (1981)

  • Volume: 34-35, page 5-208
  • ISSN: 0078-950X

How to cite

top

Flajolet, Philippe. "Analyse d'algorithmes de manipulation d'arbres et de fichiers." Cahiers du Bureau universitaire de recherche opérationnelle Série Recherche 34-35 (1981): 5-208. <http://eudml.org/doc/272546>.

@article{Flajolet1981,
author = {Flajolet, Philippe},
journal = {Cahiers du Bureau universitaire de recherche opérationnelle Série Recherche},
language = {fre},
pages = {5-208},
publisher = {Institut Henri Poincaré - Institut de Statistique de l'Université de Paris},
title = {Analyse d'algorithmes de manipulation d'arbres et de fichiers},
url = {http://eudml.org/doc/272546},
volume = {34-35},
year = {1981},
}

TY - JOUR
AU - Flajolet, Philippe
TI - Analyse d'algorithmes de manipulation d'arbres et de fichiers
JO - Cahiers du Bureau universitaire de recherche opérationnelle Série Recherche
PY - 1981
PB - Institut Henri Poincaré - Institut de Statistique de l'Université de Paris
VL - 34-35
SP - 5
EP - 208
LA - fre
UR - http://eudml.org/doc/272546
ER -

References

top
  1. [ Batcher ; 1968] : "Sorting networks and their applications" ; in Proceedings AFIPS Spring Joint Comp. Conf., Montvale (1968), pp. 307-314. 
  2. [ Bentley ; 1978] : "Decomposable Searching Problems" ; Carnegie-Mellon University Report Nu CMU-CS-78-145 (1978). Zbl0404.68067MR691496
  3. [ Berstel ; 1978] : "Séries formelles en variables non-commutatives et applications" ; J. Berstel Editeur, LITP et ENSTA, Paris (1978). Zbl0401.16001MR522632
  4. [ de Bruijn ; 1975] Communication personnelle à J. Vuillemin. 
  5. [ de Bruijn, Knuth, Rice ; 1972] : "The average height of planted plane trees" ; in "Graph Theory and Computing" ; R.C. Read Editor, Academic Press, New-York (1972), pp. 15-22. Zbl0247.05106MR505710
  6. [ Camion, Flajolet, Monier ; 1979] : "On Pollard's factorization algorithm", en préparation. 
  7. [ Carlitz ; 1964] : "A binomial identity arising from a sorting problem" ; in SIAM Rev.6 (1964), pp. 20-30. Zbl0128.01601MR167435
  8. [ Carlitz ; 1974] : "q-analog of the Lagrange expansion" ; in Eulerian Series and Applications, Pennsylvania State Univ. (1974). 
  9. [ Chihara ; 1978] : "An Introduction to Orthogonal Polynomials", Gordon and Breach, New-York (1978). Zbl0389.33008MR481884
  10. [ Chomsky, Schützenberger ; 1963] : "The algebraic theory of context-free languages" in "Computer Programming and Formal Systems" ; North Holland P.C. (1963). Zbl0148.00804MR152391
  11. [ Chung, Luccio, Wong ; 1979] : "On the complexity of sorting in magnetic bubble memory systems", manuscript. Zbl0436.68041
  12. [ Comtet ; 1970] : "Analyse Combinatoire" ; 2 vol. P.U.F., Paris (1970). 
  13. [ Delange ; 1975] : "Sur la fonction sommatoire de la fonction somme des chiffres" ; in Enseignement Math.21 (1975), pp. 31-47. Zbl0306.10005MR379414
  14. [ Edwards ; 1974] : "Riemann's Zeta Functions" ; Academic Press, New-York (1974). Zbl0315.10035
  15. [ Eilenberg ; 1974] : "Automata, Languages and Machines" ; Vol A ; Academic Press, New-York (1974). Zbl0317.94045MR530382
  16. [ Ershov ; 1958] : "On programming of arithmetic operations", CACM1 (1958), 8 pp. 3-6. Zbl0086.33203
  17. [ Flajolet ; 1978] : "Analyse d'Algorithmes de manipulation de fichiers" ; Rapport IRIA, Rocquencourt (1978). 
  18. [ Flajolet ; 1978] : "Analyse de la détection d'arbres" in "3ème Colloque de Lille sur les Arbres en Algèbres et en Programmation" ; Lille (1979). Zbl0399.05024
  19. [ Flajolet ; 1979] : "Combinatorial Aspects of Continued Fractions", soumis à Discrete Math. Zbl0445.05014
  20. [ Flajolet, Françon, Vuillemin ; 1979a] : "Computing Integrated costs of sequences of operations with application to dictionaries" ; in 11th ACM-SIGACT Conf., Atlanta (1979). MR564619
  21. [ Flajolet, Françon, Vuillemin ; 1979b] : "Towards analyzing sequences of operations for dynamic data structures" ; in 20th IEEE-FOCS Conf., Porto-Rico (1979). 
  22. [ Flajolet, Ramshaw ; 1979] : "A note on Gray-Code and Odd-Even Merge" ; SIAM Journal on Comp. (à paraître). Zbl0447.68083
  23. [ Flajolet, Raoult, Vuillemin ; 1977] : "The number of registers required for evaluating arithmetic expressions" ; version préliminaire dans "18th IEEE Symp. FOCS" (1977) Zbl0407.68057
  24. [ Flajolet, Raoult, Vuillemin ; 1979] : "The number of registers required for evaluating arithmetic expressions" ; version préliminaire dans Theoret. Comp. Sc.9 (1979), pp. 99-125. Zbl0407.68057MR535127
  25. [ Flajolet, Steyaert ; 1979] : "On the analysis of tree matching algorithms", en préparation. Zbl0434.68046
  26. [ Foata ; 1971] : "La série génératrice exponentielle dans les problèmes d'énumération" ; Presses de l'Université de Montréal (1971). Zbl0325.05007
  27. [ Foata, Schützenberger ; 1970] : "Théorie géométrique des polynômes Eulériens" ; Lecture Notes in Mathematics, N° 138, Springer Verlag, Berlin (1970). Zbl0214.26202
  28. [ Françon ; 1977] : "Sur la fonction nombre de registres", manuscript. 
  29. [ Françon ; 1978] : "Histoires de Fichiers" ; in RAIRO Inf. Th., vol. 12 (1978), pp. 49-67. Zbl0377.68034MR483819
  30. [ Françon ; 1979] : "Combinatoire des Structures de données" ; Thèse, Faculté des Sciences de Strasbourg (1979). 
  31. [ Françon, Viennot ; 1979] : "Permutations selon leurs pics, creux, doubles montées et doubles descentes ; nombres d'Euler et de Genocchi" ; in Discrete Math. (1979), à paraître. Zbl0409.05003
  32. [ Françon, Viennot, Vuillemin ; 1978] : "Description and analysis of an efficient priority queue representation" ; in "19th I.E.E.E.F.O.C.S.", Ann Harbor (1978). 
  33. [ Françon, Viennot, Vuillemin ; 1978] : "Description et analyse d'une représentation performante des files de priorité" ; Rapport Informatique Université Paris-Sud (1978). 
  34. [ Henrici ; 1978] : "Applied and Computation Complex Analysis", vol.2 ; J. Wiley, New-York (1978). 
  35. [ Jackson ; 1978] : "Some results on product-weighted lead-codes" ; in J. Comb. Th., ser. A, 25 (1978), pp. 181-187. Zbl0425.05007MR509443
  36. [ Kemp ; 1977] : "The average number of registers to evaluate a binary tree optimally", Saarbrücken University Report (1977). 
  37. [ Kemp : "The average number of registers to evaluate a binary tree optimally", Acta Informatica (1979). Zbl0395.68059
  38. [ Knuth ; 1968] : "The Art of Computer Programming : Fundamental Algorithms" ; Addison Wesley, Reading (1968). Zbl0895.68055
  39. [ Knuth ; 1969] : "The Art of Computer Programming : Semi numerical Algorithms" ; Addison-Wesley, Reading (1969). Zbl0191.18001
  40. [ Knuth ; 1973] : "The Art of Computer Programming : Sorting and Searching" ; Addison-Wesley, Reading (1973). Zbl0895.68054
  41. [ Knuth, Schönhage ; 1978] : "The expected linearity of a simple equivalence algorithm" ; in Stanford Univ. Report CS-77-599 (1977). Zbl0377.68024
  42. [ Kreweras ; 1970] : "Sur les éventails de segments" ; Cahiers du B.U.R.O., n° 15 (1970), pp. 1-41. 
  43. [ Lucas ; 1891] : "Théorie des Nombres" ; Gauthier-Villard, Paris (1891). 
  44. [ Mac Ilroy ; 1974] : "The number of ones in binary integers : bounds and extremal properties" ; in SIAM J. on Comp.3, n°4 (1974), pp. 255-261. Zbl0292.68021MR436687
  45. [ Mc Mahon ; 1975] : "The mechanical desing of trees" ; in Scient. Am.233 (1975), 1 pp. 92-102. 
  46. [ Meixner ; 1934] : "Orthogonale Polynomsystème mit einem besonderen Gestalt der erzeugenden funktion" ; J. Lond. Math. Soc.9 (1934), pp. 6-13. Zbl0008.16205
  47. [ Odlyzko ; 1979] : "Periodic oscillations of coefficients of power series that satisfy functional equations" ; Bell Lab., Murray Hill (1979). Zbl0484.30002
  48. [ Perron ; 1954] : "Die Lehre von den Kettenbrüchen", 2 vol. Teubner, Stuttgart (1954). JFM43.0283.04
  49. [ Pollard ; 1975] : "A Monte-Carlo method for factorization" ; in BIT. 15 (1975), pp. 331-334. Zbl0312.10006MR392798
  50. [ Raney ; 1960] : "Functional composition patterns and power series reversion" ; Trans. A.M.S.94 (1960), pp. 441-451. Zbl0131.01402MR114765
  51. [ Read ; 1979] : "The chord intersection problem" ; in Annals of N.Y. Ac. of Sc., 319 (1979), pp. 444-454. Zbl0479.05005MR556055
  52. [ Riordan ; 1968] : "Combinatorial Identities", John-Wiley and Sons, New-York (1968), Zbl0194.00502MR231725
  53. [ Rogers ; 1907] : "On the representation of certain asymptotic series as continued fractions" ; Proc. Lond. Math. Soc, 2 (1907), pp. 72-89. MR1576106JFM37.0255.02
  54. [ Rota ; 1975] : "Finite Operator Calculus" ; Academic Press, New-York (1975). MR379213
  55. [ Salomaa, Soittola ; 1978] : "Automata-theoretic Aspects of Formal Power Series" ; Springer Verlag, New-York (1978). Zbl0377.68039MR483721
  56. [ Sedgwick ; 1978] : "Data Movement in Odd-Even Merge ; SlAM Journal on Comp.7 (1978), pp. 239-272. Zbl0379.68024MR483680
  57. [ Sethi, Ullman ; 1970] : "The generation of optimal code for arithmetic expressions" ; in JACM17 (1970), 4 pp. 715-728, Zbl0212.18802MR275722
  58. [ Shreve ; 1966] : "Statistical law of stream numbers" ; in Geology, 74 (1966), pp. 17-37. 
  59. [ Stieltjes ; 1889] : "Sur la réduction en fraction continue d'une série procédant suivant les puissances descendantes d'une variable" ; Ann. Fac. Sc. Toulouse, 3 (1889), pp. 1-17. JFM21.0187.01
  60. [ Szegö ; 1939] : "Orthogonal Polynomials" ; A.M.S.Colloq. Pub., Providence (1939). 
  61. [ Touchard ; 1952] : "Sur un problème de configurations et sur les fractions continues" ; Can. J. of Math.4 (1952), pp. 2-25. Zbl0047.01801MR46325
  62. [ Viennot ; 1978] : "Une interprétation combinatoire des développements en série entière des fonctions elliptiques de Jacobi" ; soumis à Discrete Math. (1979). Zbl0444.33002
  63. [ Vuillemin ; 1978] : "A Data Structure for Manipulating Priority Queues" ; in CACM, 21 (1978), pp. 309-315. Zbl0371.68011MR478740
  64. [ Wall ; 1967] : "Analytic Theory of Continued Fractions" ; Chelsea Pub. Co., New-York (1967) rééd. Zbl0035.03601
  65. [ Whittaker, Watson ; 1902] : "A Course on Modern Analysis" ; Cambridge Univ. Press (1902) Zbl45.0433.02JFM45.0433.02
  66. [ Widder ; 1971] : "An Introduction to Transform Theory" ; Academic Press, New-York (1971). Zbl0219.44001

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.