Fundamentals of the Average Case Analysis of Particular Algorithms

ISBN-13: 9783519021001 / Niemiecki / Miękka / 1985 / 233 str.

Rainer Kemp

Opis

This book provides an introduction to the analysis of particular algorithms. lt has its origin in lecture courses given at the Universitat des Saarlandes, Saarbrucken in 1980 and attheJohann Wolfgang Goethe-Universitat, Frankfurt a.M. in 1982. The material can be covered in a one-semester course. ln preparing the notes for publication as a book, I have added a considerable amount of material additional to the lecture notes, with the intention of making the book more useful. My prime consideration has been to produce a textbook whose scope is selective; some of the omitted material is outlined in various exercises and should be useful in indicating possible approaches to certain problems. Moreover, problems are provided to furnish examples, to expand on the material or to indicate related results, and occasionally to guide the reader through the steps of lengthy proofs and derivations. I have referred, in various places, to those books and original papers which have been of particular assistance to me. I wish to take this opportunity to thank all those who have had apart in this work, and who have made this book possible. I am particularly indebted to Professor Dr. Gunter Hotz for his encouragement in the writing of this textbook. Special thanks are due to Ute Schurfeld for careful reading of the text. Dr. P. Spuhler from Teubner Verlag provided co-operative and competent support in all editorial problems. Finally, I wish to thank Teubner-Verlag and John Wiley & Sons for very good and timely editorial work.

Spis treści

1. Introduction.- 2. A Simple Class of Algorithms.- 3. Permutations and Their Applications.- 4. Random Walks, Trees, Lists.- 5. Applications.- Appendix A.- 1. Basic Definitions of Probability Theory.- 2. Grammars—Formal Power Series.- 3. Generating Functions.- 4. Linear Recurrences.- 5. Dirichlet Series.- 6. Laurent Series—Residues—Cauchy Integral Formula.- 7. Euler’s Summation Formula.- Appendix B.- 1. Numbers in Combinatorial Analysis.- 2. Special Functions.- References.- Index of Notation.