This HTML5 document contains 78 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n19http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n15https://books.google.com/
n20https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n10http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n22http://algnotes.info/on/background/probabilistic-method/method-of-conditional-probabilities/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Probabilistic_method
dbo:wikiPageWikiLink
dbr:Method_of_conditional_probabilities
Subject Item
dbr:Method_of_conditional_probabilities
rdf:type
yago:Indication106797169 yago:Algorithm105847438 yago:Act100030358 yago:WikicatProbabilisticArguments yago:WikicatApproximationAlgorithms yago:Communication100033020 yago:Activity100407535 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Procedure101023820 yago:Rule105846932 yago:Abstraction100002137 yago:Argument106648724 yago:Event100029378 yago:Evidence106643408
rdfs:label
Method of conditional probabilities Метод условных вероятностей
rdfs:comment
In mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they work by showing that a random object, chosen from some probability distribution, has the desired properties with positive probability. Consequently, they are nonconstructive — they don't explicitly describe an efficient method for computing the desired objects. В математике для доказательства существования математических объектов с некоторыми комбинаторными свойствами используется вероятностный метод, в котором показывается, что случайный объект, выбранный из некоторой вероятностной выборки, имеет требуемое свойство с положительной вероятностью. Следовательно, эти доказательства существования неконструктивны — они не описывают явно метод построения или вычисления таких объектов. Метод частично уместен в контексте вероятностного округления (которое использует вероятностный метод для разработки аппроксимационных алгоритмов).
foaf:depiction
n10:Method_of_conditional_probabilities.png
dct:subject
dbc:Approximation_algorithms dbc:Probabilistic_arguments
dbo:wikiPageID
26944505
dbo:wikiPageRevisionID
1087497644
dbo:wikiPageWikiLink
dbr:Max_cut dbc:Probabilistic_arguments dbr:Independent_set_(graph_theory) dbr:Cambridge_University_Press dbc:Approximation_algorithms dbr:Mathematics dbr:Polynomial_time dbr:Approximation_algorithm dbr:Graph_(discrete_mathematics) dbr:Journal_of_Computer_and_System_Sciences dbr:Springer_Verlag dbr:Deterministic_algorithm dbr:Maximum_cut dbr:Convex_function dbr:Expected_value dbr:Turán's_theorem dbr:Probabilistic_method dbr:Computer_science dbr:Nonconstructive_proof n19:Method_of_conditional_probabilities.png dbr:Derandomization dbr:Randomized_rounding
dbo:wikiPageExternalLink
n15:books%3Fid=Kz0B0KkwfVAC n15:books%3Fid=q3lUjheWiMoC&q=%22method+of+conditional+probabilities%22 n15:books%3Fid=EILqAmzKgYIC&q=%22method+of+conditional%22 n15:books%3Fid=QKVY4mDivBEC&q=%22method+of+conditional+probabilities%22 n22:
owl:sameAs
yago-res:Method_of_conditional_probabilities wikidata:Q6823704 freebase:m.0bmdhx3 n20:4rz3V dbpedia-ru:Метод_условных_вероятностей
dbp:wikiPageUsesTemplate
dbt:No_footnotes dbt:Harv dbt:Citation dbt:Cite_book dbt:ISBN
dbo:thumbnail
n10:Method_of_conditional_probabilities.png?width=300
dbo:abstract
In mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they work by showing that a random object, chosen from some probability distribution, has the desired properties with positive probability. Consequently, they are nonconstructive — they don't explicitly describe an efficient method for computing the desired objects. The method of conditional probabilities, converts such a proof, in a "very precise sense", into an efficient deterministic algorithm, one that is guaranteed to compute an object with the desired properties. That is, the method derandomizes the proof. The basic idea is to replace each random choice in a random experiment by a deterministic choice, so as to keep the conditional probability of failure, given the choices so far, below 1. The method is particularly relevant in the context of randomized rounding (which uses the probabilistic method to design approximation algorithms). When applying the method of conditional probabilities, the technical term pessimistic estimator refers to a quantity used in place of the true conditional probability (or conditional expectation) underlying the proof. В математике для доказательства существования математических объектов с некоторыми комбинаторными свойствами используется вероятностный метод, в котором показывается, что случайный объект, выбранный из некоторой вероятностной выборки, имеет требуемое свойство с положительной вероятностью. Следовательно, эти доказательства существования неконструктивны — они не описывают явно метод построения или вычисления таких объектов. Метод условных вероятностей преобразует такое доказательство во «вполне точном смысле» в эффективный детерминированный алгоритм, который гарантирует обнаружение объекта с желаемыми свойствами. То есть метод дерандомизирует доказательство. Основная идея — заменить каждый случайный выбор в случайном эксперименте детерминированным выбором таким образом, чтобы сохранить условное математическое ожидание неудачи, обусловленной выбором, меньшим 1. Метод частично уместен в контексте вероятностного округления (которое использует вероятностный метод для разработки аппроксимационных алгоритмов). Когда применяется метод условных вероятностей, технический термин пессимистический оценщик относится к величинам, использованным вместо условной вероятности (или условного математического ожидания) исходного доказательства.
prov:wasDerivedFrom
wikipedia-en:Method_of_conditional_probabilities?oldid=1087497644&ns=0
dbo:wikiPageLength
21158
foaf:isPrimaryTopicOf
wikipedia-en:Method_of_conditional_probabilities
Subject Item
dbr:Maximum_cut
dbo:wikiPageWikiLink
dbr:Method_of_conditional_probabilities
Subject Item
dbr:Berlekamp_switching_game
dbo:wikiPageWikiLink
dbr:Method_of_conditional_probabilities
Subject Item
dbr:Maximum_satisfiability_problem
dbo:wikiPageWikiLink
dbr:Method_of_conditional_probabilities
Subject Item
dbr:Karloff–Zwick_algorithm
dbo:wikiPageWikiLink
dbr:Method_of_conditional_probabilities
Subject Item
dbr:Linear_programming_relaxation
dbo:wikiPageWikiLink
dbr:Method_of_conditional_probabilities
Subject Item
dbr:Randomized_algorithm
dbo:wikiPageWikiLink
dbr:Method_of_conditional_probabilities
Subject Item
dbr:Randomized_rounding
dbo:wikiPageWikiLink
dbr:Method_of_conditional_probabilities
Subject Item
dbr:Pessimistic_estimator
dbo:wikiPageWikiLink
dbr:Method_of_conditional_probabilities
dbo:wikiPageRedirects
dbr:Method_of_conditional_probabilities
Subject Item
wikipedia-en:Method_of_conditional_probabilities
foaf:primaryTopic
dbr:Method_of_conditional_probabilities