國立虎尾科技大學 |

Property Testing = Problems and Techniques /

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Property Testing/ by Arnab Bhattacharyya, Yuichi Yoshida.
其他題名:	Problems and Techniques /
作者:	Bhattacharyya, Arnab.
其他作者:	Yoshida, Yuichi.
面頁冊數:	XIX, 427 p. 13 illus.online resource. :
Contained By:	Springer Nature eBook
標題:	Design and Analysis of Algorithms. -
電子資源:	https://doi.org/10.1007/978-981-16-8622-1
ISBN:	9789811686221

Property Testing = Problems and Techniques /
Bhattacharyya, Arnab.

Property TestingProblems and Techniques /[electronic resource] :by Arnab Bhattacharyya, Yuichi Yoshida. - 1st ed. 2022. - XIX, 427 p. 13 illus.online resource.

Chapter 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.

This 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.

ISBN: 9789811686221

Standard No.: 10.1007/978-981-16-8622-1doiSubjects--Topical Terms:

1365721
Design and Analysis of Algorithms.

LC Class. No.: QA9.58

Dewey Class. No.: 005.13

Property Testing = Problems and Techniques /
LDR:02951nam a22003975i 4500 001 1089889
003 DE-He213
005 20220711074437.0
007 cr nn 008mamaa
008 221228s2022 si | s |||| 0|eng d
020 $a 9789811686221 $9 978-981-16-8622-1
024 7 $a 10.1007/978-981-16-8622-1 $2 doi
035 $a 978-981-16-8622-1
050 4 $a QA9.58
072 7 $a UYA $2 bicssc
072 7 $a COM051300 $2 bisacsh
072 7 $a UYA $2 thema
082 0 4 $a 005.13 $2 23
100 1 $a Bhattacharyya, Arnab. $e author. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 1397186
245 1 0 $a Property Testing $h [electronic resource] : $b Problems and Techniques / $c by Arnab Bhattacharyya, Yuichi Yoshida.
250 $a 1st ed. 2022.
264 1 $a Singapore : $b Springer Nature Singapore : $b Imprint: Springer, $c 2022.
300 $a XIX, 427 p. 13 illus. $b online resource.
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
347 $a text file $b PDF $2 rda
505 0 $a Chapter 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 $a This 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 1 4 $a Design and Analysis of Algorithms. $3 1365721
650 0 $a Algorithms. $3 527865
700 1 $a Yoshida, Yuichi. $e author. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 1397187
710 2 $a SpringerLink (Online service) $3 593884
773 0 $t Springer Nature eBook
776 0 8 $i Printed edition: $z 9789811686214
776 0 8 $i Printed edition: $z 9789811686238
776 0 8 $i Printed edition: $z 9789811686245
856 4 0 $u https://doi.org/10.1007/978-981-16-8622-1
912 $a ZDB-2-SCS
912 $a ZDB-2-SXCS
950 $a Computer Science (SpringerNature-11645)
950 $a Computer Science (R0) (SpringerNature-43710)