We obtain new results regarding the precise average-case analysis of the main quantities that intervene in algorithms of a broad Euclidean type. We develop a general framework for the analysis of such algorithms, where the average-case complexity of an algorithm is related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithms. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory and provide...
En utilisant la géométrie du demi-plan de Poincaré et des familles de disques classiques - disques de Ford, disques de Farey - nous décrivons les domaines de niveau associés à la constante d'Hermite et au plus court vecteur d'un réseau. Nous en déduisons une évaluation très précise des fonctions de répartition correspondantes, en particulier au voisinage de l'origine.
Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural assumptions...
Digital trees or tries are a general purpose flexible data structure
that implements dictionaries built on words. The present paper is focussed
on the average-case analysis of
an important parameter of this
tree-structure, , the stack-size.
The stack-size of a tree is the memory needed
by a storage-optimal preorder traversal. The analysis is carried out
under a general model in which words are produced by
a source (in the information-theoretic sense)
that emits symbols.
Under some natural...
Download Results (CSV)