“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

S. Skvernelio planas – R. Karbauskis nebeturės kitos išeities

2017 balandžio mėn. 25 d. 17:35
Premjeras Saulius Skvernelis vožtelėjo išrinktajam socialdemokratų pirmininkui Gintautui Paluckui kaip reikiant: jis atsisakė susitikti su naujuoju koalicijos partnerių lyderiu ir, vietoje to, susitiko su Tėvynės sąjungos-Lietuvos krikščionių demokratų pirmininku Gabrieliumi Landsbergiu.

Lietuvos kaime įsikūręs anglas: mano šuo gyvena geriau už kai kuriuos lietuvių emigrantus (75)

2017 balandžio mėn. 25 d. 15:50
Įėjęs į Radviliškio rajone, Šaukoto miestelyje, esančią kaimo parduotuvę iškart pastebėjau, kad pokalbis tarp pardavėjos ir kliento nesiklosto labai rišliai, bet į tai nekreipiau dėmesio, pagalvojau, turbūt pirkėjas paprasčiausiai girtas. Tačiau po kurio laiko suvokiau, kad girdžiu lietuvių kalbą su stipriu anglišku akcentu. Ką čia veikia anglas, negi turistas atklydo į šį vos 400 gyventojų turintį ir nuo pagrindinių kelių nutolusį kaimą?

Tirpsta valdžios pažadai dėl kompensacijų (33)

2017 balandžio mėn. 25 d. 16:33
Valdantieji, siūlydami naikinti PVM lengvatą šildymui, žadėjo labai išplėsti ratą asmenų, kurie galėtų pretenduoti į šildymo išlaidų kompensavimą.

A. Tapinas. Lyderių supergalios ir jų reitingas (97)

2017 balandžio mėn. 25 d. 14:43
Gintauto Palucko atėjimas į Rožių sostą iš esmės baigia didįjį politinių partijų vadų panteono persitvarkymą. Prisiminkime graikų mitologiją, kur Kronas rydavo savo vaikus, kad jie neatimtų iš jo valdžios, kol Dzeusą pagimdžiusi Rėja davė Kronui praryti akmenų ryšulį, o po to jau Kronui ėmė smarkiai viskas nesisekti. Tai pirmuoju tokiu Lietuvos partijų akmenų ryšuliu 2015 metais tapo Gabrielius Landsbergis, o atsinaujinimo ratą uždarė Paluckas.

Kaune ant kojų pareigūnus sukėlę iš ligoninės dingę vaikai atsirado Mažeikiuose atnaujinta (34)

2017 balandžio mėn. 25 d. 16:36
Kauno apskrities vyriausio policijos komisariato Kauno miesto Žaliakalnio policijos komisariato pareigūnai, gavę pranešimą, kad dingo vaikai, reagavo žaibiškai. 2002 m. gimusi mergaitė ir 2003 m. gimęs berniukas dingo iš ligoninės. Tačiau atomazga leido ne vienam lengviau atsikvėpti - vaikai sveiki ir gyvi.