Bibliographie
497
46. J. Clément, P. Flajolet, B. Vallée. Dynamical sources in information theory: a general analysis
of trie structures. Algorithmica 29(1), 307–369 (2001)
47. J. Clément, T. Nguyen Thi, B. Vallée. A general framework for the realistic analysis of
sorting and searching algorithms. Application to some popular algorithms, in STACS (2013),
pp. 598–609
48. J. Clément, T.H.N. Thi, B. Vallée. Towards a realistic analysis of some popular sorting
algorithms. Comb. Probab. Comput. 24(1), 104–144 (2015). Special issue dedicated to
the memory of Philippe Flajolet
49. D. Comer, The ubiquitous B-tree. ACM Comput. Surv. 11(2), 121–137 (1979)
50. T. Cormen, C. Leiserson, R. Rivest, Introduction à l’algorithmique (Dunod, Paris, 2002)
51. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction à l’algorithmique (Dunod, Paris,
2010)
52. M. Crochemore, C. Hancart, T. Lecroq, Algorithms on Strings (Cambridge University
Press, New York, 2007). Téléchargeable en Français, http://www-igm.univ-mlv.fr/~mac/
CHL/CHL-2011.pdf
53. R. De La Briandais, File searching using variable length keys. Papers presented at
the Western Joint Computer Conference, IRE-AIEE-ACM ‘59 (Western), 3–5 March 1959
(ACM, New York, 1959), pp. 295–298
54. A. Dembo, O. Zeitouni, Large Deviations Techniques and Applications, 2nd edn. (Springer,
Berlin, 1998)
55. L. Devroye, A probabilistic analysis of the height of tries and of the complexity of triesort.
Acta Inform. 21, 229–237 (1984)
56. L. Devroye, Branching processes in the analysis of the height of trees. Acta Inform. 24,
277–298 (1987)
57. L. Devroye, Applications of the theory of records in the study of random trees. Acta Inform.
26, 123–130 (1988)
58. L. Devroye, A study of trie-like structures under the density model. Ann. Appl. Probab. 2(2),
402–434 (1992)
59. L. Devroye, Branching processes and their applications in the analysis of tree structures and
tree algorithms, in Probabilistic Methods for Algorithmic Discrete Mathematics, ed. by M.
Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed (Springer, Berlin, 1998)
60. L. Devroye, An analysis of random LC tries. Random Struct. Algoritm. 15, 359–375 (2001)
61. L. Devroye, L. Laforest, An analysis of random d-dimensional quadtrees. SIAM J. Comput.
19(5), 821–832 (1990)
62. L. Devroye, B. Reed, On the variance of the height of random binary search trees. SIAM J.
Comput. 24, 1157–1162 (1995)
63. E. Doberkat, Some observations on the average behavior of heapsort (preliminary report), in
Int. Conf. on the Foundations of Computer Science (FOCS) (1980), pp. 229–237
64. E. Doberkat, Deleting the root of a heap. Acta Inform. 17, 245–265 (1982)
65. E. Doberkat, An average case analysis of Floyd’s algorithm to construct heaps. Inf. Control
61(2), 114–131 (1984)
66. J. Doyle, R. Rivest, Linear expected time of a simple union-find algorithm. Inf. Process. Lett.
5, 146–148 (1976)
67. M. Drmota, The variance of the height of binary search trees. Theor. Comput. Sci. 270,
913–919 (2002)
68. M. Drmota, Random Trees. An Interplay between Combinatorics and Probabilities (Springer,
Berlin, 2008)
69. M. Drmota, B. Gittenberger, On the profile of random trees. Random Struct. Algoritm. 10:4,
421–451 (1997)
70. M. Drmota, B. Gittenberger, The width of Galton-Watson trees conditioned by the size.
Discret. Math. Theor. Comput. Sci. 6:2, 387–400 (2004)
71. R. Dudley, Real Analysis and Probability (Cambridge University Press, Cambridge, 2002)
72. T. Duquesne, J.-F. Le Gall, Random trees, Levy processes and spatial branching processes.
Asterisque, 281 (2002). https://www.math.u-psud.fr/~jflegall/Mono-revised.pdf
497
46. J. Clément, P. Flajolet, B. Vallée. Dynamical sources in information theory: a general analysis
of trie structures. Algorithmica 29(1), 307–369 (2001)
47. J. Clément, T. Nguyen Thi, B. Vallée. A general framework for the realistic analysis of
sorting and searching algorithms. Application to some popular algorithms, in STACS (2013),
pp. 598–609
48. J. Clément, T.H.N. Thi, B. Vallée. Towards a realistic analysis of some popular sorting
algorithms. Comb. Probab. Comput. 24(1), 104–144 (2015). Special issue dedicated to
the memory of Philippe Flajolet
49. D. Comer, The ubiquitous B-tree. ACM Comput. Surv. 11(2), 121–137 (1979)
50. T. Cormen, C. Leiserson, R. Rivest, Introduction à l’algorithmique (Dunod, Paris, 2002)
51. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction à l’algorithmique (Dunod, Paris,
2010)
52. M. Crochemore, C. Hancart, T. Lecroq, Algorithms on Strings (Cambridge University
Press, New York, 2007). Téléchargeable en Français, http://www-igm.univ-mlv.fr/~mac/
CHL/CHL-2011.pdf
53. R. De La Briandais, File searching using variable length keys. Papers presented at
the Western Joint Computer Conference, IRE-AIEE-ACM ‘59 (Western), 3–5 March 1959
(ACM, New York, 1959), pp. 295–298
54. A. Dembo, O. Zeitouni, Large Deviations Techniques and Applications, 2nd edn. (Springer,
Berlin, 1998)
55. L. Devroye, A probabilistic analysis of the height of tries and of the complexity of triesort.
Acta Inform. 21, 229–237 (1984)
56. L. Devroye, Branching processes in the analysis of the height of trees. Acta Inform. 24,
277–298 (1987)
57. L. Devroye, Applications of the theory of records in the study of random trees. Acta Inform.
26, 123–130 (1988)
58. L. Devroye, A study of trie-like structures under the density model. Ann. Appl. Probab. 2(2),
402–434 (1992)
59. L. Devroye, Branching processes and their applications in the analysis of tree structures and
tree algorithms, in Probabilistic Methods for Algorithmic Discrete Mathematics, ed. by M.
Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed (Springer, Berlin, 1998)
60. L. Devroye, An analysis of random LC tries. Random Struct. Algoritm. 15, 359–375 (2001)
61. L. Devroye, L. Laforest, An analysis of random d-dimensional quadtrees. SIAM J. Comput.
19(5), 821–832 (1990)
62. L. Devroye, B. Reed, On the variance of the height of random binary search trees. SIAM J.
Comput. 24, 1157–1162 (1995)
63. E. Doberkat, Some observations on the average behavior of heapsort (preliminary report), in
Int. Conf. on the Foundations of Computer Science (FOCS) (1980), pp. 229–237
64. E. Doberkat, Deleting the root of a heap. Acta Inform. 17, 245–265 (1982)
65. E. Doberkat, An average case analysis of Floyd’s algorithm to construct heaps. Inf. Control
61(2), 114–131 (1984)
66. J. Doyle, R. Rivest, Linear expected time of a simple union-find algorithm. Inf. Process. Lett.
5, 146–148 (1976)
67. M. Drmota, The variance of the height of binary search trees. Theor. Comput. Sci. 270,
913–919 (2002)
68. M. Drmota, Random Trees. An Interplay between Combinatorics and Probabilities (Springer,
Berlin, 2008)
69. M. Drmota, B. Gittenberger, On the profile of random trees. Random Struct. Algoritm. 10:4,
421–451 (1997)
70. M. Drmota, B. Gittenberger, The width of Galton-Watson trees conditioned by the size.
Discret. Math. Theor. Comput. Sci. 6:2, 387–400 (2004)
71. R. Dudley, Real Analysis and Probability (Cambridge University Press, Cambridge, 2002)
72. T. Duquesne, J.-F. Le Gall, Random trees, Levy processes and spatial branching processes.
Asterisque, 281 (2002). https://www.math.u-psud.fr/~jflegall/Mono-revised.pdf