“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

Partietė apie G. Kildišienės istoriją: buvo padaryta klaida

2017 sausio mėn. 23 d. 16:44
Greta Kildišienė
DELFI / Karolina Pansevič
Seimo pirmininko pirmoji pavaduotoja Rima Baškienė teigia esanti nustebinta gerąja prasme, kad Greta Kildišienė atsisako Seimo nario mandato.

V. Matijošaitis apie naująją Kauno autobusų stotį: sekso pridėta daug didžiausia stotis duris atveria jau antradienį (311)

2017 sausio mėn. 23 d. 13:41
V. Matijošaitis apie naująją Kauno autobusų stotį: sekso pridėta daug
Kas vyksta Kaune nuotr.
Po kiek daugiau nei metus trukusių statybų statybų antradienį duris oficialiai atvers naujoji Kauno autobusų stotis. Tai bus didžiausia Lietuvos autobusų stotis, o paskutinį kartą senasis stoties pastatas buvo remontuotas kone prieš aštuonis dešimtmečius.

Visą pasaulį apskriejusi D. Trumpo kalba slepia bauginančią žinią (510)

2017 sausio mėn. 23 d. 13:56
D. Trumpas prisiekia 45-uoju JAV prezidentu
AP/ Scanpix
Naujo prezidento inauguracija paprastai siejama su pusiausvyra tarp pagarbos laiko patikrintoms valstybėje nusistovėjusioms vertybėms ir pažado įgyvendinti naujus šalies gerovės link vedančius sumanymus. Įprasta, kad asmuo, pirmą kartą kreipdamasis į piliečius kaip oficialus jų prezidentas, stengiasi įkvėpti šalį permainoms ir apibrėžti būsimus prioritetus, rašo „Time“ apžvalgininkas Davidas Von Drehle.

Siūlo grąžinti sovietmetį primenančią tvarką: jauniems specialistams tektų atidirbti regionuose (258)

2017 sausio mėn. 23 d. 15:24
Siūlo grąžinti sovietmetį primenančią tvarką: jauniems specialistams tektų atidirbti regionuose
DELFI / Kiril Čachovskij
Lietuvos savivaldybių asociacija (LSA) Vyriausybei siūlo paskyrimais po universiteto spręsti specialistų trūkumą regionuose, taip pat ragina savivaldybėms suteikti daugiau savarankiškumo.

Teismas išteisino „Snoro“ auditorių: nebuvo padaryta didelė žala (2)

2017 sausio mėn. 23 d. 16:15
Ramūnas Bartašius
DELFI / Domantas Pipas
Buvęs tarptautinės audito kompanijos „Ernst & Young“ auditorius Ramūnas Bartašius, dar 2010 m. tyręs dabar jau bankrutavusio „Snoro“ banko veiklą, išteisintas dėl tarnybos pareigų neatlikimo.