Csisz?r I., Katona G., Tardos G. (eds.) Entropy, Search, Complexity

формат pdf
размер 1.51 МБ
добавлен 22 октября 2011 г.

Издательство Springer, 2007, -261 pp.
J?nos Bolyai Mathematical Society.
The present volume is a collection of survey papers in the fields given in the title. They summarize 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 volume is slightly related to the twin conferences Search And Communication Complexity and Information Theory In Mathematics held at Balatonlelle, Hungary in 2000. These conferences led us to believe that there is a need for such a collection of papers.
Two Colors and More.
Coding with Feedback and Searching with Lies.
Nonadaptive and Trivial Two-Stage Group Testing with Error-Correcting de-Disjunct Inclusion Matrices.
Model Identification.
Using Search Linear Models and Search Designs.
nformation Topologies with Applications.
Reinforced Random Walk.
Quantum Source Coding and Data Compression.
nformation Theory at the Service of Science.
Analysis of Sorting Algorithms by Kolmogorov Complexity.
Recognition Problems in Combinatorial Search.

Похожие разделы

Смотрите также

Anderson I. Combinatorics of Finite Sets

формат djvu
размер 1.86 МБ
добавлен 18 апреля 2011 г.

Dover Publications, 2002. - 272 pages. Coherent treatment provides comprehensive view of basic methods and results of the combinatorial study of finite set systems. The Clements-Lindstrom extension of the Kruskal-Katona theorem to multisets is explored, as is the Greene-Kleitman result concerning k-saturated chain partitions of general partially ordered sets. Connections with Dilworth's theorem, the marriage problem, and probability are also dis...

Buss S. Circuit Complexity and Computational Complexity

Статья

формат pdf
размер 573.37 КБ
добавлен 24 октября 2011 г.

University of California, 1992, -154 pp. These lecture notes were written for a topics course in the Mathematics Department at the University of California, San Diego during the winter and spring quarters of 1992. Introduction to circuit complexity. Theorems of Shannon and Lupanov giving upper and lower bounds of circuit complexity of almost all Boolean functions. Spira's theorem relating depth and formula size. Khrapchenko's lower bound on formu...

Chikalov I. Average Time Complexity of Decision Trees

формат pdf
размер 975.04 КБ
добавлен 09 ноября 2011 г.

Издательство Springer, 2011, -114 pp. The monograph is devoted to theoretical and experimental study of decision trees with a focus on minimizing the average time complexity. The study resulted in upper and lower bounds on the minimum average time complexity of decision trees for identification problems. Previously known bounds from information theory are extended to the case of identification problem with an arbitrary set of attributes. Some ex...

Golumbic M.C. Algorithmic Graph Theory and Perfect Graphs

формат djvu
размер 2.3 МБ
добавлен 24 октября 2011 г.

Издательство Academic Press, 1980, -303 pp. Research in graph theory and its applications has increased considerably in recent years. Typically, the elaboration of new theoretical structures has motivated a search for new algorithms compatible with those structures. Rather than the arduous and systematic study of every new concept definable with a graph, the main task for the mathematician is to eliminate the often arbitrary and cumbersome defin...

Jukna S. Boolean Function Complexity. Advances and Frontiers

формат pdf
размер 2.98 МБ
добавлен 24 октября 2011 г.

Издательство Springer, 2011, -633 pp. Boolean circuit complexity is the combinatorics of computer science and involves many intriguing problems that are easy to state and explain, even for the layman. This book is a comprehensive description of basic lower bound arguments, covering many of the gems of this complexity Waterloo that have been discovered over the past several decades, right up to results from the last year or two. Many open problems...

Kreher D.L., Stinson D.R. Combinatorial Algorithms. Generation, Enumeration and Search

формат djvu
размер 3.59 МБ
добавлен 04 октября 2011 г.

Издательство CRC Press, 1999, -340 pp. Our objective in writing this book was to produce a general, introductory textbook on the subject of combinatorial algorithms. Several textbooks on combinatorial algorithms were written in the 1970s, and are now out-of-date. More recent books on algorithms have either been general textbooks, or books on specialized topics, such as graph algorithms to name one example. We felt that a new textbook on combinat...

Lamagna E.A. The Complexity of Monotone Functions

Дисертация

формат pdf
размер 1.24 МБ
добавлен 15 декабря 2011 г.

Диссертация, Brown University, 1975, -110 pp. An important open question in the field of computational complexity is the development of nontrivial lower bounds on the number of logical operations required to compute switching functions. Two important measures of functional complexity are combinational complexity, corresponding to the minimal number of operations in any computational chain (straight-line algorithm or feedback-free network) for th...

Papadimitriou C.M. Computational Complexity

формат djvu
размер 4.5 МБ
добавлен 28 октября 2011 г.

Издательство Addison-Wesley, 1994, -540 pp. This book is an introduction to the theory of computational complexity at a level appropriate for a beginning graduate or advanced undergraduate course. Computational complexity is the area of computer science that contemplates the reasons why some problems are so hard to solve by computers. This field, virtually non-existent only 20 years ago, has expanded tremendously and now comprises a major part of...

Paterson M.S. (ed.) Boolean Function Complexity

формат djvu
размер 1.16 МБ
добавлен 28 октября 2011 г.

Издательство Cambridge University Press, 1992, -211 pp. Complexity theory attempts to understand and measure the intrinsic difficulty of computational tasks. The study of Boolean Function Complexity reaches for the combinatorial origins of these difficulties. The field was pioneered in the 1950's by Shannon, Lupanov and others, and has developed now into one of the most vigorous and challenging areas of theoretical computer science. In July 1990...

Wegener I. The Complexity of Boolean Functions

формат pdf
размер 1.88 МБ
добавлен 11 мая 2011 г.

Wegener I. The Complexity of Boolean Functions. (Wiley-Teubner series in computer science). John Wiley & Sons Ltd, and B. G. Teubner, Stuttgart, 1987. Различные аспекты теории сложности: булевы функции, схемы, формулы, программы итд. Булевы функции и схемы. Минимизация булевых функций. Разработка эффективных схем для некоторых важных функций. Асимптотики и универсальные схемы. Нижние границы сложности схем. Монотонные схемы. Связь между сложн...