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






Реклама

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

Реклама



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

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

Меню портала

Календарь

Погода

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

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

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

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

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

соц.сети

Облако тегов

Мы принимаем



ТОП РЕЙТИНГ

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


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

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

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

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

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

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

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

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

 
 




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

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


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

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

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


    Внимание!
    В комментариях запрещено размещать ссылки, рекламу сторонних ресурсов(сайтов). Если Вы разместили ссылку или рекламу, то комментарий будет удален автоматически.

    Реклама

    Корзина

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

    Переводчик

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

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

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

    Анекдоты...

    [14.02.2017][Разные]

    Где-то на лавке сидит плюшевый мишка и мечтает чтобы его купили.
    Где-то молодой человек ждёт не дождётся когда наступит этот День и он подарит девушке плюшевого мишку.
    Где-то девушка молится чтобы ей подарили что угодно, но только не плюшевого мишку.

    (0)

    Видео

    00:00:10

    Футаж на зеленом фоне (Балерина танцует)

    • Просмотры:
    • Всего комментариев: 0
    • Рейтинг: 0.0
    00:00:07

    Футаж на зеленом фоне (Винни идет)

    • Просмотры:
    • Всего комментариев: 0
    • Рейтинг: 0.0
    00:00:07

    Футаж на зеленом фоне (Винни на месте)

    • Просмотры:
    • Всего комментариев: 0
    • Рейтинг: 0.0
    00:00:14

    Футаж на зеленом фоне (Винни на шарике)

    • Просмотры:
    • Всего комментариев: 0
    • Рейтинг: 0.0
    00:04:15

    7Б - Птица RMX

    • Просмотры:
    • Всего комментариев: 0
    • Рейтинг: 0.0

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

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

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

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

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

    Обмен Webmoney

    Бонус

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

    Архив