“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

Nemenčinėje „Aro“ kovotojų išguldyti atskalūnai turi savo įvykių versiją (486)

2017 gegužės mėn. 24 d. 15:23
Jevgenijus Denisovas Nemenčinės ryšių cnetro teritorijoje
Facebook
Miške prie Nemenčinės sekmadienio rytą susirenka 12-os asmenų grupė. Akylesniems aplinkiniams į akis gali kristi, kad bent dalis vyrų vilki rusiško pavyzdžio maskuojamas uniformas, regis, yra ginkluoti rusiškais automatais. Gavusi tokį pranešimą žaibiškai reaguoja policija, atvyksta Antiteroristinių operacijų rinktinės ARAS kovotojai ir sulaiko galimai pavojingus asmenis.

Įspėja apie pavojaus signalą populiarėjančio skolinimosi būdo naudotojams (35)

2017 gegužės mėn. 24 d. 14:20
Tarpusavio skolinimosi platformas reitinguojantis „Welltrado“ teigia, kad vėluojančių ir nemokių paskolų skaičius geriausiai parodo, ar gyventojų jose investuoti pinigai yra saugūs. Tačiau populiarėjančią finansinę paslaugą Lietuvoje teikiantys verslininkai sako, jog svarbiausiu kriterijumi išlieka investicinė grąža.

Lietuvoje atsiras dar vienas bankas (1)

2017 gegužės mėn. 24 d. 16:19
Atsižvelgdama į kredito unijos „Mano unija“ prašymą ir jos atliktus pasirengimo banko veiklai veiksmus, Lietuvos banko Priežiūros tarnyba leido ją pertvarkyti į akcinę bendrovę, rašoma Lietuvos banko pranešime.

Garsaus Vilniaus gydytojo namuose policija atliko kratą: radiniai, švelniai tariant, šokiravo (241)

2017 gegužės mėn. 24 d. 13:03
Respublikinės Vilniaus universitetinės ligoninės (RVUL) gydytojo mokslinis tyrimas, esą galėjęs sukelti tikrą perversmą medicinos srityje, žinomam traumatologui ortopedui nuėjo perniek – Lietuvos policija, gavusi JAV Dingusių ir išnaudojamų vaikų centro pranešimą, mediko namuose atliko kratą. Tai, ką jie aptiko, švelniai tariant, šokiravo.

Kaimo parduotuvių savininkas su baime laukia naujausių draudimų (34)

2017 gegužės mėn. 24 d. 15:51
Seimo Sveikatos reikalų komitetas neseniai pritarė siūlymui trumpinti prekybos alkoholiu laiką. Tačiau trijų nedidelių Jurbarke esančių parduotuvių savininkas tikina, kad tai gali būti kritinis smūgis jo valdomoms parduotuvėms, kuris galimai baigsis jų uždarymu.