Skip to main content
main-content

Über dieses Buch

Probabilistic Analysis of Algorithms begins with a presentation of the "tools of the trade" currently used in probabilistic analyses, and continues with an applications section in which these tools are used in the analysis ofr selected algorithms. The tools section of the book provides the reader with an arsenal of analytic and numeric computing methods which are then applied to several groups of algorithms to analyze their running time or storage requirements characteristics. Topics covered in the applications section include sorting, communications network protocols and bin packing. While the discussion of the various algorithms is sufficient to motivate their structure, the emphasis throughout is on the probabilistic estimation of their operation under distributional assumptions on their input. Probabilistic Analysis of Algorithms assumes a working knowledge of engineering mathematics, drawing on real and complex analysis, combinatorics and probability theory. While the book is intended primarily as a text for the upper undergraduate and graduate student levels, it contains a wealth of material and should also prove an important reference for researchers. As such it is addressed to computer scientists, mathematicians, operations researchers, and electrical and industrial engineers who are interested in evaluating the probable operation of algorithms, rather than their worst-case behavior.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
Algorithms embody methods for the treatment of data so as to meet desired objectives. Normally we specify an algorithm by stating
(a)
What is a legal input for the algorithm. This contains typically parameters and data. For example, an integer n followed by n pairs of real numbers.
 
(b)
The transformation that the algorithm should perform on the input. Equivalently, we could provide a description of the output in terms of the input. For example, in (a), when the number pairs are construed as point coordinates in the plane, we could ask for the output to be a sequence of those points that are the convex hull of the entire set.
 
Micha Hofri

Chapter 2. Tools of the Trade

Abstract
It is rare that the analysis of an algorithm produces closed-form expressions in terms of standard functions that are convenient to use. It is even rarer that the results have a form simple enough, to provide an intuitive insight into the dependence of the algorithm properties on the various parameters of the input. More often the analyst nets an unwieldy sum, such an integral, or worse - the result is only available in terms of transforms that are hard to invert; sometimes even this is not available explicitly: one can only determine a recalcitrant equation that the result satisfies.
Micha Hofri

Chapter 3. Algorithms over Permutations

Abstract
In this chapter we concentrate on a simple data structure: a linear array, containing numbers. The basic properties of this structure are its length and the order of the numbers in it. The numbers are considered unrelated, although most of the discussion will assume they are all distinct. Since the actual values of the numbers are immaterial, we may assume - and shall do so through most this chapter, excepting Section 3.3.3 - that they are integers. When an array of size n is considered, the numbers in it are assumed to be 1 through n. Such an array is a “linear representation of a permutation”. Simple as it all appears, and even Chicken Little would agree with that, this structure shall furnish us with opportunities for interesting mathematics. We start meekly enough with MAX.
Micha Hofri

Chapter 4. Algorithms for Communications Networks

Abstract
In this chapter we present analyses of communications-related algorithms and protocols. The criteria I used for selection of the presented algorithms concern the type of analysis and varieties of mathematics involved in computing their operational characteristics, rather than their engineering merits. Indeed, some of the presented protocols must be considered quite unacceptable, on practical grounds. One hopes, nevertheless, that the analysis proper will prove interesting and useful in other circumstances as well. Virtually no previous knowledge of communications techniques and terminology is required, beyond what one assimilates from day-to-day life.
Micha Hofri

Chapter 5. Bin Packing Heuristics

Abstract
The Bin Packing (BP) problem is one of the more celebrated members of the class of problems commonly titled “combinatorial optimization”. Other famous ones are machine scheduling, the knapsack problem, job assignment, the traveling salesman itinerary and many more. Practically all of these problems may be viewed as special cases of integer programming, but they display special structure and characteristics which have led to specialized algorithms and approaches. While the fame of the BP problem derives to no little extent from its being simple to present and relatively easy to analyze, the significance of many others of this class of problems derives from their commercial value in a business environment; hence the great interest in them. Karp (1986) gives a sweeping overview of the field.
Micha Hofri

Backmatter

Weitere Informationen