Ученые создали алгоритм составления расписаний с помощью молекул ДНК

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

МОСКВА, 14 мар — РИА Новости. Ученые из Санкт-Петербурга создали алгоритм для гипотетического пока ДНК-компьютера, который позволит решать одну из непосильных для современных компьютеров задач — составлять учебные расписания.

ДНК-компьютеры выполняют вычисления при помощи химических реакций, в которых участвуют молекулы ДНК. В этих реакциях ферменты разрезают и склеивают молекулы подобно тому, как это происходит в живом организме. Таким образом можно получить множество молекул ДНК с разным строением и отобрать те, что отвечают заданным условиям. Эти действия можно перевести на математический язык и создать в пробирке биохимический компьютер, способный производить вычисления.

"Все ДНК-алгоритмы предлагают рецепты, как закодировать информацию, которая нам нужна, то есть перевести на "язык" цепочек ДНК, какие операции с ДНК делать — это могут быть только те операции, которые выполнимы в реальности, и потом, как извлечь ответ. Последнее обычно просто. Вот один из таких алгоритмов мы и предложили", — пояснил РИА Новости Игорь Попов из Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики.

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

"(В задаче составления расписания) есть и учителя, и классы, и уроки — все это надо перебрать и сопоставить. Задача гигантская по объему, и поэтому компьютерные расписания так реально до сих пор и не внедрены", — сказал Попов.

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

Сейчас ДНК-компьютеры являются лишь теоретической разработкой. Всего алгоритмов для них существует пара десятков, а практически реализованы лишь единицы, при этом ДНК-компьютеры пока что умеют решать только самые примитивные задачи и отнюдь не быстро. Так, например, уже существует алгоритм решения с помощью ДНК математической задачи, в которой нужно проложить путь между несколькими соединенными друг с другом точками, обойдя их все, но только по одному разу.

"(Ученые) решали ее в примитивном варианте — всего 7 вершин. Любой человек, глядя на эту картинку, в течение минуты выдаст ответ, или даже быстрее. У них это заняло с переливанием пробирок, по-моему, 3 рабочих дня" — рассказал Попов.

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

Работа Попова и его коллег Анастасии Воробьевой и Ирины Блиновой опубликована в International Journal of Bioinformatics Research and Applications.