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

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

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

Палеонтология современности, ничье золото и жизнь во Вселенной

Наука и жизнь
Жизнь начинается с растений Жизнь начинается с растений

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

Наука и жизнь
Свежий взгляд Свежий взгляд

Основательница компании Trinity Yachts Анна Гончарук о том, как начался ее путь

Y Magazine
Император железных дорог Император железных дорог

Двенадцать лет назад за этой железнодорожной историей следил весь мир

ТехИнсайдер
Самые быстрые Самые быстрые

Когда речь заходит о скорости, победитель может быть только один

ТехИнсайдер
Искусственный интеллект смотрит в небо Искусственный интеллект смотрит в небо

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

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

Хороший урожай не позволит ценам сильно расти

Агроинвестор
Всем пригож песец Всем пригож песец

Песец – полярный кочевник с удивительной выносливостью

Знание – сила
Как искусственный интеллект переписывает правила медиарынка Как искусственный интеллект переписывает правила медиарынка

О том, где проходит граница между помощником человека и его заменой

ТехИнсайдер
Переход на отечественный софт: комфорт превыше всего Переход на отечественный софт: комфорт превыше всего

Как осуществлялось импортозамещение в сфере кадастра и геодезии

Наука и техника
Первые шаги стратегической авиации Первые шаги стратегической авиации

О том, ценой какого труда, в каких муках рождалась стратегическая авиация

Наука и техника
Биосигнатуры и их разоблачение: жизненно важные улики Биосигнатуры и их разоблачение: жизненно важные улики

Судить о возможном существовании иной жизни приходится по косвенным признакам

ТехИнсайдер
Тучерезы Тучерезы

Какие современные здания имеют шансы пережить столетия?

ТехИнсайдер
Золотая жила для агроинвестора Золотая жила для агроинвестора

Сколько стоит зайти на рынок готовой еды

Агроинвестор
День… суслика День… суслика

Я протёр глаза и приподнялся на локте: да это же суслик!

Наука и жизнь
Код будущего Код будущего

Умные очки для плавания, роботы-сварщики и другие технологии будущего

ТехИнсайдер
Позвольте представить: виноградовник Позвольте представить: виноградовник

Чем придать естественности натургардену? Попробуйте посадить виноградовник

Наука и жизнь
Есенин: божественный бросок вперед Есенин: божественный бросок вперед

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

Знание – сила
Три кита пивной отрасли Три кита пивной отрасли

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

Агроинвестор
Математические фронты Великой Отечественной войны Математические фронты Великой Отечественной войны

В 1930-х годах в России сформировалась плодотворная математическая жизнь

Наука и техника
Ставка давит на инвестиции Ставка давит на инвестиции

Какие макроэкономические факторы сдерживают рост агросектора

Агроинвестор
Удивительный и животворный трепанг Удивительный и животворный трепанг

Древние императоры пили настой трепанга как эликсир молодости и долголетия

Знание – сила
ИИ — иллюзия интеллекта? ИИ — иллюзия интеллекта?

Что же такое искусственный интеллект? Какие опасности он может таить?

Наука и жизнь
На каком языке говорили скифы? На каком языке говорили скифы?

Обзор книги Сергея Кулланда «Скифы: язык и этногенез»

Знание – сила
Новости науки Новости науки

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

Знание – сила
Достоевский и раненая самость Достоевский и раненая самость

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

Знание – сила
Инженерия рекордов Инженерия рекордов

О самых ярких случаях и новейших тенденциях в сфере спорта

ТехИнсайдер
«Красный» чай в «Бирюзовой чайхане» «Красный» чай в «Бирюзовой чайхане»

Ташкентец Ширяевец стал проводником поэта Есенина в мир Туркестана

Знание – сила
Скифы Северного Причерноморья: легенды и реальность Скифы Северного Причерноморья: легенды и реальность

Как греки превратили скифов в символ воинской чести и простоты

Знание – сила
«Мозг – самый важный орган» «Мозг – самый важный орган»

Что такое память? Где она «хранится»? Почему мы помним не всё?

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