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

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

Рефераты Рефераты

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

Наука и жизнь
Спинной мозг самолета – автопилот Спинной мозг самолета – автопилот

Пока человек толком не понимал, что такое полет, автопилот был не нужен

Наука и техника
Удивительный и животворный трепанг Удивительный и животворный трепанг

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

Знание – сила
«Красный» чай в «Бирюзовой чайхане» «Красный» чай в «Бирюзовой чайхане»

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

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

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

ТехИнсайдер
Достоевский и раненая самость Достоевский и раненая самость

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

Знание – сила
Разноцветные пески Калининградских пляжей Разноцветные пески Калининградских пляжей

Почему после шторма песок на Калининградском пляже становится… разноцветным?

Наука и жизнь
Инженерия рекордов Инженерия рекордов

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

ТехИнсайдер
Три кита пивной отрасли Три кита пивной отрасли

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

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

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

Наука и жизнь
Позвольте представить: виноградовник Позвольте представить: виноградовник

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

Наука и жизнь
Галльская война Галльская война

Юлий Цезарь: завоевание Галлии

Знание – сила
Император железных дорог Император железных дорог

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

ТехИнсайдер
Одна маленькая лягушка и 10 000 мышей Одна маленькая лягушка и 10 000 мышей

Почему батрахотоксин смертелен для человека, но безвреден для маленькой лягушки?

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

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

Агроинвестор
Тучерезы Тучерезы

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

ТехИнсайдер
Мы длинной вереницей идём за Синей птицей… Мы длинной вереницей идём за Синей птицей…

Синяя Птица — символ счастья, которое ищут все люди, но находят лишь немногие

Наука и жизнь
Что такое интеллект? Что такое интеллект?

В каком направлении движется развитие искусственного интеллекта?

Знание – сила
Искусственный интеллект смотрит в небо Искусственный интеллект смотрит в небо

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

Наука и жизнь
Всем пригож песец Всем пригож песец

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

Знание – сила
Самые быстрые Самые быстрые

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

ТехИнсайдер
ИИ — иллюзия интеллекта? ИИ — иллюзия интеллекта?

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

Наука и жизнь
Учимся понимать наши растения Учимся понимать наши растения

Кажется, чего уж проще: полить цветы. Но и здесь есть ряд тонкостей...

Наука и жизнь
Скифы: наследие, не расшифрованное до конца Скифы: наследие, не расшифрованное до конца

Скифы – народ, о которых мы знаем многое, но почти ничего не понимаем

Знание – сила
Беременные андроиды Беременные андроиды

В последнее время идет прогресс в работах над искусственной маткой

ТехИнсайдер
В «Зеленой Долине» разместится 40 тыс. голов КРС В «Зеленой Долине» разместится 40 тыс. голов КРС

Агрохолдинг «Зеленая Долина» возведет крупнейший в Европе молочный комплекс

Агроинвестор
Боспор: царство греков и варваров Боспор: царство греков и варваров

Почему события, происходившие в Боспоре, имели для Афин большое значение?

Наука и жизнь
Наука в фантастике: эпизоды истории Наука в фантастике: эпизоды истории

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

Наука и жизнь
Математические фронты Великой Отечественной войны Математические фронты Великой Отечественной войны

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

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

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

Агроинвестор
Открыть в приложении