[Zurück zum
Forschungsbericht]

Analyse von Algorithmen und randomisierte Algorithmen

Projektbeschreibung:
Zur Analyse von Algorithmen, die in der Informatik und Stochastik angewendet werden, ist in Arbeiten von Rösler (1991, 1992) und Rachev und Rüschendorf (1990, 1995) eine neue Methode entwickelt worden. Es handelt sich um eine Kontraktionsmethode basierend auf der Verwendung geeigneter minimaler Metriken. Mit Hilfe dieser Methode ist es gelungen, für eine große Klasse von Algorithmen und allgemeiner rekursiven Strukturen das asymptotische Verhalten zu beschreiben. Die Beispielklassen die dieser Methode zugänglich sind enthalten insbesondere verschiedene Such- und Sortierverfahren, Algorithmen zur Auflösung von Kollisionen in Netzwerken (CRI), Algorithmen im Zusammenhang mit GARCH-Modellen, Baumalgorithmen, aber auch Bootstrapverfahren und iterative Funktionensysteme, die für das Image encoding von Interesse sind. Weitere Themengebiete sind die Konstruktion multifraktaler Maße, Produkte zufälliger Matrizen sowie die fraktale Kodierung von Bildern und die Untersuchung von GARCH-Modellen für Finanzdaten. Neben der Analyse von Algorithmen werden auch randomisierte Algorithmen vom Monte-Carlo-Typ für kombinatorische und graphentheoretische Probleme entwickelt und analysiert, wie z.B. für spanning trees oder für Gitterprobleme.

Tel: 0761/203-5665
Email: ruschen@stochastik.uni-freiburg.de
Projektlaufzeit:
Projektbeginn: 2002
Projektende: (unbegrenzt)
Projektleitung:
Prof. Dr. Ludger Rüschendorf

Albert-Ludwigs-Universität Freiburg
Abteilung für Mathematische Stochastik
Prof. Dr. Ludger Rüschendorf
Ernst-Zermelo-Straße 1
79104 Freiburg

Telefon: 0761/203-5664
Fax: 0761/203-5661
Email: sekretariat@stochastik.uni-freiburg.de
http://www.stochastik.uni-freiburg.de/rueschendorf
Schlagworte:

    Analyse von Algorithmen, Konstruktion multifraktaler Maße, P

Projektbezogene Publikationen:

  • Neininger R, Rüschendorf L: A general limit theorem for recursive algorithms and combinatorial structures. Ann Appl Probab, 2004; 14: 378-418.
  • Fehrenbach J, Rüschendorf L: A multicommodity flow for the counting of spanning trees. Preprint Uni Freiburg, 2003; 25.
  • Neininger R, Rüschendorf L: Analysis of algorithms by the contraction method: additive and max-recursive sequences. Preprint Uni Freiburg, 2003; 24.
  • Neininger R, Rüschendorf L: Multivariate aspects of the contraction method. Preprint Uni Freiburg, 2003; 19.
  • Neininger R, Rüschendorf L: Rates of convergence for Quicksort. Journal of Algorithms, 2002; 44 (1): 52-62.
  • Neininger R, Rüschendorf L: On the contraction method with degenerate limit equation. Preprint Uni Freiburg, 2002; 19.
  • Anthes B, Rüschendorf L: On the weighted Euclidean matching problem in R^d-dimensions. Applicationes Mathematicae, 2001; 28: 181-190.
  • Cramer M, Rüschendorf L: Convergence of two-dimensional branching recursions. Journal Computational Appl. Math., 2001; 130: 53-73.
  • Neininger R, Rüschendorf L: Limit laws for partial match queries in quadtrees. The Annals of Applied Probability, 2001; 11 (2): 452-469.
  • Hutchinson J.R, Rüschendorf L: Random fractals and probability metrics. Advances of Appl. Prob., 2000; 32: 925-947.
  • Rüschendorf L, Sachs G: On partitioning algorithms for matching problems. Journal Appl. Probab., 2000; 37: 494-503.
  • Hutchinson J.R, Rüschendorf L: Random fractal measures via the contraction method. Indiana Univ. Math. J., 1998; 47: 471-488.
  • Cramer M: Convergence of a branching type recursion with non-stationary immigration. Metrika, 1997; 46 (3): 187-211.
  • Cramer M: Stochastic analysis of 'simultaneous merge-sort'. J. Adv. Appl. Probab., 1997; 29 (3): 669-694.
  • Cramer M: Stochastic analysis of the Merge-Sort algorithm. J. Random Struct. Algorithms, 1997; 1/11: 81-96.
  • Feldman P, Rachev S.T, Rüschendorf L: Limiting distribution of the collision resolution interval. Statistica Neerlandica, 1997; 51: 1-22.
  • Cramer M: A note concerning the limit distribution of the quicksort algorithm. RAIRO, Inform. Theor. Appl., 1996; 30: 195-207.
  • Cramer M, Rüschendorf L: Convergence of a branching type recursion. Ann. Inst. Henri Poincaré, 1996; 32: 725-741.
  • Feldman P, Rachev S.T, Rüschendorf L.: Limit theorems for recursive algorithms. J. Comp. Appl. Mathematics, 1995; 56: 169-182.
  • Rachev S.T, Rüschendorf L: Probability metrics and recursive algorithms. Adv. Appl. Prob., 1995; 27: 770-779.
  • Rüschendorf L: Convergence of the iterative proportional fitting procedure. Ann. Statistics, 1995; 23: 1160-1174.

Aktueller Forschungsbericht