Лас-Вегас (алгоритм)

Лас-Вегас — вид вероятностного алгоритма.

Идея алгоритма Лас-Вегас состоит в следующем. Если у нас есть некий вероятностный алгоритм $A$ , который с определенной вероятностью даёт верный результат, и существует возможность алгоритмически проверить результат алгоритма $A$ на корректность (скажем, с помощью алгоритма $K$ ), то можно выполнять алгоритм $A$ до тех пор, пока проверка не установит, что результат верен:

Выполнить алгоритм  $A$  с результатом  $r$  до тех пор, пока  $K(r)$  не будет истиной.

Название этому принципу было дано с одной стороны как намек на метод Монте-Карло. С другой стороны это название намекает на «метод выигрыша в казино», которое схоже с процессом работы алгоритма — «если я буду играть ещё и ещё, я когда-нибудь обязательно выиграю».

Следует заметить, что алгоритм Лас-Вегаса гарантирует получение правильного результата. Алгоритм работает за конечное, но не детерминированное время. Можно указать только вероятность получения результата за заданное время.

Примеры

Данный псевдокод можно назвать примером алгоритма Лас-Вегас:

function lasvegas()
begin
    var a := random();
    
    if(verify(a) = true) then
        return a;
end

Примером алгоритма, относящегося к классу Лас-Вегас, является алгоритм сортировки Bogosort: данные, которые нужно отсортировать, перемешиваются случайным образом, и затем проверяется, оказались ли они расположенными в нужном порядке. В случае неудачи перемешивание многократно повторяется вплоть до достижения желаемого порядка.

Связь с алгоритмами Монте-Карло

Пусть ${\mathcal {A}}$ - алгоритм Лас-Вегаса с ожидаемой временной сложностью $f(n)$ , где $n$ - длина входа. Если остановить ${\mathcal {A}}$ после $\alpha \cdot f(n)$ шагов ( $0<\alpha <1$ ), то мы получим алгоритм Монте-Карло ${\mathcal {B}}$ с вероятностью ошибки в $1/\alpha$ . Для доказательства теоремы рассмотрим $x$ как вход длины $n$ и $T$ - случайную переменную, описывающую временную сложность ${\mathcal {A}}$ . Тогда математическое ожидание $\mathbb {E} [T]\leqslant f(n)$ и согласно неравенству Маркова: $\mathbb {P} r[T\geqslant \alpha \cdot f(n)]\leqslant \mathbb {P} r[T\geqslant \alpha \cdot \mathbb {E} [T]]\leqslant 1/\alpha$ .

Ссылки

Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999
"Las Vegas algorithm" / Dictionary of Algorithms and Data Structures, Paul E. Black, ed., U.S. NIST. 17 July 2006. (англ.)

В статье не хватает ссылок на источники (см. рекомендации по поиску).

Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (22 августа 2018)

Это заготовка статьи по математике. Помогите Википедии, дополнив её.

Read other articles:

Bagas Godang

Bagas Godang di Huta Godang, Ulu Pungkut, Mandailing Natal. Bagas Godang di Panyabungan Tonga, Panyabungan, Mandailing Natal. Bagas Godang (dalam bahasa Batak Mandailing) adalah bentuk rumah tradisional atau arsitektur tradisional masyarakat Batak Mandailing & Batak Angkola. Rumah besar ini dahulu sebagai tempat tinggal atau tempat istirahat raja.[1] Kompleks Bagas Godang di lengkapi dengan Sopo Godang dan Alaman Bolak.[2] Defenisi Bagas Godang merupakan rumah be...

Indonesia Creator Economy

Indonesia Creators Economy (ICE)JenisAnak perusahaanPendahuluIDN Creator NetworkDidirikan8 Maret 2017; 6 tahun lalu (2017-03-08) (sebagai IDN Creator Network)8 Maret 2022; 23 bulan lalu (2022-03-08) (sebagai Indonesia Creator Economy)Ditutup08 Maret 2022 (2022-03-08) (sebagai IDN Creator Network)KantorpusatJakarta, IndonesiaWilayah operasiIndonesiaPemilikIDN MediaSitus webhttps://www.ice.id/ Indonesia Creators Economy (ICE) merupakan marketplace kreator konten dari Indonesia mi...

Créteil

CréteilNegaraPrancisArondisemenCréteilKantonIbukota 3 kantonAntarkomuneCommunauté d'agglomération Plaine Centrale du Val-de-MarneKode INSEE/pos94028 (ex 75028) 94028 (ex 75028) / Gereja Saint-Christophe, di komune Créteil. Créteil merupakan sebuah komune di pinggiran tenggara Paris, Prancis. Terletak 11.5 km (7.1 mil) dari pusat kota Paris. Créteil adalah préfecture (ibu kota dari département Val-de-Marne, juga ibu kota Arondisemen Créteil. Kota ini, lainnya, adalah ibu k...

Suyoso Karsono

Suyoso KarsonoLahir(1921-07-18)18 Juli 1921 Tanjungpandan, Kepulauan Bangka Belitung, Hindia BelandaMeninggal26 Oktober 1984(1984-10-26) (umur 63)Jakarta, IndonesiaPekerjaanPemilik sekaligus pendiri dari Irama Record, didirikan 1952Suami/istriBibit Suwarto Karsono (Almarhumah) Suyoso Karsono (18 Juli 1921 – 26 Oktober 1984) atau yang lebih dikenal dengan panggilan Mas Yos adalah pemilik perusahaan musik Irama Record, yang terkenal pada era 60-an. Namanya tidak bisa dipis...

Magistrates Court of the Australian Capital Territory

Magistrates Court of the Australian Capital TerritoryThe Magistrates Court Building located in Civic, Canberra, completed in 1996.35°16′49″S 149°07′37″E / 35.280385°S 149.127023°E / -35.280385; 149.127023Established25 November 1930 (1930-11-25) (as the Court of Petty Sessions)[1]1 February 1986 (1986-02-01) (as the Magistrates Court)[1]JurisdictionAustralian Capital TerritoryJervis Bay TerritoryAustralian Antar...

Laura & Paola

Laura & PaolaPaeseItalia Anno2016 Generevarietà, musicale Edizioni1 Puntate3 Lingua originaleitaliano RealizzazioneConduttoreLaura PausiniPaola Cortellesi IdeatoreLaura Pausini, Paola Cortellesi, Furio Andreotti RegiaCristiano D'Alisera Autoriscritto da Paolo Biamonte, Giorgio Cappozzo e Ennio Meloni Casa di produzioneBallandi MultimediaF&P Group Rete televisivaRai 1 Modifica dati su Wikidata · Manuale Laura & Paola è stato un programma televisivo musicale con la ...

Perjanjian Gencatan Senjata 1949

Perbedaan utama antara usulan pembagian 1947 dan garis gencatan senjata 1949. Perjanjian Gencatan Senjata 1949 adalah perjanjian yang ditandatangani pada tahun 1949 antara Israel dengan Mesir,[1] Lebanon,[2] Yordania,[3] dan Suriah.[4] Persetujuan ini mengakhiri perang Arab-Israel 1948, dan menentukan batas wilayah sementara yang dikenal sebagai Garis Hijau. Garis ini tetap berlaku hingga meletusnya Perang Enam Hari tahun 1967. Referensi ^ Egypt Israel Diarsipk...

Stellarium (software)

Open-source planetarium This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Stellarium software – news · newspapers · books · scholar · JSTOR (April 2018) (Learn how and when to remove this template message) StellariumStellarium 0.12.0 running on Ubuntu LinuxOriginal author(s)Fabien ChéreauDeveloper(s)Alex...

Catacomb Abyss

