Average Case Analysis of Algorithms on Sequences

1. Auflage 2001
ISBN: 978-0-471-24063-1
Verlag: Wiley

Buch, Englisch, 576 Seiten, Format (B × H): 161 mm x 240 mm, Gewicht: 1029 g

Reihe: Wiley-Interscience Series in Discrete Mathematics and Optimization

Zufallsgesteuerte Algorithmen erwiesen sich im Laufe des letzten Jahrzehnts in vielen Zusammenhängen als sehr erfolgreich, darunter in der computergestützten Geometrie, der Visualisierung naturwissenschaftlicher Daten, der Molekularbiologie und in der Informationstheorie. Dieser Band vereint mit einem ausgesprochen interdisziplinären Ansatz analytische und probabilistische Theorien. Jedes Kapitel wird durch Übungsaufgaben und weiterführende Anmerkungen ergänzt.

Autoren/Hrsg.

Szpankowski, Wojciech

Fachgebiete

• Mathematik | Informatik Mathematik Operations Research Graphentheorie
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik Mathematik Stochastik Mathematische Statistik
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Computeranwendungen in der Mathematik
• Mathematik | Informatik Mathematik Mathematische Analysis
• Mathematik | Informatik Mathematik Stochastik Wahrscheinlichkeitsrechnung
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten

Inhaltsverzeichnis

Foreword.

Preface.

Acknowledgments.

PROBLEMS ON WORDS.

Data Structures and Algorithms on Words.

Probabilistic and Analytical Models.

PROBABILISTIC AND COMBINATORIAL TECHNIQUES.

Inclusion-Exclusion Principle.

The First and Second Moment Methods.

Subadditive Ergodic Theorem and Large Deviations.

Elements of Information Theory.

ANALYTIC TECHNIQUES.

Generating Functions.

Complex Asymptotic Methods.

Mellin Transform and Its Applications.

Analytic Poissonization and Depoissonization.

Bibliography.

Index.

Über Autor(innen)

WOJCIECH SZPANKOWSKI, PhD, is Professor of Computer Science at Purdue University and has held visiting research positions at the Technical University of Gdansk, McGill University, INRIA, the Technical University of Vienna, University of Witwatersrand, Hewlett-Packard Laboratories, and Stanford University. He is the author of over 100 scientific publications in the areas of analysis of algorithms, information theory, performance evaluation of computer networks, stability of distributed systems, and queueing theory.