ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    A result in order statistics related to probabilistic counting (1993)
    Springer
    Computing 51 (1993), S. 15-27 
    Details
    ISSN: 1436-5057
    Keywords: 68R05 ; Order statistics ; asymptotic analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Bezüglich geometrisch verteilter zufälliger Veränderlicher wird dasd-Maximum solcher Ereignisse studiert, also dasd-größte Element, wobei Wiederholungen erlaubt sind. Das quantitative Verhalten von Erwartungswert und Varianz wird ausgiebig analysiert. Insbesondere wird das Verhalten der Varianz für großed mit Hilfe nichttrivialer Techniken aus Kombinatorik und komplexer Analysis untersucht. Diese Resultate haben Anwendungen bei probabilistischen Zählalgorithmen, die zur Schätzung der Kardinalitäten großer Mengen verwendet werden.
    Notes: Abstract Considering geometrically distributed random variables thed-maximum of these events is investigated, i.e. thed-th largest element (with repetitions allowed). The quantitative behaviour of expectation and variance is analyzed thoroughly. In particular the asymptotics of the variance ford getting large is established by means of nontrivial techniques from combinatorial analysis and complex variable theory. These results apply to probabilistic counting algorithms, where the cardinalities of large sets are estimated.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02243826
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A note on a result of R. Kemp on R-typly rooted planted plane trees (1982)
    Springer
    Computing 28 (1982), S. 363-366 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung R. Kemp hat gezeigt, daß die mittlere Höhe von r-fach gewurzelten Bäumen $$\sqrt {\pi n} - \frac{1}{2}(r - 2) + O(\log (n)n^{1/2 - \varepsilon } ), \varepsilon 〉 0, n \to \infty ,$$ ist, falls man annimmt, daß alle solchen Bäume mitn Knoten gleich wahrscheinlich sind. Wir geben für dieses Resultat (mit einem Fehler vonO (1)) einen ziemlich kurzen Beweis.
    Notes: Abstract R. Kemp has shown that the average height of r-tuply rooted planted plane trees is $$\sqrt {\pi n} - \frac{1}{2}(r - 2) + O(\log (n)n^{1/2 - \varepsilon } ), \varepsilon 〉 0, n \to \infty ,$$ assuming that all such trees withn nodes are equally likely. We give a quite short proof of this result (with an error term ofO (1)).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02279818
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Einige Kommentare zu einer bin-packing Aufgabe von W. Knödel (1992)
    Springer
    Computing 47 (1992), S. 247-254 
    Details
    ISSN: 1436-5057
    Keywords: 68R05 ; Bin-packing ; random walk ; generating function ; Mellin transform
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung W. Knödel hat einbin-packing Problem betrachtet, das im Kontext der Zufallspfade gesehen werden kann. Die Höhe eines Zufallspfades ist ein eingehend untersuchter Parameter, der auch in Knödels Modell definiert werden kann. Es zeigt sich, daß der Erwartungswert von der Ordnung $$\sqrt n $$ ist. Um dies zu zeigen werden u.a. die Singularitäten der erzeugenden Funktionen studiert sowie die Mellintransformation verwendet.
    Notes: Abstract W. Knödel has considered a bin-packing problem which can be seen within the context of random walks. The height of a random walk is a well studied parameter which can also be defined in Knödels model. Its average is computed and shown to be of order $$\sqrt n $$ . The methods include singularity analysis of generating functions as well as Mellin transforms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02320195
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Average-Case Analysis of Priority Trees: A Structure for Priority Queue Administration (1998)
    Springer
    Algorithmica 22 (1998), S. 600-630 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Priority trees, Generating functions, Path length, Height of nodes.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Priority trees (p-trees ) are a certain variety of binary trees of size n constructed from permutations of the numbers 1, . . ,n . In this paper we analyze several parameters depending on n (the size) and j (a number between 1 and n ), such as the length of the left path (connecting the root and the leftmost leaf), the height of node j (the distance from the root), the number of left edges on the path from the root to node j , the number of descendants of node j , the number of key comparisons when inserting an element between j and j+1 , the number of key comparisons when cutting the p-trees into two p-trees , the number of nodes with 0 , 1 , or 2 children. Methodologically, recursions are set up according to a fundamental decomposition of the family $ \cal A $ of p-trees (using auxiliary quantities $ \cal B $ and $ \cal C$ ); using generating functions, they lead to systems of differential equations that can be solved explicitly with some efforts. The quantities of interest can then be identified as coefficients in the explicit forms of the generating functions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009243
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Preface (1998)
    Springer
    Algorithmica 22 (1998), S. 363-365 
    Details
    ISSN: 1432-0541
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009229
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Bottom-up mergesort — A detailed analysis (1995)
    Springer
    Algorithmica 14 (1995), S. 340-354 
    Details
    ISSN: 1432-0541
    Keywords: Sorting ; Mergesort ; Analysis of algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Though the behaviors of mergesort algorithms are basically known, the periodicity phenomena encountered in their analyses are not easy to deal with. In this paper closed-form expressions for the necessary number of comparisons are derived for the bottom-up algorithm, which adequately describe its periodic behavior. This allows us, among other things, to compare the top-down and bottom-up mergesort algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294131
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Philippe Flajolet's Research in Analysis of Algorithms and Combinatorics (1998)
    Springer
    Algorithmica 22 (1998), S. 366-387 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Singularity analysis, Generating functions, Mellin transform, Digital sums, Rice's method, Trees, Continued fractions, Random generation, Limit distribution.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Philippe Flajolet's research in theoretical computer science spans over more than 20 years. He made lasting contributions to the analysis of algorithms and analytic combinatorics. Among many of his results we mention here some in such diversified topics as enumeration, number theory, formal languages, continued fractions, automatic analysis of algorithms, Mellin transform, digital sums, recurrences, trees, random generation of combinatorial objects, random graphs and mappings, polynomial factorization, communications, codes, graphics, etc. This gives only a small snapshot of his work, and we encourage the reader to visit Flajolet's homepage http://www-rocq.inria.fr/algo/flajolet/index.html for a fuller account. The bibliography was taken from his homepage and may not be totally complete, although we added a few items. Our paper was written without giving any prior notice to Philippe Flajolet. It reflects the view of the authors and any misunderstandings and shortcomings should be put on their account.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009230
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Spanning tree formulas and chebyshev polynomials (1986)
    Springer
    Graphs and combinatorics 2 (1986), S. 191-200 
    Details
    ISSN: 1435-5914
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The Kirchhoff Matrix Tree Theorem provides an efficient algorithm for determiningt(G), the number of spanning trees of any graphG, in terms of a determinant. However for many special classes of graphs, one can avoid the evaluation of a determinant, as there are simple, explicit formulas that give the value oft(G). In this work we show that many of these formulas can be simply derived from known properties of Chebyshev polynomials. This is demonstrated for wheels, fans, ladders, Moebius ladders, and squares of cycles. The method is then used to derive a new spanning tree formula for the complete prismR n (m) =K m ×C n . It is shown that $$2^{\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)\left( {1 - \frac{1}{{r - 1}} + o\left( 1 \right)} \right)} $$ whereT n (x) is then th order Chebyshev polynomial of the first kind.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01788093
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    facet.materialart.
    Unknown
    A q -Analogue of the Path Length of Binary Search Trees (2001)
    Springer
    Details
    Publication Date: 2001-11-01
    Print ISSN: 0178-4617
    Electronic ISSN: 1432-0541
    Topics: Computer Science , Mathematics
    Published by Springer
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    PAPER CURRENT
  • 10
    facet.materialart.
    Unknown
    Preface (2001)
    Springer
    Details
    Publication Date: 2001-02-01
    Print ISSN: 0178-4617
    Electronic ISSN: 1432-0541
    Topics: Computer Science , Mathematics
    Published by Springer
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    PAPER CURRENT
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...