Чтение RSS
По вопросам сотрудничества и рекламы на портале MixliP, обращаться на почту admin@turklib.ru
MixliP - Территория вебмастера! На нашем сайте вы найдете все для веб-мастеров и не только =) ! Различные скрипты для вашего сайта. И еще на нашем сайте немало софта! Заходи не пожалеешь!


Бабай приблизился к решению "проблемы тысячелетия"



 Бабай приблизился к решению "проблемы тысячелетия"

Математик Ласло Бабай из Чикагского университета в США разработал теоретический алгоритм, позволяющий существенно ускорить сравнение графов друг с другом. Исследование ученого связано с проблемой равенства классов N и NP, являющейся одной из «проблем тысячелетия». Об этом сообщает Nature News.


Исследование ученого относится к теории графов и посвящено сравнению изоморфных (сохраняющих структуру обратимых отображений) графов (некоторого набора вершин и связей между ними). Ученый показал, что проблема изоморфизма графов (перенумерации вершин одного графа для получения другого), связанная с возможностью существования доказывающего изоморфность двух графов алгоритма, может быть решена.




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


У изоморфных графов существуют инварианты — одинаковые для них числовые характеристики (например, число вершин). Вычисление полного инварианта графа (всех его инвариантов, перечисления которых необходимо и достаточно для доказательства его изоморфности другому графу) за полиномиальное время остается нерешенной задачей современной математики.


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


Метод математика основывается на предыдущих результатах и ищет симметрии графа, позволяющие переименовать его вершины. Реализация алгоритма происходит в несколько этапов, в каждом из которых происходит упрощение задачи за счет уменьшения количества вершин, которые необходимо переименовать, а также использует алгоритм Джонсона и рекурсию.


Работа Бабая вводит новый и работающий быстрее предыдущих алгоритм, который относится к классу NP-алгоритмов (возможность их работы можно проверить за полиномиальное время), а не классу P-алгоритмов (их время работы полиномиально зависит от размера входных данных).


Проблема равенства классов N и NP сформулирована как одна из семи задач тысячелетия, за решение которой Математический институт Клэя обещает премию в миллион долларов. В случае, если исследования Бабая окажутся верными, это может означать существенный прогресс в математике.




Просмотры:
Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.


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


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


Вся информация о программном обеспечении и скриптах, размещенная на данном сайте, предоставлена исключительно в ознакомительных целях и только для просмотра, и призвана помочь посетителям сайта MixliP.ru выбрать для себя и в последствии приобрести соответствующие лицензионные авторские программные продукты.


Читать полностью информацию правообладателям.


Сайт работает на хостинге BEGET.RU


Рекомендует Mixlip.RU





Наши друзья

Полезное

NEW - Анализ сайта

Оптимизация вашего сайта.

Читайте также

 Пользователи онлайн

  • Всего на сайте: 8
    Пользователей: 0
    Гостей: 7
    Роботов: 1
    Google