Материалы портала «Научная Россия»

Новый алгоритм обещает упростить проблему «изоморфизма графов»

Новый алгоритм обещает упростить проблему «изоморфизма графов»
Возможно, ученым удалось найти алгоритм, упрощающий определение, являются ли два графически различных графа одним и тем же. Если решение подтвердится, то оно существенно упростит задачу сравнения данных, а также, возможно, изменит требования к шифрованию

Известный американский математик из Чикагского университета (США) Ласло Бабай (László Babai) на прошлой неделе прочел серию лекций, посвященных решению так называемой проблеме «изоморфизма графов», сообщает сайт MIT Technology Review. Как ожидается, ученый в ближайшем будущем опубликует результаты своей работы в одном из научных журналов.

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

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

Однако, по мнению Ласло Бабая, задача установления «изоморфизма графов», возможно, не является крайне сложной. Согласно предложенному им алгоритму, можно за гораздо меньшее число шагов — по сравнению с используемыми сейчас методами — установить, что два графа, по сути, являются одним. К сожалению, пока никаких конкретных сведений о том, как именно работает его алгоритм, нет. Однако ученый обещает их обнародовать в ближайшем будущем. Если его предположение подтвердится, это не только позволит быстрее оперировать с огромным массивом данных, накопленных в естественных науках, но и возможно заставит пересмотреть принципы шифрования данных, поскольку существенно упросит процесс расшифровки данных, которые были зашифрованы при помощи факторов.

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

алгоритмы поиска изоморфизм графов шифрование данных

Назад

Социальные сети

Комментарии

Авторизуйтесь, чтобы оставить комментарий