With the advent of computers, search theory emerged in the sixties as an area of research in its own right. Sorting questions arising in computer science were the first to be thoroughly studied. But soon it was found that the intrinsic complexity of many other data structures could be fruitfully analyzed from a search theoretic point of view. Worst case and average case analyses of algorithms have since become indispensable tools in many fields bordering on combinatorics and computer science.
Combinatorial Search gives an overview of the subject, ranging from such time-honored problems as the defective coin puzzle to some very recent advances in parallel computing. It stresses the strong connections with information theory, combinatorics, tree structures, order and graphs.
Each chapter contains a large number of exercises of various degrees of difficulty with an addendum of solutions to recommended exercises. There are also bibliographical notes to all topics discussed and all chapters are concluded with an extensive list of open problems.
Author(s): Martin Aigner
Series: Wiley Teubner Series on Applicable Theory in Computer Science
Publisher: John Wiley & Sons
Year: 1988
Language: English
Pages: 372
Tags: Математика;Дискретная математика;
Contents......Page 7
1.1 The Model......Page 9
1.2 Search Processes and Trees......Page 15
1.3 Search Processes and Codes......Page 21
1.4 Search Processes: Worst Case......Page 25
1.5 Search Processes: Average Case......Page 29
1.6 Alphabetic Search Processes......Page 45
1.7 Binary Search Trees......Page 51
1.8 Predetermined Algorithms......Page 61
1.9 Binary Search Processes......Page 66
1.10 A Game-Theoretic Point of View......Page 76
Problems......Page 80
Notes and References......Page 81
2.1 Balance Scale......Page 84
2.2 More Coins are Defective......Page 96
2.3 Weighings With a Spring Scale......Page 102
2.4 Spring Scale: Arbitrary Case......Page 113
Problems......Page 123
Notes and References......Page 124
3.1 Graph Notions......Page 127
3.2 Searching For an Edge: Binary Variant......Page 132
3.3 Searching For an Edge: Ternary Variant......Page 149
3.4 Searching For an Edge......Page 159
3.5 Searching For Subgraphs......Page 164
3.6 Recognizing Subgraphs......Page 171
Problems......Page 191
Notes and References......Page 193
4 Sorting Problems......Page 196
4.1 Linear Sorting......Page 198
4.2 Merging Chains......Page 207
4.3 Selection Problems......Page 221
4.4 Sorting Networks......Page 232
4.5 Parallel Sorting......Page 249
Problems......Page 260
Notes and References......Page 261
5.1 The General Sorting Problem......Page 265
5.2 Producing Posets......Page 274
5.3 Data Location......Page 283
5.4 Correlation Among Linear Extensions......Page 291
Problems......Page 305
Notes and References......Page 306
6.1 Notions From Convex Geometry......Page 310
6.2 Polyhedral Membership Problem......Page 314
6.3 Colorings of Graphs......Page 320
6.4 Longest Increasing Subsequences......Page 328
Problems......Page 334
Notes and References......Page 335
Answers to Recommended Exercises......Page 337
Index......Page 368
