Редакция газеты "Iўеўскі край"

Учреждение "Редакция газеты "Iўеўскі край"

Белорусские айтишники решили задачу, за которую обещали миллион долларов. Но денег не получат

Наука и технологии / Среда, 11 апреля 2018 11:01 / Прочитано: 9454

Работники минской IT-компании Дмитрий Литвинович и Евгений Клещук прочитали о награде в миллион долларов за решение шахматной задачи — и создали программу, которая превосходит многие существующие. Правда, позже оказалось, что миллион платят не за само решение, а за ответ на более сложный вопрос.

Иллюстрация: gizmodo.com
Иллюстрация: gizmodo.com

Миллион за «быстрое» решение

Новость про «Задачу о ферзях» облетела СМИ в сентябре 2017 года. На TUT.BY она появилась под заголовком «Британские ученые пообещали миллион долларов за разгадку шахматной задачи». Речь в ней шла об ученых из Сент-Эндрюсского университета в Великобритании, которые изучали шахматную задачу и рассуждали о перспективах ее решения.

Суть задачи заключается в том, чтобы расставить на шахматной доске восемь ферзей таким образом, чтобы ни один из них не попадал под удар другого. Подразумевается, что ферзь бьет все клетки, расположенные на одной с ним вертикали, горизонтали или диагонали.

Для восьми ферзей и доски 8 на 8 клеток решить задачу легко. А вот с увеличением размеров поля и количества фигур задача усложняется. Британские исследователи обнаружили, что если размер доски увеличить до 1000 на 1000 клеток, компьютерные программы начинают зависать. Также они отметили, что создатель программы, которая докажет, есть ли у задачи «быстрое» решение, может рассчитывать на приз в миллион долларов. Сами они уверены, что такая программа невозможна.

«Не совсем перебор»

Сотрудники одной минской IT-компании OnePoint Дмитрий Литвинович и Евгений Клещук решили попробовать. За полгода работы они создали алгоритм, который рассчитывает решение для доски с заданным размером. Программа работает на обычных компьютерах и мобильных телефонах. С задачей для 1000 ферзей она справляется за три минуты.

— Это не совсем перебор, там есть определенный алгоритм, — рассказал Дмитрий. — От обычного перебора, пишут, зависает компьютер. Здесь есть конкретная логика, по которой высчитывается позиция каждой конкретной фигуры, а не просто перечисляются варианты.

Молодые люди обратились в институт за вознаграждением, но выяснилось, что деньги обещали не совсем за это. Выплатой миллиона долларов занимается не британский Сент-Эндрюсский университет, а американский институт Клэя. Он готов заплатить любому, кто докажет, равны ли математические классы P и NP.

Шахматная задача о ферзях может лишь помочь в поиске ответа на вопрос о P и NP. Правда, из-за того, что британский институт выпустил сообщение с заголовком «шахматная головоломка содержит ключ к призу в миллион долларов» получилась путаница, а по интернету разлетелась новость, которую все поняли не так.

— Я не совсем расстроился, — рассказывает Дмитрий. — Если они так написали, это, возможно, все-таки является ключом. Может, стоит как-то шире поработать над этой программой или связаться с тем профессором, который эту мысль озвучил.

Переключаться на математическую «задачу тысячелетия» Дмитрий пока не планирует.

— Я не великий математик, я немного другим себе на хлеб зарабатываю. Но если вдруг у меня появится знакомый математик, который подскажет, как это можно воплотить, — то, может быть, займусь. Пока я буду работать с тем, что есть.

Что за задача об P и NP?

Классом P называют множество задач, которые компьютер может решить «быстро» (то есть за полиномиальное время). К ним относят базовые арифметические действия, сортировку списков, поиск по таблице с данными.

Класс NP — это задачи, правильность ответа на которые можно быстро проверить. Например, задача о сумме. Предположим, что у вас есть монеты номиналом 2, 3, 5, 6 и 7 рублей, по одной каждого номинала, и вы хотите без сдачи оплатить покупку стоимостью 21 рубль. Можно ли набрать из данных монет сумму, равную 21?

В этой задаче для получения ответа нужно перебрать разные варианты, а чтобы доказать, что решения нет, — вообще перебрать все возможные варианты. Если количество монет увеличить на несколько порядков, решение выглядит совсем непрактичным. При этом результат проверить легко — просто сложить номиналы всех монет.

Суть «задачи тысячелетия» формулируется так: равны ли классы P и NP? Если легко проверить правильность решения задачи, может ли быть так же легко решить эту задачу? Большинство специалистов уверены, что ответ отрицательный. Однако доказать этого пока никто не смог. Если же вдруг окажется, что P = NP, то человечество ждет переворот в криптографии. Именно за это решение американский институт Клэя готов заплатитьмиллион долларов.

https://42.tut.by/587956

Оставить комментарий

Ивье

Облачно
2°C
ЮЮВ - 33.80 км/ч
Среда
3°C / 6°C
Четверг
2°C / 4°C
Пятница
-1°C / 2°C
  • Популярное
  • Коммент.

Способы оплаты

Наши соцсети

PDF-рассылка

Уважаемые читатели газеты «Іўеўскі край»!

Вы можете подписаться на электронную версию нашей газеты, представленную в PDF-формате. Газета будет высылаться на указанный вами адрес электронной почты  по вторникам и пятницам накануне выхода в печать. Подписаться можно, начиная с любой даты. Будьте первыми в курсе свежих новостей Ивьевщины!

СТОИМОСТЬ ЭЛЕКТРОННОЙ ПОДПИСКИ:

– на месяц – 1 руб. 80 коп. (18 тысяч рублей); 
– на три месяца – 5 руб. 40 коп. (54 тысяч рублей); 
– на шесть месяцев – 10 руб. 80 коп. (108 тысяч рублей).

Подробнее

Наши контакты

р/с № BY47BAPB30152768600140000000

в РКЦ № 14 в. г. Ивье филиала
ОАО "Белагропромбанк" -
Гродненское областное управление,
расположенном по адресу:
231337, г. Ивье, ул. 50 лет Октября,
21а, код BAPBBY2X,

УНН 500051130.

E-mail: pressa.ik@gmail.com

Тел/факс: (01595) 2-23-92

Наш адрес:
231337, Гродненская обл., г. Ивье,
ул. 1 Мая, 18

Ссылки

Президент Республики Беларусь


Ивьевский районный исполнительный комитет

\

 

 

Please publish modules in offcanvas position.