Muutke küpsiste eelistusi

E-raamat: Algorithmics of Nonuniformity: Tools and Paradigms [Taylor & Francis e-raamat]

(Worcester Polytechnic Institute, Massachusetts, USA), (George Washington University, Washington, District of Columbia, USA)
Teised raamatud teemal:
  • Taylor & Francis e-raamat
  • Hind: 327,75 €*
  • * hind, mis tagab piiramatu üheaegsete kasutajate arvuga ligipääsu piiramatuks ajaks
  • Tavahind: 468,21 €
  • Säästad 30%
Algorithmics of Nonuniformity: Tools and ParadigmsSuurem pilt
Teised raamatud teemal:
Taylor & Francis e-raamatudRohkem infot Taylor & Francis e-raamatute kohta
Raamatu kodulehekülg: https://www.taylorfrancis.com/books/9781315368306
Algorithmics of Nonuniformity is a solid presentation about the analysis of algorithms, and the data structures that support them.

Traditionally, algorithmics have been approached either via a probabilistic view or an analytic approach. The authors adopt both approaches and bring them together to get the best of both worlds and benefit from the advantage of each approach.

The text examines algorithms that are designed to handle general datasort any array, find the median of any numerical set, and identify patterns in any setting. At the same time, it evaluates "average" performance, "typical" behavior, or in mathematical terms, the expectations of the random variables that describe their operations.

Many exercises are presented, which are essential since they convey additional

material complementing the content of the chapters. For this reason, the solutions are more than mere answers, but explain and expand upon related concepts, and motivate further work by the reader.

Highlights:











A unique book that merges probability with analysis of algorithms





Approaches analysis of algorithms from the angle of uniformity





Non-uniformity makes more realistic models of real-life scenarios possible





Results can be applied to many applications





Includes many exercises of various levels of difficulty

About the Authors:

Micha Hofri is a Professor of Computer Science, and former department head at Worcester Polytechnic Institute. He holds a Ph.D. of Industrial Engineering (1972), all from Technion, the Israel Institute of Technology. He has 39 publications in Mathematics.

