"Русский переплет" зарегистрирован как СМИ.
Свидетельство о регистрации в Министерстве печати РФ: Эл. #77-4362 от
5 февраля 2001 года. При полном или частичном использовании
материалов ссылка на www.pereplet.ru обязательна.
|
|
20.11.2015
15:58 |
Бабай приблизился к решению «проблемы тысячелетия» Математик Ласло Бабай из Чикагского университета в США разработал теоретический алгоритм, позволяющий существенно ускорить сравнение графов друг с другом. Исследование ученого связано с проблемой равенства классов P и NP, являющейся одной из «проблем тысячелетия». Об этом сообщает Nature News.
Исследование ученого относится к теории графов и посвящено сравнению изоморфных (сохраняющих структуру обратимых отображений) графов (некоторого набора вершин и связей между ними). Ученый показал, что проблема изоморфизма графов (перенумерации вершин одного графа для получения другого), связанная с возможностью существования доказывающего изоморфность двух графов алгоритма, может быть решена.
Положение вершин и связей между ними в графе определяется матрицей смежности. В случае если два графа изоморфны друг другу, существует перестановка, которая позволяет трансформировать матрицу смежности одного графа в матрицу смежности другого графа. Сложность решения этой задачи сводится к нахождению эффективного алгоритма, реализующего такую процедуру.
У изоморфных графов существуют инварианты — одинаковые для них числовые характеристики (например, число вершин). Вычисление полного инварианта графа (всех его инвариантов, перечисления которых необходимо и достаточно для доказательства его изоморфности другому графу) за полиномиальное время остается нерешенной задачей современной математики.
Последние успехи в этом направлении были сделаны в 1983 году. Бабай изложил основные моменты своей работы в двух лекциях, а присутствующие на них эксперты в области теории графов пока не нашли ошибок в рассуждениях ученого. Между тем окончательной верификации в математическом сообществе его работа пока не получила.
Метод математика основывается на предыдущих результатах и ищет симметрии графа, позволяющие переименовать его вершины. Реализация алгоритма происходит в несколько этапов, в каждом из которых происходит упрощение задачи за счет уменьшения количества вершин, которые необходимо переименовать, а также использует алгоритм Джонсона и рекурсию.
Работа Бабая вводит новый и работающий быстрее предыдущих алгоритм, который относится к классу NP-алгоритмов (возможность их работы можно проверить за полиномиальное время), а не классу P-алгоритмов (их время работы полиномиально зависит от размера входных данных).
Проблема равенства классов P и NP сформулирована как одна из семи задач тысячелетия, за решение которой Математический институт Клэя обещает премию в миллион долларов. В случае если исследования Бабая окажутся верными, это может означать существенный прогресс в математике.
По информации http://lenta.ru/news/2015/11/20/graphtheory/
|
|
20.11.2015
13:43 |
Найден виновник поражающей целый город болезни Альцгеймера
Американские ученые объяснили происхождение «проклятия Ярумаля»: в этом колумбийском городке выявлена крупнейшая в мире популяция страдающих болезнью . . . |
|
20.11.2015
13:40 |
Ученые узнали о стимулирующем влиянии паразитов на деторождение
Одни паразитические черви (аскариды) помогают женщинам рожать больше детей, тогда как другие (анкилостомы), напротив, снижают репродуктивные способности . . . |
|
20.11.2015
13:36 |
Китай потеснил США в рейтинге самых быстрых суперкомпьютеров
Количество китайских суперкомпьютеров в рейтинге Top-500 почти утроилось в ноябре по сравнению с июньским списком. При этом количество выскопроизводительных систем . . . |
|
20.11.2015
13:31 |
Запуск многомиллиардного международного термоядерного реактора отложен
Запуск проекта ИТЭР (ITER, International Thermonuclear Experimental Reactor — Международный термоядерный экспериментальный реактор) стоимостью несколько миллиардов долларов отложен на . . . |
|
20.11.2015
13:28 |
Изменение скорости света связали с темной материей
Физики из Университета Нового Южного Уэльса в Сиднее предположили, что темная материя может приводить к изменению фундаментальных констант, в частности, скорости . . . |
|
19.11.2015
23:17 |
Премию «Просветитель» 2015 года дали за математику и антропологию
В Российском академическом молодежном театре в Москве в четверг, 19 ноября, состоялась Восьмая торжественная церемония вручения премии «Просветитель» за лучшую . . . |
|
19.11.2015
17:00 |
Федор Конюхов облетит Землю на воздушном шаре
Российский путешественник Федор Конюхов отправится в кругосветное путешествие на воздушном шаре «Мортон». Об этом сообщается в пресс-релизе организаторов . . . |
|
19.11.2015
15:54 |
«Сокол» отправит россиян в стратосферу на истребителе за 800 тысяч рублей
Россияне смогут отправиться на экскурсию в стратосферу на истребителе МиГ-29 с Нижегородского авиационного завода «Сокол». Об этом сообщает туристический сервис . . . |
|
18.11.2015
21:10 |
Каждый десятый россиянин использует один пароль на все случаи жизни
Каждый десятый российский пользователь Интернета для всех своих аккаунтов применяет один и тот же пароль. Такие данные были получены по результатам теста на . . . |
|
18.11.2015
21:08 |
Huawei разработала аккумуляторы с 10-кратной скоростью заряда
В Huawei понимают, что время автономной работы — одна из самых насущных проблем для современных смартфонов, имеющих большие экраны и, следовательно, потребляющих . . . |
|
18.11.2015
20:49 |
Станция Cassini сделала снимок Дионы на фоне Энцелада
Станция Cassini сделала снимок спутников Сатурна. На изображении темная и близкая Диона расположена на фоне более светлого и далекого Энцелада. Об этом сообщается на . . . |
|
18.11.2015
20:47 |
Роспотребнадзор задумался о запрете моющих средств из-за водорослей
Роспотребнадзор рассмотрит возможность ограничить содержание фосфатов в моющих средствах. Об этом заявила руководитель ведомства Анна Попова, передает ТАСС . . . |
|
18.11.2015
20:44 |
Математик из Нигерии заявил о решении «проблемы тысячелетия»
Нигерийский математик Опиеми Энох из Федерального университета в городе Ойе-Экити заявил, что сумел доказать гипотезу Римана. Эта задача входит в список семи . . . |
|
18.11.2015
20:41 |
Тестовая сеть 5G запущена в Великобритании
Британская компания Gigaclear в тестовом режиме начала подключать абонентов к сверхскоростной широкополосной сети пятого поколения (5G). Об этом сообщается на сайте . . . |
|
18.11.2015
20:38 |
Три российских вуза вошли в сотню лучших университетов мира по физическим наукам
Три российских вуза вошли в число ста лучших в предметном рейтинге THE (Times Higher Education) по физическим наукам, обнародованном в 20:00 по московскому времени 18 ноября. НИЯУ . . . |
|
18.11.2015
14:58 |
Впервые описано превращение животного в одноклеточного паразита
Американские ученые выяснили, что некоторые медузы превратились в одноклеточных паразитов. Это беспрецедентный случай эволюции в сторону упрощения (из крупного . . . |
|
18.11.2015
14:04 |
Обнаружена связь между завтраками и успеваемостью школьников
Диетологи из Великобритании обнародовали результаты, согласно которым завтраки существенно повышают успеваемость школьников. Результаты своих исследований . . . |
|
18.11.2015
14:00 |
Астрофизик рассказал о возможности секса в космосе
Известный американский астрофизик и популяризатор науки Нил деГрасс Тайсон ответил на вопрос о том, как проходит секс в космосе и как преодолеть воздействие . . . |
|
18.11.2015
14:00 |
Астрофизик рассказал о возможности секса в космосе
Известный американский астрофизик и популяризатор науки Нил деГрасс Тайсон ответил на вопрос о том, как проходит секс в космосе и как преодолеть воздействие . . . |
