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

Наука и жизнь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 веке. Часть 2 Русско-американские отношения в XIX веке. Часть 2

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

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

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

Автопилот
Сарацинка, воительница, христианка Сарацинка, воительница, христианка

В эпоху джахилийи у разных племен бедуинов положение женщин различалось

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

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

Наука и техника
Беззубый театр. Беседа на спорные темы Беззубый театр. Беседа на спорные темы

Продолжение статьи худрука Марка Розовского о современном театре

Знание – сила
Керосиновая история Керосиновая история

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

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

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

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

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

Знание – сила
Гладкая мускулатура самолета – электродвигатели Гладкая мускулатура самолета – электродвигатели

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

Наука и техника
Возвращение гребного колеса Возвращение гребного колеса

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

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

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

Знание – сила
Система Юпитера: Ганимед и Каллисто Система Юпитера: Ганимед и Каллисто

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

Наука и техника
Монеты в восточной пыли Монеты в восточной пыли

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

Знание – сила
Новый поход ветеранов Троянской войны Новый поход ветеранов Троянской войны

Филистимляне и троянцы против египетских фараонов

Знание – сила
Перовскитные солнечные элементы как перспективное направление зеленой энергетики Перовскитные солнечные элементы как перспективное направление зеленой энергетики

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

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

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

Знание – сила
Недоросли, скотинины, бригадиры и Стародум Недоросли, скотинины, бригадиры и Стародум

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

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

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

Знание – сила
«Галилея археологов» «Галилея археологов»

Археологи давно борются с искушением перекопать поглубже всю Святую Землю

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

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

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

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

Знание – сила
Революция со счастливым концом Революция со счастливым концом

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

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

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

Знание – сила
Беззубый театр Беззубый театр

Наступило время театра беспроблемного и потому бесчеловечного

Знание – сила
Себя посмотреть Себя посмотреть

Самые важные открытия, которые я сделал, связаны с кухней родного края

Bones
Честность как концепция Честность как концепция

Как шефы относятся к чистоте концепции и что в целом думают о честной позиции?

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

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

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

Брюгге — город, словно застывший в пространственно-временной капсуле

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