In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if some combinatorial structure S (such as a graph or a boolean function) satisfies some property P, or is "far" from having this property (meaning an ε-fraction of the representation of S need be modified in order to make S satisfy P), using only a small number of "local" queries to the object.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - اختبار الخاصية (ar)
- Test de propriété (fr)
- Property testing (en)
|
| rdfs:comment
| - En informatique théorique, un test de propriété (ou property testing en anglais) est un test probabiliste qui a pour objectif de déterminer si un objet donné, par exemple un graphe ou une fonction, possède une propriété fixée ou bien s'il est « loin » de l'avoir. Ces algorithmes ont l'avantage d'être très rapides. Les testeurs de propriété sont notamment utiles pour tester que des grands graphes ont certaines propriétés. (fr)
- في علوم الحاسوب، خوارزمية اختبار الخاصية هي الخوارزمية التي يكون فيها تعقيد تساؤلها لمدخلاتها أصغر بكثير من حجم المشكلة. وعادة ما يتم استخدام خوارزميات اختبار الخاصية لتقرر ما إذا كان بعض الكينونات الرياضية (مثل أو ) لديها خاصية «عالمية»، أو أنها «بعيدة» عن امتلاك هذه الخاصية، وذلك باستخدام عدد قليل من التساؤلات «المحلية» للكائن.فعلى سبيل المثال، التالية تُدخل خوارزمية تعقيد تساؤلها مستقل عن الحجم (لثابت تعسفي ε > 0): "وبالنظر إلى الرسم البياني G على رؤوس n، قرر ما إذا كان G مخطط ثنائي، أواذا كان لا يصلح لـ G أن تكون مخطط ثنائي حتى بعد إزالة مجموعة فرعية تعسفية في الأكثر من حواف G" (ar)
- In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if some combinatorial structure S (such as a graph or a boolean function) satisfies some property P, or is "far" from having this property (meaning an ε-fraction of the representation of S need be modified in order to make S satisfy P), using only a small number of "local" queries to the object. (en)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - في علوم الحاسوب، خوارزمية اختبار الخاصية هي الخوارزمية التي يكون فيها تعقيد تساؤلها لمدخلاتها أصغر بكثير من حجم المشكلة. وعادة ما يتم استخدام خوارزميات اختبار الخاصية لتقرر ما إذا كان بعض الكينونات الرياضية (مثل أو ) لديها خاصية «عالمية»، أو أنها «بعيدة» عن امتلاك هذه الخاصية، وذلك باستخدام عدد قليل من التساؤلات «المحلية» للكائن.فعلى سبيل المثال، التالية تُدخل خوارزمية تعقيد تساؤلها مستقل عن الحجم (لثابت تعسفي ε > 0): "وبالنظر إلى الرسم البياني G على رؤوس n، قرر ما إذا كان G مخطط ثنائي، أواذا كان لا يصلح لـ G أن تكون مخطط ثنائي حتى بعد إزالة مجموعة فرعية تعسفية في الأكثر من حواف G" خوارزميات اختبار الخاصية مهمة في نظرية . (ar)
- In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if some combinatorial structure S (such as a graph or a boolean function) satisfies some property P, or is "far" from having this property (meaning an ε-fraction of the representation of S need be modified in order to make S satisfy P), using only a small number of "local" queries to the object. For example, the following promise problem admits an algorithm whose query complexity is independent of the instance size (for an arbitrary constant ε > 0): "Given a graph G on n vertices, decide if G is bipartite, or G cannot be made bipartite even after removing an arbitrary subset of at most edges of G." Property testing algorithms are central to the definition of probabilistically checkable proofs, as a probabilistically checkable proof is essentially a proof that can be verified by a property testing algorithm. (en)
- En informatique théorique, un test de propriété (ou property testing en anglais) est un test probabiliste qui a pour objectif de déterminer si un objet donné, par exemple un graphe ou une fonction, possède une propriété fixée ou bien s'il est « loin » de l'avoir. Ces algorithmes ont l'avantage d'être très rapides. Les testeurs de propriété sont notamment utiles pour tester que des grands graphes ont certaines propriétés. (fr)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is differentFrom
of | |
| is Link from a Wikipage to another Wikipage
of | |
| is known for
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)