دانلود کتاب تست مشخصات -مشکلات و تکنیک ها

Property testing is an emerging area that aims for algorithms that decide whether the input satisfies a predetermined property in sublinear time in the input size, or even in constant time, that is, independent of the input size. Of course, we cannot correctly solve problems in sublinear time without reading the whole input; so, we need several assumptions or compromises. First, we assume that query access to the input is available through which we can get a small part of the input in constant time. Second, we compromise with approximate decisions; that is, we only aim for algorithms that distinguish inputs satisfying the predetermined property from those that are far from satisfying it. Such algorithms are called testers for the property, and it has been shown in the past few decades that there are sublinear-time testers for many properties on various objects such as strings, graphs, and functions. The first goal of this book is to introduce important results and techniques in property testing to a broad audience. To design efficient testers and show their correctness, we will make use of a variety of connections to other areas of mathematics and computer science, such as combinatorics, graph theory, matroid theory, computational learning theory, and coding theory. We hope that the reader appreciates how beautifully these connections are employed for the purpose of designing and analyzing property testers.