Hosam Mahmoud is a Professor at, the Department of Statistics at George Washington University in Washington D.C., where he used to be the former chair. He holds an Ph.D. in Computer Science from Ohio State University. He is on the editorial board of five academic journals.
Preface xiii
List of Symbols and Notation xvii
1 Introduction 1(12)
1.1 Computing machines and models
1(6)
1.1.1 Computer elements
1(2)
1.1.2 Turing machines
3(2)
1.1.3 Pseudocode
5(2)
1.2 Asymptotic notation
7(6)
2 Counting 13(36)
2.1 Generating functions
13(11)
2.1.1 Multivariate generating functions and special numbers
17(3)
2.1.2 The principle of inclusion and exclusion
20(4)
2.2 Stirling numbers: Combinatorial interpretation
24(5)
2.2.1 Stirling numbers of the first kind
25(1)
2.2.2 Stirling numbers of the second kind
26(1)
2.2.3 Stirling numbers and powers
27(2)
2.3 Expansion of generating functions
29(7)
2.3.1 Direct expansion of functions
29(5)
2.3.2 Lagrange inversion theorem
34(2)
2.4 Generating functions in probability
36(4)
2.4.1 Convolution of random variables
38(2)
2.5 Generating functions in the solution of recurrences
40(4)
2.6 Notes and sources
44(5)
3 Symbolic Calculus 49(22)
3.1 Admissible operations
51(9)
3.1.1 The sum and product rules
51(5)
3.1.2 Labeled combinatorial operations
56(4)
3.2 Applications of the symbolic calculus
60(9)
3.2.1 Compositions of integers
60(4)
3.2.2 Positional tree counting
64(1)
3.2.3 Plane tree counting
65(1)
3.2.4 Rooted oriented trees
66(3)
3.3 Notes and sources
69(2)
4 Languages and Their Generating Functions 71(34)
4.1 Regular languages
74(3)
4.2 Finite-state automata
77(3)
4.3 Finite-state automata and regular languages
80(5)
4.4 Generating functions and their regular languages
85(3)
4.4.1 Word equations
85(1)
4.4.2 Solutions to word equations
86(2)
4.5 Counting regular languages
88(14)
4.5.1 A matricial alternative to word equations
93(4)
4.5.2 Admissibility considerations
97(5)
4.6 Notes and sources
102(3)
5 Probability in Algorithmics 105(56)
5.1 Random variables
108(10)
5.1.1 Independence of discrete random variables
110(2)
5.1.2 Probability spaces for sequences of random variables arising in combinatorial objects
112(3)
5.1.3 Illustration via runs
115(3)
5.2 Characteristic functions
118(2)
5.3 Mixed distributions
120(2)
5.4 Inequalities
122(9)
5.4.1 Boole inequality
123(2)
5.4.2 Chebyshev inequality
125(1)
5.4.3 Markov inequality
126(1)
5.4.4 Gauss inequality
127(2)
5.4.5 Schwarz inequality
129(2)
5.5 Modes of probabilistic convergence
131(7)
5.6 Some classic results from probability theory
138(6)
5.6.1 Weak and strong laws
139(4)
5.6.2 Further convergence theorems
143(1)
5.7 Central limit theorems
144(3)
5.8 Martingales
147(3)
5.9 Generating random numbers
150(4)
5.9.1 The probability integral transform
152(2)
5.10 Notes and sources
154(7)
6 Functional Transforms 161(26)
6.1 Mellin transform
161(10)
6.1.1 Properties of the Mellin transform
161(6)
6.1.2 Harmonic sums
167(4)
6.2 Poissonization
171(11)
6.2.1 Algebraic depoissonization-uniform distribution
175(3)
6.2.2 Algebraic depoissonization-arbitrary distributions
178(3)
6.2.3 Asymptotics of the Poisson transform
181(1)
6.3 Notes and sources
182(5)
7 Nonuniform Polya Urn Schemes 187(40)
7.1 Classic Polya urns
187(2)
7.2 Tenability
189(1)
7.3 Polya urns with ball activity
190(24)
7.3.1 Polya-Eggenberger urn with ball activity
191(3)
7.3.2 Ehrenfest urn with ball activity
194(4)
7.3.3 Bagchi-Pal urn schemes with ball activity
198(11)
7.3.4 Triangular urns with ball activity
209(5)
7.4 A nonuniform Polya process
214(8)
7.5 Notes and sources
222(5)
8 Nonuniform Data Models 227(68)
8.1 Restricted permutations
227(12)
8.1.1 The combinatorics of 1-away permutations
229(6)
8.1.2 Properties of 1-away permutations via recurrences
235(4)
8.2 Automata for restricted permutations
239(5)
8.2.1 1-away permutations
239(2)
8.2.2 2-away permutations
241(3)
8.3 Random multisets
244(15)
8.3.1 Inversions in random multisets
246(11)
8.3.2 Multinomially generated multisets
257(2)
8.4 Binary search trees
259(15)
8.4.1 Optimal binary search trees
262(3)
8.4.2 Bounds on the (optimal) access cost
265(4)
8.4.3 Nearly optimal binary search trees
269(4)
8.4.4 Binary search trees-unknown p
273(1)
8.5 Digital trees
274(13)
8.5.1 The Bernoulli model
275(1)
8.5.2 Depth of nodes in a trie
276(8)
8.5.3 Clades
284(3)
8.6 Notes and sources
287(8)
9 Sorting Nonuniform Data 295(26)
9.1 Data comparisons
295(2)
9.2 Insertion sort
297(9)
9.2.1 Linear insertion sort
298(1)
9.2.2 Inversions under the uniform random permutation model
299(2)
9.2.3 Performance on a slightly perturbed input
301(1)
9.2.4 Sorting a partially sorted file
302(3)
9.2.5 Insertion sort for multisets
305(1)
9.3 Quick sort
306(12)
9.3.1 Three-way partition
308(2)
9.3.2 Analysis of Quick Sort for random multisets
310(8)
9.4 Notes and sources
318(3)
10 Recursive Trees 321(48)
10.1 Uniform recursive trees
323(6)
10.1.1 Outdegrees in uniform recursive trees
323(2)
10.1.2 Depth of nodes in a uniform recursive tree
325(1)
10.1.3 Leaves in uniform recursive trees
326(3)
10.2 Trees with vertex affinity proportional to age
329(5)
10.2.1 Degree profile in age-affinity random recursive trees
330(1)
10.2.2 Depth of nodes in an age-affinity random recursive tree
331(1)
10.2.3 Leaves in age-affinity random recursive trees
332(2)
10.3 Recursive trees grown under the power of choice
334(8)
10.3.1 Degree profile of k-minimal-label recursive trees
335(3)
10.3.2 Depth of nodes in k-minimum-label tree models
338(3)
10.3.3 Maximal-label recursive tree
341(1)
10.4 Preferential attachment tree model
342(7)
10.4.1 Leaves in a random PORT
344(1)
10.4.2 Depth of nodes in a random PORT
345(4)
10.5 Blocks trees
349(11)
10.5.1 Building trees from random tree blocks
349(2)
10.5.2 Leaves in a blocks tree
351(1)
10.5.3 Depth of nodes in blocks trees
352(5)
10.5.4 The height of a random blocks tree
357(3)
10.6 Hoppe trees
360(5)
10.6.1 The number of species
361(3)
10.6.2 Sizes of species populations
364(1)
10.7 Notes and sources
365(4)
11 Series-Parallel Graphs 369(32)
11.1 Some models of binary series-parallel graphs
371(3)
11.2 Enumerating binary series-parallel graphs
374(3)
11.3 The order of binary series-parallel graphs
377(4)
11.3.1 The order of factorial binary series-parallel graphs
377(2)
11.3.2 The order of Catalan binary series-parallel graphs
379(2)
11.4 Path length in binary series-parallel graphs
381(10)
11.4.1 Path length under the factorial model
381(4)
11.4.2 Path length under the Catalan model
385(6)
11.5 A series-parallel graph with unrestricted degrees
391(8)
11.5.1 Nodes of small outdegree
392(7)
11.6 Notes and sources
399(2)
Bibliography 401(17)
Solutions 418(141)
Index 559
Micha Hofri is a professor of computer science, and former department head at Worcester Polytechnic Institute. He holds a Ph.D. of industrial engineering (1972), all from the Technion-Israel Institute of Technology. He has 39 publications in Mathematics.



Hosam Mahmoud is a professor at the Department of Statistics at George Washington University in Washington D.C., where he is the former chair. He holds a Ph.D. in computer science from Ohio State University. He is on the editorial board of five academic journals.
Püsilink: https://www.kriso.ee/db/9781315368306_pe.html
Märksõnad: