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

Лас-Вегас — увипадковлений алгоритм, що завжди повертає правильний результат; тобто, він завжди видає правильний результат або повідомляє про збій. Інакше кажучи, Лас-Вегас не грається із правильністю результату, а лише з ресурсами використовними для обчислень. Єдиною відмінністю між запусками на одних вхідних даних є час виконання, який може бути необмеженим, але очікуваний час виконання завжди обмежений. Простим прикладом є увипадковлене швидке сортування, де опірний елемент вибирають випадковим чином, але результат завжди правильний.

Алгоритм Лас-Вегаса представив Ласло Бабай у 1979, у контексті проблеми визначення чи два графи ізоморфні, як сильнішу версію алгоритму Монте-Карло.^[1]^[2]^[3] Алгоритм Лас-Вегаса можна використати в ситуаціях коли число можливих розв'язків порівняно обмежене і перевірка правильності кандидата в розв'язки порівняно проста тоді коли обчислення розв'язку складне.

Ім'я покликається до міста Лас-Вегас у штаті Невада, яке добре відоме своїм ігорним бізнесом.

Приклад

// алгоритм Лас-Вегас
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;

Зв'язок з алгоритмом Монте-Карло

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

Примітки

↑ Ласло Бабай, Monte-Carlo algorithms in graph isomorphism testing [Архівовано 8 грудня 2017 у Wayback Machine.], Université de Montréal, D.M.S. No. 79-10.
↑ Леонід Левін, The Tale of One-way Functions [Архівовано 9 липня 2012 у Archive.is], Problems of Information Transmission, vol. 39 (2003), 92-103.
↑ Dan Grundy, Concepts and Calculation in Cryptography [Архівовано 12 квітня 2016 у Wayback Machine.], University of Kent, Ph.D. thesis, 2008

Read other articles:

Tom Clancy's Rainbow Six 3: Raven Shield

2003 video gameTom Clancy's Rainbow Six 3:Raven ShieldDeveloper(s)Ubi Soft MontrealUbi Soft MilanRed Storm Entertainment[a]Publisher(s)Ubi Soft[b][c]Producer(s)Mathieu FerlandChadi LebbosDesigner(s)Mike McCoyCarl LavoieProgrammer(s)Eric BéginArtist(s)Carol BertrandJosef SyComposer(s)Bill BrownSeriesTom Clancy's Rainbow SixEngineUnreal Engine 2.0Platform(s)Windows, Mac OS X, mobile phoneReleaseWindowsNA: March 18, 2003[2]EU: March 21, 2003[1] Mac OS XE...

Mao Tse-tung: Ruler of Red China

Book by Robert Payne Mao Tse-tung: Ruler of Red China First editionAuthorRobert PayneLanguageEnglishGenreBiographiesPublisherHenry SchumanPublication date1950Media typePrint (hardback book)ISBN978-1-4437-2521-7 Mao Tse-tung: Ruler of Red China is a book written by Robert Payne and published by Henry Schuman, New York in 1950, shortly after Mao Zedong (here his name is transliterated as Mao Tse-tung) came to power.[1] Fifteen years before the Cultural Revolution, Payne anticipated...

Sovana

Disambiguazione – Se stai cercando altri significati, vedi Sovana (disambigua). Questa voce o sezione sull'argomento Toscana è priva o carente di note e riferimenti bibliografici puntuali. Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i sugger...

Inderlok (angkutan cepat Delhi)

Inderlokइन्द्रलोकStasiun angkutan cepat di DelhiKoordinat28°40′24″N 77°10′13″E / 28.673445°N 77.170337°E / 28.673445; 77.170337Jalur Jalur Hijau Jalur MerahJumlah peronSamping (Jalur Merah)Pulau (Jalur Hijau)Jumlah jalur4KonstruksiJenis strukturMelayangParkirTersediaSejarahDibuka3 Oktober 2003 (Jalur Merah)3 April 2010 (Jalur Hijau)Operasi layanan Stasiun sebelumnya Delhi Metro Stasiun berikutnya Terminus Jalur Hi...

Vehicle registration plates of Cuba

Cuba vehicle license plates New Cuban licence plates that use FE-Schrift (since 2013) miniatur miniatur miniatur miniatur miniatur The current vehicle registration plate system of Cuba was introduced in May 2013. Current plates are European standard 520 mm × 110 mm, completely replacing the previous system introduced in 2002.[1] The international vehicle registration code for Cuba is C. New registration system The new system uses a standard manufacturer format, where the al...

Bukan Salah Cinta

Bukan Salah CintaGenre Drama Roman PembuatTripar Multivision PlusBerdasarkanSino ang Maysala?: Mea Culpaoleh Keiko AquinoSutradara Sanjay Verma Irwan Ibon Ranto Chin Bayu Chaki Teguh Prayogi Sridhar Jetty Pemeran Mayang Yudittia Miqdad Addausy Ririn Dwi Ariyanti Krisjiana Baharudin Raquel Katie Larkin Bima Samudra Tessa Kaunang Dini Vitri Ihsan Tarore Pangky Suwito Krisna Murti Wibowo Penggubah lagu temaTiti DJ feat. Agnez MoLagu pembukaHanya Cinta yang Bisa — Titi DJ feat. Agnez MoLagu pe...

Langkawi

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: Langkawi – news · newspapers · books · scholar · JSTOR (September 2021) (Learn how and when to remove this message) For the federal constituency represented in the Dewan Rakyat, see Langkawi (federal constituency). Not to be confused with Lok Kawi. District of ...

Local electoral area

District of local elections in the Republic of Ireland Dublin divided into its eleven local electoral areas, with dots symbolising members of Dublin City Council for each LEA Clane LEA, County Kildare, shown divided into its electoral divisions (EDs). A local electoral area (LEA; Irish: Toghlimistéir Áitiúil)[1] is an electoral area for elections to local authorities in Ireland. All elections use the single transferable vote. The Republic of Ireland is divided into 166 LEAs, with a...

Western world

Countries with an originally European shared culture This article is about the grouping of countries with an originally European shared culture. For other uses, see Western World (disambiguation). Western power and Westerners redirect here. For historical politics in Korea, see Westerners (Korean political faction). For other uses, see Western Power (disambiguation). The Western world as derived from Samuel P. Huntington's 1996 Clash of Civilizations:[1] in light blue are Latin Americ...

Floyd Dominy

Floyd Dominy Floyd Elgin Dominy (December 24, 1909 Adams County, Nebraska – April 20, 2010 Boyce, Virginia) was appointed commissioner of the United States Bureau of Reclamation from May 1, 1959, to December 1, 1969, by Dwight D. Eisenhower.[1] Dominy joined the Bureau in 1946. He was the assistant commissioner from 1957 to 1958. He was responsible for building Glen Canyon Dam and the creation of Lake Powell behind it. He died in Boyce, Virginia, where he had lived since at lea...

Seignory

Lordship granted over an estate English feudalismHarold Sacramentum Fecit Willelmo Duci(Bayeux Tapestry) FiefEcclesiastical fiefCrown landAllodial titleAppanageVassalFeoffmentSeignorySubinfeudationFeoffeeFealtyHomageAffinityFeudal maintenanceFeudal fragmentationBastard feudalismLivery Manorialism Lord of the manorManorial courtManor house (List)DemesneGlebeOverlordLordPeasantSerfdomFree tenant Feudal land tenure in England Land tenureEnglish feudal baronyFeudal baronKnight's feeKnight-service...

Poindexter Dunn

American politician Poindexter DunnMember of the U.S. House of Representativesfrom Arkansas's 1st districtIn officeMarch 4, 1879 – March 3, 1889Preceded byLucien C. GauseSucceeded byWilliam H. CateMember of the Arkansas House of RepresentativesIn office1858 Personal detailsBornPoindexter DunnNovember 3, 1834 (1834-11-03)Wake County, North Carolina, United StatesDiedOctober 12, 1914 (1914-10-13) (aged 79)Texarkana, TexasResting placeRose Hill Cemetery, Tex...

Zone umide italiane della lista di Ramsar

Indice 1 Lombardia 2 Trentino-Alto Adige 3 Veneto 4 Friuli Venezia Giulia 5 Emilia-Romagna 6 Toscana 7 Umbria 8 Lazio 9 Abruzzo 10 Puglia 11 Campania 12 Basilicata 13 Calabria 14 Sicilia 15 Sardegna 16 Note 17 Altri progetti 18 Collegamenti esterni Questa voce o sezione deve essere rivista e aggiornata appena possibile. Commento: L'elenco comprende più voci di quelle designate siti Ramsar che sono 56 (vedi: https://www.ramsar.org/wetland/italy) per un'area complessiva di 73 308 ettari....

LVTP-5裝甲車

LVTP-5 LVTP-5类型兩棲裝甲運兵車原产地美国服役记录服役期间1952-参与战争／衝突1958年黎巴嫩危機越戰生产历史研发者博格華納研发日期1950-1951制造数量1124基本规格重量37.4公噸长度9.04公尺宽度3.57公尺高度2.92公尺操作人数3+34 乘員装甲6-16公厘的鋼質裝甲主武器M1919A4機槍(A、A1)、白朗寧M2重機槍(A1與其他款式)、M240通用機槍(LVTH-6)、M49 24倍徑105mm榴彈炮(LVTH-6)、工蜂四型(LVTP-...

Checkers

Strategy board game For other uses, see Checkers (disambiguation). Draughts redirects here. For other uses, see Draft (disambiguation). CheckersStarting position for American checkers on an 8×8 checkerboard; Black (red) moves first.Years activeat least 5,000GenresBoard gameAbstract strategy gameMind sportPlayers2Setup time<1 minutePlaying timeCasual games usually last 10 to 30 minutes; tournament games last anywhere from about 60 minutes to 3 hours or more.ChanceNoneAge range4+SkillsStrat...

Robert Richardson

Untuk fisikawan, lihat Robert Coleman Richardson. Robert RichardsonRobert Richardson 2019LahirRobert Bridge Richardson27 Agustus 1955 (umur 68)Hyannis, Massachusetts, Amerika SerikatKebangsaanAmerikaPekerjaanSinematograferTahun aktif1982—sekarangGelarASCSuami/istriMonona WaliStephanie MartinAnakKanchan Wali-RichardsonMaya Wali RichardsonBibi Haberstock RichardsonMadeleine Martin RichardsonPenghargaanAcademy Award untuk Sinematografi TerbaikJFK, 1991The Aviator, 2004Hugo, 2011 Robe...

Lorenz Leonard Lindelöf

Finnish mathematician and astronomer Lorenz Lindelöf Lorenz Leonard Lindelöf (13 November 1827, Karvia, Finland – 3 March 1908, Helsinki) was a Finnish mathematician and astronomer. Biography Lindelöf came from a poor family. He learned German and French and studied astronomy and mathematics at the University of Helsinki. He initially specialized in astronomy at the graduate level and was at Pulkovo Observatory in 1855–1856. After his completion of his PhD (Promotierung), Lindelöf fro...

Kyiv Post

English-language newspaper in the capital of Ukraine Kyiv PostType of siteNewsAvailable inEnglishHeadquartersKyiv, UkraineOwnerAdnan Kivan, operating as Businessgroup LLCEditorBohdan Nahaylo, Chief EditorCEOLuc ChénierURLwww.kyivpost.com CommercialYesRegistrationNot requiredLaunchedOctober 18, 1995; 28 years ago (1995-10-18)[1][2]Current statusNews mediaISSN1563-6429 This article's lead section may be too short to adequately summarize the key point...

Tordesillas

Municipality in Castile and León, SpainTordesillasMunicipalitySouthern Tordesillas in September 2012. FlagCoat of armsTordesillasLocation in SpainShow map of Castile and LeónTordesillasTordesillas (Spain)Show map of SpainCoordinates: 41°30′N 5°00′W / 41.500°N 5.000°W / 41.500; -5.000Country SpainAutonomous community Castile and LeónProvinceValladolidComarcaTierra del VinoGovernment • MayorMaría del Milagro Zarzuelo Capellán (PP)Area&...

Wacław Marzantowicz

Polish mathematician (born 1950) Wacław Bolesław Marzantowicz[3]Wacław Bolesław MarzantowiczBorn (1950-06-18) 18 June 1950 (age 74)Poznań, PolandNationalityPolishAlma mater Gdańsk University Adam Mickiewicz University AwardsStefan Banach Prize (2003)Scientific careerFieldsMathematicsInstitutionsAdam Mickiewicz UniversityThesis Lefschetz Numbers of Maps Commuting with an Action of a Group (PhD) 13 May 1977 Habilitation 22 June[1] 1991 Professorship 15 March 2002...