“Minesweeper” – ne toks paprastas, kaip atrodo

 (13)
Tariamai paprastas žaidimas “Minesweeper”, esantis beveik visuose kompiuteriuose, galėtų būti didžiausia matematikams pateikta metų mįslė. Nors kai kurie žmonės valandų valandas praleido bežaisdami šį žaidimą, matematikai vargsta su didesne žaidimo versija. Ši užduotis yra tokia sunki, kad universitetas netgi pasiūlė milijoną dolerių išsprendusiam galvosūkį.
O sumaištis prasidėjo dėl brito Richardo Kaye, dirbančio Birmingemo universitete. Mokslininką domina matematinį prieskonį turintys žaidimai, todėl jis susidomėjo “Minesweeper” žaidimu ir pradėjo ieškoti jame gilesnės minties.

“Minesweeper”, komplektuojamas su “Windows” operacinėmis sistemomis, yra žaidimas, kuriame žaidėjas turi susiprasti, kuriuose žaidimo langeliuose yra minos. Kiekviename “neužminuotame” langelyje būna arba skaičius, žymintis šalia esančių minų kiekį, arba tuščias plotas.

Po kelių savaičių nuolatinio žaidimo profesorius R.Kaye suprato, kad jei “Minesweeper” būtų žaidžiamas kur kas didesniame lauke, tuomet jį matematiniu atžvilgiu būtų galima laikyti neišsprendžiamu. Bet mokslininkas mano kad žaidimas galėtų padėti išspręsti jau 30 metų matematikams ramybės neduodančią vadinamąją “P vs. NP” užduotį.

Šia užduotimi bandoma nustatyti, ar iš pirmo žvilgsnio neišsprendžiami klausimai iš tikrųjų išsprendžiami pakankamai paprastai, galbūt kompiuteriu.

R.Kaye sakė, kad jei kas nors sukurtų algoritmą, galintį nustatyti visas galimas minų išdėstymo kombinacijas gerokai didesnėje “Minesweeper” versijoje, tuomet jis išspręstų “P vs. NP” užduotį, todėl pirmajam laimingajam matematikui žadamas milijono dolerių prizas.

Bet šio atradimo rezultatai turėtų kur kas platesnę pritaikymo sferą. Jis galėtų padėti netgi bandant efektyviai “nulaužti” kodus.

www.DELFI.lt
Parašykite savo nuomonę
arba diskutuokite anonimiškai čia
Skelbdami savo nuomonę, Jūs sutinkate su taisyklėmis
Rodyti diskusiją Rodyti diskusiją
 

Aktualijos

D. Trumpas nusitaikė į „Nord Stream 2“ ir bando pamokyti Rusiją (599)

2017 birželio mėn. 26 d. 21:42
Vidurio ir Rytų Europoje vis daugiau paramos sulaukia geopolitinė iniciatyva, metanti iššūkį „Nord Stream 2“, skelbia politico.com.

Gardine aptiko Lietuvoje perkamus papildus: kainų skirtumas – šokiruojantis (201)

2017 birželio mėn. 26 d. 22:45
Gardine aptiko Lietuvoje perkamus papildus: kainų skirtumas – šokiruojantis
DELFI / Ugnė Karaliūnaitė
Šiuo metu sveikatos apsaugos ministerija įgyvendina keletą priemonių, kuriomis turėtų pigti daugiau kaip 800 pavadinimų kompensuojamųjų vaistų. Skaičiuojama, kad pacientai, rinkdamiesi pigesnius vaistus, galėtų sutaupyti apie 20 mln. eurų priemokų.

Orai: įspūdingą karštį lydės nemalonūs reiškiniai (3)

2017 birželio mėn. 27 d. 00:01
Orai: įspūdingą karštį lydės nemalonūs reiškiniai
Skaitytojo nuotr.
Šią savaitę numatomi labai neramūs ir permainingi orai. Iki savaitės vidurio temperatūra kilti neskubės, pūs smarkus vėjas, o dangumi plaukiantys debesys vis atneš lietaus, tačiau savaitės pabaigoje sulauksime malonios staigmenos.

R. Karbauskio valstiečiai Seime įgijo netikėtą advokatą, apie kurį nieko nenori žinoti (163)

2017 birželio mėn. 26 d. 20:15
Mišriai Seimo narių grupei priklausantis parlamentaras Bronius Matelis teigia sulaukęs partijos „Tvarka ir teisingumas“ atstovo Petro Gražulio raginimų grįžti į Lietuvos valstiečių ir žaliųjų sąjungos (LVŽS) frakciją. „Tokius raginimus P. Gražulis man išsakė mažiausiai du kartus“, – DELFI tvirtino B. Matelis.

Išsipildė vaiko svajonė: slapstytis nebereikės (60)

2017 birželio mėn. 26 d. 21:45
Išsipildė vaiko svajonė: slapstytis nebereikės
DELFI / Kęstutis Cemnolonskis
Pirmadienį valdžios desantas skubėjo į Vilkaviškio rajono savivaldybę, kur domėjosi ne kartą DELFI aprašyto 13-mečio šeimos problemomis. Savivaldybės valdininkams pavyko suminkštinti širdį – vaikas galės likti pas mamą.