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

Наука и жизнь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

История необычного гибрида спиреи: от сада XIX века до природных популяций История необычного гибрида спиреи: от сада XIX века до природных популяций

История гибрида, обнаруженного в природе спустя столетие после его создания

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

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

Вокруг света
«Двойка» за хорошее поведение «Двойка» за хорошее поведение

BMW M2 Gran Coupe: баварское купе, которое на самом деле седан

Автопилот
Жизнь в магнитном поле Жизнь в магнитном поле

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

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

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

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

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

Наука и техника
Пережившие века Пережившие века

Обережные символы и представления о прекрасном, вшитые в традиционные ремесла

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

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

Знание – сила
Космический буксир: мирный атом или ненаучная фантастика? Космический буксир: мирный атом или ненаучная фантастика?

Чем интересна перспектива использования ядерного двигателя в космосе?

Наука и техника
Аграрный PR как часть стратегии развития компании Аграрный PR как часть стратегии развития компании

Какие эффективные инструменты маркетинговых коммуникаций используют в 2025 году

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

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

Знание – сила
Апрель: «нашествие» хохлаток Апрель: «нашествие» хохлаток

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

Наука и жизнь
Ход слоном Ход слоном

Почему та или иная страна становится передовой, а потом вдруг отстающей?

ТехИнсайдер
Бурялом Бурялом

Перед ним появилась огромная голова зверя с вытянутой мордой и острыми ушами...

Наука и жизнь
Кочевая кузница Кочевая кузница

Путешествие в край шаманов за секретами якутских мастеров

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

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

Наука и техника
Индейка на взлете Индейка на взлете

Российское производство мяса индейки выросло почти на 4%

Агроинвестор
Островский – революция в русском театре Островский – революция в русском театре

Гончаров, известный трилогией на букву «О», был интересным и метким критиком

Знание – сила
Учимся понимать наши растения Учимся понимать наши растения

Легко прочитать, как именно надо ухаживать за цветком, но почему именно так?

Наука и жизнь
Лингвистические фантомы Лингвистические фантомы

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

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

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

Знание – сила
Фотосинтез — «игра с огнём» для растения Фотосинтез — «игра с огнём» для растения

Каким образом свет «питает» растение и как вызывает химические реакции?

Наука и жизнь
Система Юпитера: Ганимед и Каллисто Система Юпитера: Ганимед и Каллисто

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

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

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

Наука и техника
Верни мой каменный топор Верни мой каменный топор

Вновь изобрести технологии каменного века занимательно, но зачем это нужно?

Вокруг света
Время спать Время спать

Хотите впасть в спячку до весны? Теоретически для этого нет никаких препятствий

ТехИнсайдер
Русско-американские отношения в XIX веке. Часть 2 Русско-американские отношения в XIX веке. Часть 2

Какими были отношения США и России накануне войны между Севером и Югом

Наука и техника
Зажигаем звезды Зажигаем звезды

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

ТехИнсайдер
Наука в фантастике: эпизоды истории Наука в фантастике: эпизоды истории

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

Наука и жизнь
Вновь о темной материи Вновь о темной материи

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

Знание – сила
Открыть в приложении