“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

R. Kuodis: situacija negrįžtama, Lietuvoje liks 2,5 miesto (189)

2017 vasario mėn. 24 d. 05:30
Lietuvoje egzistuoja dvi ekonomikos – gyventojais vis pasipildanti sostinė Vilnius ir regionai, virstantys ištisais pensionatais. Geru demografijos ciklu dar pasižymi tik Kaunas, iš dalies Klaipėda, bet regionuose vyrauja ekonomiškai neaktyvūs žmonės. Apsukti šios tendencijos trumpuoju laikotarpiu neįmanoma.

Emigrantai jau ruošiasi gyvenimui po „Brexit": galutinai nusisuks nuo Lietuvos? (35)

2017 vasario mėn. 24 d. 05:30
Artimiausiu metu Didžioji Britanija turėtų oficialiai pradėti išstojimo iš ES procedūras. Derybų baigtis turės įtakos ne tik jau išvykusiems emigrantams iš Lietuvos, bet ir kiekvienam, gyvenančiam čia.

Dalis vairuotojų apie nebegaliojančius pažymėjimus gali nežinoti (17)

2017 vasario mėn. 24 d. 06:22
Senojo pavyzdžio vairuotojo pažymėjimas
Regitros nuotr.
Senųjų vairuotojų pažymėjimų, kurie baigė galioti vasario 3 dieną, kol kas vis dar nepasikeitė beveik 90 tūkst. žmonių. Tikėtina, kad nemaža jų dalis gyvena užsienyje ir galbūt net nežino, jog vairuoja turėdami pažymėjimą, kuris nebegalioja. Vairuoti Lietuvoje su tokiu senu laminuotu pažymėjimu galima, bet gresia bauda už dokumento neturėjimą.

A. Guoga, V. Mazuronis ir A. Paulauskas: kuriems rinkimams jie ruošiasi (12)

2017 vasario mėn. 24 d. 06:54
Trys aukštus reitingus ir įtaką partijose turėję politikai – Antanas Guoga, Valentinas Mazuronis ir Artūras Paulauskas – teigia visiškai nuo Lietuvos politikos neatitrūkę ir svarsto apie dalyvavimą artimiausiuose rinkimuose. Vertindami dabartinę šalies politiką, jie laikosi skirtingų požiūrių į valdančiosios koalicijos darbo pradžią.

Orai: po baisaus savaitgalio – labai malonios permainos (7)

2017 vasario mėn. 24 d. 00:04
Savaitei baigiantis orai bus vėsesni, vis dar pūs gūsingas vėjas, sulauksime kritulių. Savaitgalio naktys bus šaltesnės, spustels šaltukas. Tačiau jau antroje sekmadienio pusėje į šalį pradės plūsti šiltesni orai ir ateinančios savaitės pradžioje termometrų stulpeliai šoktels iki 10 laipsnių.