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

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

Заповедные новости Заповедные новости

Свежие новости из особо охраняемых территорий России

Наука и жизнь
Евпатория Евпатория

Евпатория — город, существующий во многих измерениях

Знание – сила
Она вышивает мечты Она вышивает мечты

Самая яркая звезда на небосклоне высокой моды Поднебесной — талантливая Гуо Пей

Y Magazine
Что скрывается за модным словом «роялти» ? Что скрывается за модным словом «роялти» ?

Пассивный доход на интеллектуальной собственности: как работает роялти?

Наука и техника
Не всякая поганка — гриб Не всякая поганка — гриб

Почему красивых и изящных водоплавающих птиц назвали поганками?

Наука и жизнь
Космическая пыль в междупланетном пространстве Космическая пыль в междупланетном пространстве

Наука в годы войны: астроном Фесенков об астероидах и космической пыли

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

Как масло для дерева может стать причиной пожара?

Наука и жизнь
Мускулы крылатой машины – система управления Мускулы крылатой машины – система управления

Как пилот заставляет слушаться машину в десятки тонн, контролируя ее в воздухе?

Наука и техника
Полет Fram2 Полет Fram2

Командиром этого полета был Ван Чунь – миллионер, оплативший полет участников

Наука и техника
Жабрей и зябра, они же пикульники Жабрей и зябра, они же пикульники

Пикульники — настоящие джентльмены среди растения, хотя и каждый со своим нравом

Наука и жизнь
Рассказ солдата Рассказ солдата

Воспоминания Георгия Немчинова о войне на передовой

Знание – сила
Устричный гриб, его собратья и однофамильцы Устричный гриб, его собратья и однофамильцы

Где растёт вёшенка и кто её лесные «однофамильцы»

Наука и жизнь
Мост в небесах Мост в небесах

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

Знание – сила
Мир экзопланет: что для космоса «норма»? Мир экзопланет: что для космоса «норма»?

Уже можно говорить о планетах необычных. Как выглядят «обычные» – установлено

Наука и техника
В зоне степей и полупустынь В зоне степей и полупустынь

Сергей Богун о проблемах защиты редких степных видов

Знание – сила
Мысль как вечное движение, – или «Что такое интеллигенция»… Мысль как вечное движение, – или «Что такое интеллигенция»…

Беседа с Константином Кедровым о немецком философе Гегеле

Знание – сила
Есть ли жизнь на Марсе? Есть ли жизнь на Марсе?

Пройдемся по имеющимся фактам в вопросе о жизни на Марсе

Наука и техника
Когда ещё был лес… Когда ещё был лес…

Рассказ Саши Тэмлейн «Когда ещё был лес…»

Наука и жизнь
Мост – это мир со своими законами Мост – это мир со своими законами

Наш сегодняшний разговор – не о фантастике, а о фантастических мостах

Знание – сила
Убить Лумумбу Убить Лумумбу

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

Знание – сила
Молодой Цезарь Молодой Цезарь

Карьера Цезаря могла бы оборваться, едва начавшись, равно как и его жизнь...

Знание – сила
Безмолвный пациент, или вакцинация в аквакультуре Безмолвный пациент, или вакцинация в аквакультуре

Кто, как и зачем вакцинирует рыб в аквахозяйствах?

Наука и жизнь
«Дом А. Ф. Лосева» «Дом А. Ф. Лосева»

О том, как создавалась уникальная структура Дома Лосева

Знание – сила
Социология утопии, или Почему у Стругацких в их «Мире Полудня» нет котиков и попугайчиков Социология утопии, или Почему у Стругацких в их «Мире Полудня» нет котиков и попугайчиков

Почему на Прекрасной Земле Будущего полностью отсутствуют домашние питомцы

Знание – сила
Наука в фантастике: эпизоды истории Наука в фантастике: эпизоды истории

Сказочная повесть — фантастика с просветительской задачей

Наука и жизнь
Современные подводные лодки постройки Швеции и Нидерландов Современные подводные лодки постройки Швеции и Нидерландов

Швеция и Нидерланды: как изменилась отечественная школа подводного судостроения

Наука и техника
Дрофа – степной реликт Дрофа – степной реликт

Все ли знают о самой крупной птице России? Это дрофа

Знание – сила
Узорочье древних славянок Узорочье древних славянок

Древняя мода: как выглядела одежда на Руси до XIII века

Знание – сила
В ожидании Меркурия В ожидании Меркурия

Меркурий единственная планета Солнечной системы без атмосферы с магнитным полем

Наука и жизнь
Код нации Код нации

Генетическая база данных поможет бороться с наследственными заболеваниями

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