НАМ 10 ЛЕТ
беЛн.бу
- Белорусский, народный портал





Реклама

Купить ссылку здесь за руб.
Поставить к себе на сайт

Вход на портал

Для просмотра профиля, войдите на портал как пользователь.

Меню портала

Календарь

Погода

GISMETEO: Погода по г.Минск
Погода в других городах

Категории раздела

Интернет и СМИ [4054]
Технологии, Техника и наука [5872]
Общество [41]
Происшествия [3894]
Кино [1395]
Медиа [81]
Игры [897]
Музыка [608]
О кино [142]
Здоровье [0]
Иное [48]
Разное [610]
Навины.БУ [3097]
Общество, Происшествия и т.д.
Общество (СБ) [647]
Спорт (СБ) [96]
Происшествия (СБ) [186]
Программа телепередач [35]
На неделю
Белорусская нива (БН) [82]
Общество, происшествия, Пульс: события и факты и т.д.
Кино, мультфильмы, сериалы и т.д. В Онлайне [60]
Жизнь [0]

Реклама



Полезные ссылки

Статистика портала



соц.сети

Облако тегов

Мы принимаем



ТОП РЕЙТИНГ

Главная » 2015 » Ноябрь » 21 » Бабай приблизился к решению «проблемы тысячелетия»
14:41
Бабай приблизился к решению «проблемы тысячелетия»


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

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

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

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

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

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

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

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

 
 




Прямые ссылки beln.by:

  • - ссылка
  • - BBCode
  • - HTML


  • Прямые ссылки 24beln.ru:

  • - ссылка
  • - BBCode
  • - HTML

  • Категория: Технологии, Техника и наука | Просмотров: 201 | Добавил: rinhed | Теги: проблемы, к решению, Новости, беЛн, тысячелетия, приблизился, бабай | Рейтинг: 0.0/0
    Всего комментариев: 0
    Добавлять комментарии могут только зарегистрированные пользователи.
    [ Регистрация | Вход ]

    Реклама

    Купить ссылку здесь за руб.Поставить к себе на сайт

    Корзина

    Ваша корзина пуста

    Переводчик

    Выберите язык портала

    Поиск по порталу

    Поиск от яндекс

    Анекдоты...

    [12.03.2017][Разные]

    — Висит на заборе колышется ветром
    Колышется ветром бумажный листок
    Пропала собака пропала собака
    Пропала собака по кличке Дружок
    — Молодой человек, вы бы не могли петь свои песни подальше от нашей чебуречной?

    (0)

    Видео

    Мэй Дэй - Недоспать (An...

    00:02:52
    27 0 0.0

    ELTON - Тигрица

    00:03:07
    25 0 0.0

    Юта - Как в воду глядела

    00:03:51
    29 0 0.0

    Kava Tsikava - Море

    00:03:04
    30 0 0.0

    Sasha Zhulina - Влюбилась

    00:03:29
    35 0 0.0

    Получить бонус

    Еще бонусы тут

    Моментальный обмен WebMoney

    Вы можете получить WMR-бонус в размере 0,01-0,10 WMR на свой кошелек 1 раз в сутки

    Кошелек
    Код Защитный код

    Обмен Webmoney

    Бонус

    BAKSGRAD.RU
    Обновить Код.

    Архив