“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į.
"Minesweeper"
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

Baugi valda prie ežero: prie įspėjimo „Nelipk!Užmuš“ pakrantėje aidėjo šūvis (181)

2016 gruodžio mėn. 10 d. 14:29
Asvejos regioniniame parke, Asvejos kraštovaizdžio draustinyje bandymai prieiti prie Asvejos ežero gali baigtis liūdnai. Noras pasivaikščioti ežero pakrante gali kainuoti ir gyvybę, mat parke egzistuoja teritorija, ant kurios tvoros kabo užrašas: „Nelipk!Užmuš“, o įvykio liudininkai teigia, kad teritorijoje ne taip seniai kažkas šaudė ir gąsdino užklydusius lankytojus.

Nustato, kokia tikimybė mirti per 10 metų: pasitikrinau ir aš (33)

2016 gruodžio mėn. 10 d. 15:22
Nustato, kokia tikimybė mirti per 10 metų: pasitikrinau ir aš
DELFI (K. Pansevič nuotr.)
Lietuvoje sergančiųjų širdies ir kraujagyslių ligomis amžius jaunėja, žmonės vis dar vangiai naudojasi profilaktikos programomis, o mirtingumas nuo šių ligų gerokai didesnis už Europos vidurkį. Statistika gąsdinanti, tiesa?

Miestas, kuriame kadaise glaudėsi pabėgėliai lietuviai: dabar čia tautiečiai vengia vieni kitų (71)

2016 gruodžio mėn. 10 d. 12:20
Birminghamas
Facebook nuotr.
Kai kurių lietuvių gyvenimo pradžia Jungtinėje Karalystėje buvo panaši į dabartinių pabėgėlių sąlygas Europoje. Birminghamo lietuvių ištakos – būtent tokios.

R. Žemaitaitis išrinktas „Tvarkos ir teisingumo“ pirmininku papildyta (127)

2016 gruodžio mėn. 10 d. 14:35
Remigijus Žemaitaitis
DELFI (A.Ufarto nuotr.)
Partijos „Tvarka ir teisingumas“ pirmininku šeštadienį išrinktas laikinasis partijos vadovas parlamentaras Remigijus Žemaitaitis.

A. Pugačiova prasitarė, kodėl ėmė vengti fotografų (3)

2016 gruodžio mėn. 10 d. 16:14
Alla Pugačiova ir Maksimas Galkinas
Vida Press
Pastaruoju metu 67-erių metų Rusijos estrados primadoną Alą Pugačiovą buvo galima gana dažnai išvysti viešuosiuose susibūrimuose. Visiškai neseniai atlikėja pasirodė per „Auksinio gramofono“ apdovanojimus, be to, lankėsi Dimos Bilano koncerte. Visgi kalbėdamasi su žurnalistais neblėstanti scenos žvaigždė prasitarė, kad kiekvienais metais jai vis sunkiau ryžtis išeiti į viešumą, rašo segodnya.ua.