This book is devoted to the study of deterministic and nondeterministic computation trees. Computation trees are a natural generalization of decision trees: in addition to the one-place predicate-type operations (attributes) used in decision trees, computation trees can use multi-place predicate and function operations. They arise both where we deal with algorithms for solving problems of combinatorial optimization, computational geometry, etc., and where we solve classification or predict...

This book is devoted to the transforming of decision rule systems into deterministic and nondeterministic decision trees that recognize the properties of these systems. It continues the development of the so-called syntactic approach to the study of the transformation problem, which assumes that the input data is unknown, and there is only a system of decision rules that must be transformed into decision trees.The book studies the depth and weighted depth of decision trees based on...

In this book, the concept of a hypothesis about the values of all attributes is added to the standard decision tree model, considered, in particular, in test theory and rough set theory. This extension allows us to use the analog of equivalence queries from exact learning and explore decision trees that are based on various combinations of attributes, hypotheses, and proper hypotheses (analog of proper equivalence queries). The two main goals of this book are (i) to provide tools for the e...

This book explores, within the framework of rough set theory, the complexity of decision trees and decision rule systems and the relationships between them for problems over information systems, for decision tables from closed classes, and for problems involving formal languages. Decision trees and systems of decision rules are widely used as means of representing knowledge, as classifiers that predict decisions for new objects, as well as algorithms for solving various problems of fault d...

In this book, we study decision trees for fault diagnosis in circuits and switching networks, which are among the most fundamental models for computing Boolean functions. We consider two main cases: when the scheme (circuit or switching network) has the same mode of operation for both calculation and diagnostics, and when the scheme has two modes of operation—normal for calculation and special for diagnostics. In the former case, we get mostly negative results, including superpolynomial lo...

This book introduces a fairly universal approach to the design and analysis of exact optimization algorithms for multi-objective combinatorial optimization problems. It proposes the circuits without repetitions representing the sets of feasible solutions along with the increasing and strictly increasing cost functions as a model for such problems. The book designs the algorithms for multi-stage and bi-criteria optimization and for counting the solutions in the framework of this model....

This book compares four parameters of problems in arbitrary information systems: complexity of problem representation and complexity of deterministic, nondeterministic, and strongly nondeterministic decision trees for problem solving. Deterministic decision trees are widely used as classifiers, as a means of knowledge representation, and as algorithms. Nondeterministic (strongly nondeterministic) decision trees can be interpreted as systems of true decision rules that cover all objects (ob...

The results presented here (including the assessment of a new tool – inhibitory trees) offer valuable tools for researchers in the areas of data mining, knowledge discovery, and machine learning, especially those whose work involves decision tables with many-valued decisions. The authors consider various examples of problems and corresponding decision tables with many-valued decisions, discuss the difference between decision and inhibitory trees and rules, and develop tools for their analy...

Dynamic programming is an efficient technique for solving optimization problems. It is based on breaking the initial problem down into simpler ones and solving these sub-problems, beginning with the simplest ones. A conventional dynamic programming algorithm returns an optimal object from a given set of objects. This book develops extensions of dynamic programming, enabling us to (i) describe the set of objects under consideration; (ii) perform a multi-stage optimization of objects relativ...

Discrete optimization problems are everywhere, from traditional operations research planning (scheduling, facility location and network design); to computer science databases; to advertising issues in viral marketing. Yet most such problems are NP-hard; unless P = NP, there are no efficient algorithms to find optimal solutions. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions. The book is organized around central algorit...

Despite growing interest, basic information on methods and models for mathematically analyzing algorithms has rarely been directly accessible to practitioners, researchers, or students. An Introduction to the Analysis of Algorithms, Second Edition, organizes and presents that knowledge, fully introducing primary techniques and results in the field.Robert Sedgewick and the late Philippe Flajolet have drawn from both classical mathematics and computer scienc...

This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a bro...