000 | 03341nam a22004935i 4500 | ||
---|---|---|---|
001 | 978-981-16-8622-1 | ||
003 | DE-He213 | ||
005 | 20240423125427.0 | ||
007 | cr nn 008mamaa | ||
008 | 220308s2022 si | s |||| 0|eng d | ||
020 |
_a9789811686221 _9978-981-16-8622-1 |
||
024 | 7 |
_a10.1007/978-981-16-8622-1 _2doi |
|
050 | 4 | _aQA9.58 | |
072 | 7 |
_aUYA _2bicssc |
|
072 | 7 |
_aCOM051300 _2bisacsh |
|
072 | 7 |
_aUYA _2thema |
|
082 | 0 | 4 |
_a005.13 _223 |
100 | 1 |
_aBhattacharyya, Arnab. _eauthor. _4aut _4http://id.loc.gov/vocabulary/relators/aut |
|
245 | 1 | 0 |
_aProperty Testing _h[electronic resource] : _bProblems and Techniques / _cby Arnab Bhattacharyya, Yuichi Yoshida. |
250 | _a1st ed. 2022. | ||
264 | 1 |
_aSingapore : _bSpringer Nature Singapore : _bImprint: Springer, _c2022. |
|
300 |
_aXIX, 427 p. 13 illus. _bonline resource. |
||
336 |
_atext _btxt _2rdacontent |
||
337 |
_acomputer _bc _2rdamedia |
||
338 |
_aonline resource _bcr _2rdacarrier |
||
347 |
_atext file _bPDF _2rda |
||
505 | 0 | _aChapter 1: Introduction -- Chapter 2: Basic Techniques -- Chapter 3: Strings -- Chapter 4: Graphs in the Adjacency Metrix Model -- Chapter 5: Graphs in the Bounded-Degree Model -- Chapter 6: Functions over Hypercubes -- Chapter 7: Massively Parameterized Model -- Chapter 8: Vectors and Matrices over the Reals -- Chapter 9: Graphs in the Adjacency Matrix Model -- Chapter 10: Graphs in the Bounded-Degree Model -- Chapter 11: Affine-Invariant Properties of Functions -- Chapter 12: Linear Properties of Functions -- Chapter 13: Massively Parameterized Model. | |
520 | _aThis book introduces important results and techniques in property testing, where the goal is to design algorithms that decide whether their input satisfies a predetermined property in sublinear time, or even in constant time – that is, time is independent of the input size. This book consists of three parts. The first part provides an introduction to the foundations of property testing. The second part studies the testing of specific properties on strings, graphs, functions, and constraint satisfaction problems. Vectors and matrices over real numbers are also covered. The third part is more advanced and explains general conditions, including full characterizations, under which properties are constant-query testable. The first and second parts of the book are intended for first-year graduate students in computer science. They should also be accessible to undergraduate students with the adequate background. The third part can be used by researchers or ambitious graduate students who want to gain a deeper theoretical understanding of property testing. | ||
650 | 0 | _aAlgorithms. | |
650 | 1 | 4 | _aDesign and Analysis of Algorithms. |
650 | 2 | 4 | _aAlgorithms. |
700 | 1 |
_aYoshida, Yuichi. _eauthor. _4aut _4http://id.loc.gov/vocabulary/relators/aut |
|
710 | 2 | _aSpringerLink (Online service) | |
773 | 0 | _tSpringer Nature eBook | |
776 | 0 | 8 |
_iPrinted edition: _z9789811686214 |
776 | 0 | 8 |
_iPrinted edition: _z9789811686238 |
776 | 0 | 8 |
_iPrinted edition: _z9789811686245 |
856 | 4 | 0 | _uhttps://doi.org/10.1007/978-981-16-8622-1 |
912 | _aZDB-2-SCS | ||
912 | _aZDB-2-SXCS | ||
942 | _cSPRINGER | ||
999 |
_c177813 _d177813 |