“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

Aktualu mėgstantiems keliauti: kur bus galima skristi šią vasarą (14)

2017 kovo mėn. 23 d. 11:57
Atostogas svetur šiltuoju metų laiku planuojantiems keleiviams oro bendrovės jau pranešė, kur žada skraidyti šį sezoną. DELFI domisi, kokius naujus skrydžius iš Lietuvos siūlys oro bendrovės.

Apie pinigų švaistymą pranešė ministrui: vietoj padėkos dabar laukia nuobaudų (157)

2017 kovo mėn. 23 d. 10:50
Socialinės apsaugos ir darbo ministerijai (SADM) pavaldžią įstaigą gaubia galimo piktnaudžiavimo bei pinigų švaistymo šešėlis. O apie pažeidimus ministrui Linui Kukuraičiui pranešusios darbuotojos sulaukė sistemos kirčio: ieškoma, kaip jas nubausti.

Teroras Londone: drastiškai išaugo sužeistųjų skaičius, policija surengė reidą nuolat atnaujinama  (102)

2017 kovo mėn. 23 d. 09:41
Londone keturi žmonės žuvo, o dar apie 29 buvo sužeisti trečiadienį per žaibišką ataką prie Didžiosios Britanijos demokratijos simbolio vartų, kurią policija laiko „su islamistais susijusio terorizmo“ aktu.

Lietuva neatsiliks nuo pasaulinių madų: naujoji VSD būstinė jau turi pravardę (55)

2017 kovo mėn. 23 d. 11:57
Lietuva neatsiliks nuo pasaulinių madų: naujoji VSD būstinė jau turi pravardę
VSD nuotr.
Legolendas, Mįslių rūmai, Akvariumas, Spurga, Baseinas – tai tik dalis kodinių pavadinimų, kurie prigijo garsiausių pasaulio žvalgybos tarnybų būstinėms. Ketvirtadienį atidaromas Valstybės saugumo departamento (VSD) pastatų kompleksas jau taip pat turi kelias pravardes.

Infografikas. Kaip keitėsi daugiausiai ir mažiausiai uždirbančiųjų algos (42)

2017 kovo mėn. 23 d. 11:04
Per pastaruosius 6 metus ketvirtadalio mažiausiai uždirbančiųjų gyventojų algos augo sparčiau, nei ketvirtadalio uždirbančiųjų daugiausiai, tačiau pastarųjų padidėjimo suma eurais buvo didesnė.