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

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

Наука и жизнь. Архив: 1941—1945 годы Наука и жизнь. Архив: 1941—1945 годы

О чем писали в журнале «Наука и жизнь» в годы Великой Отечественной войны?

Наука и жизнь
Заполняя белые места на карте Заполняя белые места на карте

Некоторые ключевые вехи экспедиционной истории РГО

Вокруг света
Слово редактора Слово редактора

На самом деле, нет более открытых миру людей, чем яхтсмены

Y Magazine
Артериальное движение Артериальное движение

Как прошли съемки фильма про зимние дороги и людей, которые по ним едут

Автопилот
Сделано с душой Сделано с душой

Эта уютная квартира — новая, но у неё уже есть своя интересная история

Идеи Вашего Дома
У эволюции нет конкретной цели, но есть результат У эволюции нет конкретной цели, но есть результат

Как происходит видообразование, с чего начинается и через какие этапы проходит

Наука и жизнь
Лихие 900-е Лихие 900-е

Как выглядит тест-драйв автомобиля Lynk & Co 900 в Китае для иностранных граждан

Автопилот
Июньская метель снежноцвета Июньская метель снежноцвета

Снежноцветы считаются красивейшими деревьями, и с этим трудно не согласиться

Наука и жизнь
«Нечестная» игра Баше «Нечестная» игра Баше

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

Наука и жизнь
Скромные великаны Скромные великаны

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

Seasons of life
Электрокопия Электрокопия

Игрушка для богатых мальчиков — электрическая копия Bentley 4½ litre ‘Blower’

Автопилот
Долгий путь от «учебки» к Победе Долгий путь от «учебки» к Победе

В минометной роте любили песни: о поэтах на фронте Отечественной войны

Знание – сила
Надеяться и делать Надеяться и делать

О стрит-арте: почему Португалия — не лучшая страна для современного художника

Seasons of life
«Ползи, улитка…» «Ползи, улитка…»

Куда деться от городской суеты? Создать город без суеты!

Вокруг света
Смелая палитра Смелая палитра

Эта небольшая квартира не производит впечатления маленького пространства

Идеи Вашего Дома
На аллеях Аполлона На аллеях Аполлона

Остафьево: образ места, где всё буквально дышит поэзией

Знание – сила
В европейском духе В европейском духе

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

Идеи Вашего Дома
Уютный аскетизм Уютный аскетизм

Интерьер в стиле софт-минимализм с органично вплетённой японской темой

Идеи Вашего Дома
«Кузнец – это в первую очередь инженер» «Кузнец – это в первую очередь инженер»

Как ученые исследуют магнитное поле Земли? Влияют ли на нас магнитные бури?

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

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

Идеи Вашего Дома
Белеет парус на болоте Белеет парус на болоте

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

Наука и жизнь
Тихая гавань русских литераторов Тихая гавань русских литераторов

Усадьбе Остафьево повезло, в ее облике с давних времен мало что менялось

Знание – сила
Жизнь на колесах Жизнь на колесах

Вэнлайф в России – жизнь в поисках смысла, лета и новых впечатлений

Автопилот
Сплю и вижу Сплю и вижу

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

Вокруг света
Возвращение к истокам Возвращение к истокам

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

Автопилот
Жить интересно Жить интересно

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

Вокруг света
Самое древнее чувство Самое древнее чувство

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

Наука и жизнь
Что «видели» астероиды? Что «видели» астероиды?

Чем астероиды интересны астрономам?

Наука и жизнь
И ты, Брут И ты, Брут

Второй год португальский проект Broot путешествует по мировым выставкам дизайна

Seasons of life
Художники Художники

Рассказ Александра Маркова «Художники»

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