1992 video game 1992 video gameCatacomb AbyssCatacomb Abyss title screenDeveloper(s)SoftdiskPublisher(s)SoftdiskDesigner(s)Greg MaloneProgrammer(s)Nolan MartinMichael MaynardJames T. RowArtist(s)Adrian CarmackJerry K. JonesCarol LuddenSteven MainesEnginePrototype of Wolfenstein 3D enginePlatform(s) MS-DOS Microsoft Windows MacOS Release November 1992 MS-DOS November 1992 Catacombs Pack Microsoft Windows, OS X March 2013 Genre(s)First-person shooterMode(s)Single-player Catacomb Abyss (also kno...

List of androgens and anabolic steroids

For chemically related esters, see list of androgen esters. Testosterone. Steroid ring system. This article needs attention from an expert in Chemicals. The specific problem is: chemical names need verification and correction as necessary. WikiProject Chemicals may be able to help recruit an expert. (September 2016) This is a list of androgens/anabolic steroids (AAS) or testosterone derivatives. Androgen esters are mostly not included in this list. The major classes of testosterone derivativ...

Bolaños Municipality

Municipality in Jalisco, MexicoBolañosMunicipality Coat of armsLocation within the state of JaliscoBolañosLocation in MexicoShow map of JaliscoBolañosBolaños (Mexico)Show map of MexicoCoordinates: 21°49′50″N 103°46′50″W / 21.83056°N 103.78056°W / 21.83056; -103.78056Country MexicoState JaliscoMunicipal seatBolañosFounded1548 (Toribio de Bolaños)Area • Total866.5 km2 (334.6 sq mi) • Seat0.28 km2 (0....

Consubstantiation

Christian theological doctrine Not to be confused with Consubstantiality. Part of a series on theEucharist Lord's Supper Communion Elements Bread Wine Ritual and liturgy Divine Liturgy Holy Qurobo Holy Qurbana Divine Service Mass Requiem Solemn Consecration/Anaphora Epiclesis Words of Institution Anamnesis Practices and customs Closed and open table Communion under both kinds Adoration Discipline Thanksgiving Reserved sacrament Feast of Corpus Christi First Communion Infant communion Viaticum...

Outline of China

Overview of and topical guide to China The Flag of the People's Republic of ChinaThe National Emblem of the People's Republic of China An enlargeable map of the People's Republic of China The following outline is provided as an overview of and topical guide to China: The People's Republic of China is the most extensive country in East Asia and the third most extensive country in the world.[1][note 1] With a population of over 1,400,000,000, it is the second most populous count...

Matthaios Paranikas

Matthaios ParanikasMatthaios Paranikas (sitting) with some teachers and graduates of the Evangelical School of Smyrna in 1878Born1832Vitsa, Janina VilayetDied1914ConstantinopleNationalityGreekEducationZosimaia School, University of Athens, University of MunichOccupation(s)Scholar, philologist teacher and writer Matthaios K. Paranikas (Greek: Ματθαίος Παρανίκας; 1832–1914) was an ethnically Greek scholar, philologist teacher and writer of the 19th and early 20th centuries wh...

April 2007 Yazidi massacre

Massacre of Yazidis April 2007 Yazidi massacrePart of the Iraqi civil war (2006–2008)Al-Hamdaniya District, Nineveh GovernorateLocationMosul, Al-Hamdaniya District, IraqDateApril 22, 2007 2:00pm (UTC+03:00)TargetYazidisAttack typeMassacre, Ethnic violenceDeaths23PerpetratorsUnknown vteList of bombings during the Iraq War‡ indicates attacks resulting in over 100 deaths § indicates the deadliest attack in the Iraq WarThis list only includes major attacks. 2003 1st Baghdad 2nd Baghdad Najaf...

QBZ-95

Senapan otomatis Tipe 95 Senapan QBZ-95 Jenis Senapan serbu Negara asal Tiongkok Sejarah pemakaian Masa penggunaan 1997–sekarang Sejarah produksi Perancang Duo Yingxian Tahun 1989–1991 Produsen Norinco Diproduksi 1995–2019 (de jure) Spesifikasi Berat 3,27 kg Panjang 745 mm Peluru 5,8×42mm DBP87 (QBZ-95)5,8×42mm DBP10 (QBZ-95-1)5,56×45mm NATO (QBZ-97) Mekanisme Operasi gas, baut berputar Rata² tembakan 650 peluru/menit Kecepatan peluru 930 m/s (3.051&#...

1950 United Kingdom general election

1950 United Kingdom general election ← 1945 23 February 1950 1951 → ← outgoing memberselected members →All 625 seats in the House of Commons313 seats needed for a majorityOpinion pollsTurnout83.9% 11.1% First party Second party Third party Leader Clement Attlee Winston Churchill Clement Davies Party Labour Conservative Liberal Leader since 25 October 1935 9 October 1940 2 August 1945 Leader's seat Walthamstow West[a...

اضطرابات الأهواز 2005

اضطرابات اهواز 2005[1][2] أو احتجاجات اهواز 15 أبريل[3] كانت أعمال شغب عنيفة بدأها عرب إيران في مدينة الأهواز في جنوب غرب المحافظة الإيرانية خوزستان. وقد اندلعت الاضطرابات في 15 أبريل 2005، واستمرت لمدة 4 أيام. في البداية، ذكرت وزارة الداخلية الإيرانية أن شخصًا واحدًا ف...

اللواء 2 حرس حدود (اليمن)

هذه المقالة بحاجة لصندوق معلومات. فضلًا ساعد في تحسين هذه المقالة بإضافة صندوق معلومات مخصص إليها. يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2019) اللواء 2 ...

History of Oaxaca

In the Central Valley region of the Southern Mexican state of Oaxaca archeologists discovered evidence of historic settlements. Aztecs from Tenochtitlan on the volcanic plateau to the North around what today is Mexico City first arrived in this region around 1250 AD establishing military rule in the 15th century until the arrival of the Spanish. After the fall of Tenochtitlan, the Spanish took over Oaxaca which led to the eventual decrease of the Native population and the increase in African...