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

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

О чём пишут научно-популярные журналы мира О чём пишут научно-популярные журналы мира

Научпоп: целебные звуки природы, археология Марса и исчезающие журналы

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

Может ли кентавр существовать с точки зрения биологии?

Вокруг света
Белеет парус на болоте Белеет парус на болоте

Чем так уникален нерукотворный природный парус — белокрыльник болотный?

Наука и жизнь
Испанские авианосцы на мировом рынке Испанские авианосцы на мировом рынке

Что помогло определиться с основными требованиями к универсальному авианосцу

Наука и техника
Удивительный трубкозуб Удивительный трубкозуб

Ожившей химерой с прошедших веков трубкозуба, шутя, обзывают

Знание – сила
Вечные ценности Вечные ценности

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

Вокруг света
Перелет–2023 «Байкальская кругосветка» Перелет–2023 «Байкальская кругосветка»

«Байкальская кругосветка» – воздушное путешествие вокруг знаменитого озера

Наука и техника
Девятое искусство Девятое искусство

Французы и бельгийцы росли на комиксах до того, как это стало мейнстримом

Вокруг света
На «зеленой» волне На «зеленой» волне

Какие экологические технологии внедряют отечественные аграрии

Агроинвестор
Скромные великаны Скромные великаны

В Португалии больше потерь и сожалений об утраченном величии, чем приобретений

Seasons of life
Черное зеркало Черное зеркало

Aito Seres M5 – достойная замена Mercedes-Benz в России

Автопилот
Самое древнее чувство Самое древнее чувство

Как у животных представлено чувства обоняния и вкуса

Наука и жизнь
Ключи от города Ключи от города

Мы даем несколько «точек входа» в Лиссабон, которые помогут понять его

Seasons of life
Сплю и вижу Сплю и вижу

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

Вокруг света
Лучше новых двух Лучше новых двух

Solaris НС от рождения приспособлен именно к российским условиям эксплуатации

Автопилот
Книга как искусство Книга как искусство

На протяжении долгих веков книга являлась главным хранителем информации

Знание – сила
Экологическая модернизация Экологическая модернизация

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

Агроинвестор
Малыми силами Малыми силами

Автомобильная экзотика: Urban Hopper Twin и Mini Pickup Twin Kipper

Автопилот
Возвращение к истокам Возвращение к истокам

Бизнес-седан Audi A6: классика и одновременно статус

Автопилот
Конкурсы интересные Конкурсы интересные

Как развлекали себя и окружающих на банкете или празднестве в прошлом?

Вокруг света
«Нечестная» игра Баше «Нечестная» игра Баше

Как найти выигрышную стратегию в игре Баше?

Наука и жизнь
Посвящено Беатриче Посвящено Беатриче

Он не смел поверить, что Биче исчезла навсегда. Его мир рухнул

Наука и жизнь
В европейском духе В европейском духе

Дом в стиле конструктивизма, построенный в 1931 г. таил сюрпризы…

Идеи Вашего Дома
Жизнь вечная Жизнь вечная

Глагол — это жизнь как она есть

Seasons of life
Делянка лирохвоста Делянка лирохвоста

Большая птица-лира живет во влажных лесах восточной Австралии и Тасмании

Знание – сила
Яркий кадр Яркий кадр

Заказчики этой квартиры оказались большими фанатами кино и поп-арта

Идеи Вашего Дома
Нижний Новгород: без лишних слов Нижний Новгород: без лишних слов

Нижний Новгород – место, где «заезженные эпитеты» имеют право на жизнь

Вокруг света
Сотворить «Онегина» Сотворить «Онегина»

Кто участвует в сотворении «Евгения Онегина» вместе с Пушкиным

Seasons of life
Жить интересно Жить интересно

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

Вокруг света
«Мои счастливейшие дни…» «Мои счастливейшие дни…»

Понятие гения места, «genius loci» – к Остафьево применимо как нельзя более

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