Login
 
Main Data
Author: Imre Csiszár, Gyula O. H. Katona, Gábor Tardos, Gábor Wiener
Editor: Imre Csiszár, Gyula Katona, Gabor Tardos
Title: Entropy, Search, Complexity
Publisher: Springer-Verlag
ISBN/ISSN: 9783540327776
Edition: 1
Price: CHF 135.50
Publication date: 01/01/2007
Content
Category: Informatik, EDV Buch
Language: English
Technical Data
Pages: 262
Kopierschutz: DRM
Geräte: PC/MAC/eReader/Tablet
Formate: PDF
Table of contents

This book collects survey papers in the fields of entropy, search and complexity, summarizing the latest developments in their respective areas. More than half of the papers belong to search theory which lies on the borderline of mathematics and computer science, information theory and combinatorics, respectively. The book will be useful to experienced researchers as well as young scientists and students both in mathematics and computer science.

Table of contents
Contents6
Preface8
Two Colors and More10
1. The majority problem10
2. First Generalization: Determining a k-majority12
3. Second generalization: more colors17
4. Third generalization: the plurality problem20
5. The liar problem23
6. A final generalization: determining the color classes26
References27
Coding with Feedback and Searching with Lies28
1. Introduction28
2. Definitions and terminology31
3. A Berlekamp strategy and the translation bound33
4. Linear growth35
5. Fixed error35
6. Asymptotic results for fixed error38
7. Fixed number of messages39
8. Fast algorithm40
9. Comparison and interval questions41
10. Asymmetric questions43
11. Detecting errors44
12. Linearly bounded error45
13. Local restrictions47
14. Unbounded search47
15. Optimal strategies with minimum adaptiveness49
16. The continuous case50
17. Q-ary case54
18. The probabilistic case57
19. Search and information theory59
20. Identification and a general search model61
21. The game without feedback62
22. Learning and searching63
23. Unequal protection with feedback64
References67
Nonadaptive and Trivial Two-Stage Group Testing with Error-Correcting de-Disjunct Inclusion Matrices72
1. Group testing72
2. Inclusion matrices73
3. de-disjunct matrices76
4. Some optimal de-disjunct matrices with constant rowweight81
5. Remarks82
References82
Model Identification Using Search Linear Models and Search Designs86
1. Introduction86
2. Search linear model88
3. Search procedure, search probabilities, and performance evaluation88
4. Search designs90
5. Statistical design of scientific experiments96
6. The information provided by an experiment98
7. Some elegant combinatorial problems arising in search designs102
8. Analysis under the general slm using simulation distributions105
References110
Information Topologies with Applications114
1. Introduction and preliminaries114
2. The strong information topology121
3. Continuity of entropy and divergence128
4. Weak information topologies135
5. The conditional limit theorem141
6. Discussion148
References149
Reinforced Random Walk152
An open problem152
Spontaneous emergence of opinions154
The current state of affairs158
References159
Quantum Source Coding and Data Compression160
1. Classical source coding160
2. Quantum mechanical sources167
3. Extension to sources with memory172
4. Appendix174
References178
Information Theory at the Service of Science180
1. Introduction, background180
2. Game Theoretical Equilibrium, the idea183
3. Information theoretical concepts184
4. Instances of GTE188
5. Technical discussion of the Dmin-game194
References205
Analysis of Sorting Algorithms by Kolmogorov Complexity ( A Survey)210
1. Introduction210
2. Bubblesort214
3. Heapsort216
4. Shellsort220
5. Dobosiewicz Sort and Shakersort225
6. Sorting with queues and stacks227
References232
Recognition Problems in Combinatorial Search234
1. Introduction234
2. Preliminaries235
3. Recognition problems241
4. The generalized communication model247
5. Recognition problems in partially ordered sets253
6. Predetermined complexity260
7. Open problems263
References264