| dbo:abstract
|
- In theoretical computer science, the algorithmic Lovász local lemma gives an algorithmic way of constructing objects that obey a system of constraints with limited dependence. Given a finite set of bad events {A1, ..., An} in a probability space with limited dependence amongst the Ais and with specific bounds on their respective probabilities, the Lovász local lemma proves that with non-zero probability all of these events can be avoided. However, the lemma is non-constructive in that it does not provide any insight on how to avoid the bad events. If the events {A1, ..., An} are determined by a finite collection of mutually independent random variables, a simple Las Vegas algorithm with expected polynomial runtime proposed by and Gábor Tardos can compute an assignment to the random variables such that all events are avoided. (en)
- Алгоритмическая локальная лемма Ловаcа — лемма в теоретической информатике, позволяющая конструировать объекты, подчиняющиеся определённым ограничениям. Из локальной леммы Ловаса следует, что вероятность того, что ни одно событие из некоторого множества «плохих» событий не произойдёт, строго положительна, если эти события удовлетворяют некоторым дополнительным ограничениям. В то же время лемма неконструктивна и не позволяет явным образом конструировать примеры объектов, для которых эти события не наступают. В случае когда указанные события определяются конечным набором независимых друг от друга случайных величин, разработанный учёными и алгоритм типа «Лас-Вегас» с полиномиальным временем работы позволяет в явном виде вычислить некоторый набор значений этих величин, для которого не выполняется ни одно из рассматриваемых случайных событий. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 15299 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In theoretical computer science, the algorithmic Lovász local lemma gives an algorithmic way of constructing objects that obey a system of constraints with limited dependence. Given a finite set of bad events {A1, ..., An} in a probability space with limited dependence amongst the Ais and with specific bounds on their respective probabilities, the Lovász local lemma proves that with non-zero probability all of these events can be avoided. However, the lemma is non-constructive in that it does not provide any insight on how to avoid the bad events. (en)
- Алгоритмическая локальная лемма Ловаcа — лемма в теоретической информатике, позволяющая конструировать объекты, подчиняющиеся определённым ограничениям. Из локальной леммы Ловаса следует, что вероятность того, что ни одно событие из некоторого множества «плохих» событий не произойдёт, строго положительна, если эти события удовлетворяют некоторым дополнительным ограничениям. В то же время лемма неконструктивна и не позволяет явным образом конструировать примеры объектов, для которых эти события не наступают. В случае когда указанные события определяются конечным набором независимых друг от друга случайных величин, разработанный учёными и алгоритм типа «Лас-Вегас» с полиномиальным временем работы позволяет в явном виде вычислить некоторый набор значений этих величин, для которого не выпол (ru)
|
| rdfs:label
|
- Algorithmic Lovász local lemma (en)
- Алгоритмическая локальная лемма Ловаса (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
