Бюро научно-технической информации

Наука и жизньFan

БНТИ

Бюро научно-технической информации

В конце ноября 2018 года состоялся седьмой Национальный суперкомпьютерный форум в Переславле-Залесском. Институт программных систем РАН ежегодно собирает специалистов отрасли для обсуждения передовых достижений, вопросов создания и применения суперкомпьютерных технологий. Корреспонденты «Науки и жизни» Ольга Баклицкая-Каменева и Анна Смирнова побывали на форуме и познакомились с некоторыми разработками.

Задача коммивояжёра: в сто раз быстрее «Конкорда»

В 1857 году ирландский математик Уильям Гамильтон придумал забавную головоломку «Кругосветное путешествие» по додекаэдру. Игра сводилась к обходу по рёбрам всех вершин правильного додекаэдра при условии, что ни в одну из вершин нельзя заходить более одного раза. Вершины символизировали названия городов, а рёбра — соединяющие их дороги. Такой додекаэдр Гамильтон В конце ноября 2018 года состоялся седьмой Национальный суперкомпьютерный форум в Переславле-Залесском. Институт программных систем РАН ежегодно собирает специалистов отрасли для обсуждения передовых достижений, вопросов создания и применения суперкомпьютерных технологий. Корреспонденты «Науки и жизни» Ольга Баклицкая-Каменева и Анна Смирнова побывали на форуме и познакомились с некоторыми разработками. заменил плоским графом (см. рисунок).

В современном виде эта головоломка известна как задача странствующего торговца или коммивояжёра, которому необходимо проложить через города самый выгодный маршрут, например, по времени и стоимости, а затем вернуться домой. Для нематематика эта задача кажется простой, но прямой способ перебора вариантов непосилен даже для современных компьютеров: число маршрутов с ростом городов увеличивается стремительно, а машино-часы начнут измерять миллионы и миллиарды лет! Для математика и формулировка звучит по-другому: это задача о нахождении минимального гамильтонова цикла на полном ориентированном графе с неотрицательными весами дуг. Для профессионала она NP-трудная. Это означает, что на данный момент не существует эффективных полиномиальных* алгоритмов её решения. Но если бы таковой нашёлся (или было бы получено доказательство, что его нет), то Математический институт Клэя (Кембридж, США) выплатил бы миллион долларов за решение этой — главной из семи задач тысячелетия (проблема равенства классов P и NP).

O'qishni davom ettirish uchun tizimga kiring. Bu tez va bepul.

Roʻyxatdan oʻtish orqali men foydalanish shartlari 

Tavsiya etilgan maqolalar

Расшифровка диалога, полученного по молекулярной связи Расшифровка диалога, полученного по молекулярной связи

Я жив. И даже условно цел, но существую в виде облака...

Наука и жизнь
Десять цветов Десять цветов

Самые древние и почитаемые традиционные ремесла – часть культурного кода Мьянмы

Вокруг света
Она вышивает мечты Она вышивает мечты

Самая яркая звезда на небосклоне высокой моды Поднебесной — талантливая Гуо Пей

Y Magazine
Культура сбережений: зачем откладывать на завтра то, что можно потратить сегодня? Культура сбережений: зачем откладывать на завтра то, что можно потратить сегодня?

Зачем каждому гражданину нужно выработать у себя привычку делать сбережения?

Наука и техника
Революция со счастливым концом Революция со счастливым концом

Рубеж XIX и XX веков отмечен бурными событиями в целом ряде наук

Знание – сила
Неуместные следы и водоплавающий единорог: злоключения Карла Бау Неуместные следы и водоплавающий единорог: злоключения Карла Бау

«Научный» креационизм. Мифы и предубеждения

Наука и техника
Жила-была золотая рыбка Жила-была золотая рыбка

Как золотые рыбки из аквариумов угрожают экологии

Наука и жизнь
Звезды манящие Звезды манящие

Ослепительная вспышка, которой уже некого слепить, миг неуловимый

Знание – сила
Искоренить фальсификат Искоренить фальсификат

Методики проверки, испытаний, идентификации продукции нужно совершенствовать

Агроинвестор
Китайское техно Китайское техно

Краткая история технологического идеализма

ТехИнсайдер
Если на месте не сидится Если на месте не сидится

Все существа, начиная с самых первых, неустанно пытались обрести движение

Наука и жизнь
Физика в поисках ответа на разгадку бытия: от Эйнштейна до Хокинга и Лоуренса Краусса Физика в поисках ответа на разгадку бытия: от Эйнштейна до Хокинга и Лоуренса Краусса

Почему существует Вселенная? Почему существует мир, почему в нем есть мы?

Знание – сила
В тени новой биологии, или Вверх по лестнице, ведущей вниз В тени новой биологии, или Вверх по лестнице, ведущей вниз

Сравнительная анатомия – старая наука, интеллектуальный опыт которой очень богат

Знание – сила
Вновь о темной материи Вновь о темной материи

Проблема темной материи всерьез привлекает ученых

Знание – сила
Наука в фантастике: эпизоды истории Наука в фантастике: эпизоды истории

Одной из тем обсуждения в научной фантастике ХХ века была космическая экспансия

Наука и жизнь
Недоросли, скотинины, бригадиры и Стародум Недоросли, скотинины, бригадиры и Стародум

И спустя 200 лет пьесы Дениса Фонвизина остаются интересны и востребованы

Знание – сила
Там, где свет слушает звук Там, где свет слушает звук

Как и для чего создаются гиперспектрометры и мультиспектральные камеры

Наука и жизнь
Растениеводы в поисках маржи Растениеводы в поисках маржи

На чем смогут заработать аграрии в 2025 году

Агроинвестор
Система Юпитера: Ганимед и Каллисто Система Юпитера: Ганимед и Каллисто

Что делает Ганимед и Каллисто очень интересными космическими телами?

Наука и техника
Водяные козлы – аристократы саванн Водяные козлы – аристократы саванн

«Водяных козлов я часто встречал в восточноафриканской саванне»

Знание – сила
Липецк: за рулем и пешком Липецк: за рулем и пешком

Как в Липецкой области мастера восстанавливают связь между прошлым и настоящим

Вокруг света
Апрель: «нашествие» хохлаток Апрель: «нашествие» хохлаток

Хохлатки-эфемероиды — радостный вскрик пробуждающейся природы

Наука и жизнь
Керосиновая история Керосиновая история

Жизнь в послевоенном социализме делится на «время керосина» и «время газа»

Знание – сила
Ушедшее в народ Ушедшее в народ

Как сон мастера картонажа прославил духов Мексики?

Вокруг света
Монеты в восточной пыли Монеты в восточной пыли

Важным источником наших знаний об античной истории являются монеты

Знание – сила
Авианосцы ВМС Индии XXI века Авианосцы ВМС Индии XXI века

История постройки авианосца «Викрант»

Наука и техника
Биология на рубеже веков, или Сто лет тому вперед Биология на рубеже веков, или Сто лет тому вперед

Биология в 1900-х годах по темпам своего развития ничуть не отставала от физики

Знание – сила
Зажигаем звезды Зажигаем звезды

Подборка историй о людях, которые двигают прогресс небывалым

ТехИнсайдер
Новости науки Новости науки

Обнаруженная в ранней Вселенной грандиозная галактика и другие новости науки

Знание – сила
Непростая материя Непростая материя

Секреты, которые скрывают узоры ивановских тканей

Вокруг света
Открыть в приложении