Content deleted Content added
Definition of Las Vegas. |
m Maintain {{WPBS}}: 4 WikiProject templates. Remove 1 deprecated parameter: field. Tag: |
||
| (11 intermediate revisions by 9 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=Start|
{{WikiProject Computing|importance=}}
{{WikiProject Computer science|importance=mid}}
{{WikiProject Statistics|importance=low}}
{{WikiProject Mathematics|importance=low}}
}}
The following is given as the definition of Monte Carlo and Las Vegas by Babai, Cooperman, Finkelstein, Luks and Seress in ''Fast Monte Carlo Algorithms for Permutation Groups'':
Line 9 ⟶ 15:
polytime bounded Las Vegas algorithms or with expected polynomial time randomized decision algorithms,
giving the same class, but by slightly different machinations. -[[User:Ozga|Ozga]] 03:23, 5 April 2006 (UTC)
== Term Etymology? ==
I added a reference to the NIST [http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures] definition, although I'm not sure that's the best reference. Does anybody have any idea from where the term originated?
BTW, the NIST definition agrees a little more with "gambling with resources" in that for each run, <em>for the same problem instance</em>, the runtime resource requirements (time/space/etc) will possibly be different. But all programs, etc "gamble with resources", always assuming that there will be enough resources to solve any particular problem instance (and sometimes failing). So I agree, probably ought to consider better wording. [[User:Root4(one)|Root4(one)]] 04:58, 12 January 2007 (UTC)
== Want more examples ==
I should like to see more examples of Las Vegas algorithms. For instance, is [[bogosort]] a Las Vegas algorithm? Bogosort is very random but is supposed to ''eventually'' give the right solution. Right now, there is only one example of a Las Vegas algorithm in the article, and it isn't even particularly well-explained. I'm sure that adding more examples will make this article far more accessible to laymen. [[User:Purpy Pupple|Purpy Pupple]] ([[User talk:Purpy Pupple|talk]]) 04:43, 6 December 2010 (UTC)
:Yes, bogosort is a simple example of a Las Vegas algorithm. You might want to create a new section with examples. Please, be [[WP:BOLD]] and edit the relevant part(s). [[User:Hermel|Hermel]] ([[User talk:Hermel|talk]])
| |||