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

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

ДНК-компьютеры выполняют вычисления при помощи химических реакций, в которых участвуют молекулы ДНК.

В этих реакциях ферменты разрезают и склеивают молекулы подобно тому, как это происходит в живом организме.

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

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

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

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

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

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

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

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

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

Источник - http://www.nanonewsnet.ru/news/2014/uchenye-sozdali-algoritm-sostavleniya-raspisanii-s-pomoshchyu-molekul-dnk

 

Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта Карта сайта