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

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

Фотосинтез — «игра с огнём» для растения Фотосинтез — «игра с огнём» для растения

Каким образом свет «питает» растение и как вызывает химические реакции?

Наука и жизнь
Академик Петр Чумаков: вирусы позволяют увидеть раковые клетки и сформировать иммунный ответ Академик Петр Чумаков: вирусы позволяют увидеть раковые клетки и сформировать иммунный ответ

Вирусы дают надежду в лечении самых злокачественных видов рака

Наука
Биология эльфов Биология эльфов

Чем эльфам пришлось бы «пожертвовать» в обмен на вечную жизнь?

Вокруг света
Жабрей и зябра, они же пикульники Жабрей и зябра, они же пикульники

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

Наука и жизнь
Китайский с нуля Китайский с нуля

Сложно ли выучить новый язык и как это сделать самостоятельно

РБК
Мост в небесах Мост в небесах

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

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

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

Знание – сила
Причудливая лилия кардиокринум Причудливая лилия кардиокринум

Что помогает садоводам-любителям выращивать редкий кардиокринум?

Наука и жизнь
Политика с открытым кодом Политика с открытым кодом

Какие факторы определяют успех Китая в индустрии искусственного интеллекта

РБК
Земля тысячи королей Земля тысячи королей

Как в Камеруне реалии современности переплетаются с наследием древности

Вокруг света
По законам моды По законам моды

Почему предпочтения в одежде так сильно меняются из поколения в поколение?

Вокруг света
Генеральная уборка Генеральная уборка

Как РГО старается уменьшить следы антропогенного воздействия

Вокруг света
Убить Лумумбу Убить Лумумбу

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

Знание – сила
Дрофа – степной реликт Дрофа – степной реликт

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

Знание – сила
На Сахалине бамбук не курят На Сахалине бамбук не курят

Аккумуляторные батареи можно собрать из водорослей и высокорослых злаков

Наука
Есть ли жизнь на Марсе? Есть ли жизнь на Марсе?

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

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

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

Наука и техника
Наталья Зубаревич: «Массовый переезд россиян на Дальний Восток пока нечем мотивировать» Наталья Зубаревич: «Массовый переезд россиян на Дальний Восток пока нечем мотивировать»

Какие барьеры сильнее всего удерживают российский экспорт и импорт

РБК
Молодой Цезарь Молодой Цезарь

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

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

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

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

Байкало-Амурская магистраль — детище русско-японской и последующих войн

Наука
Чтобы изучать Вселенную, надо выходить в космос Чтобы изучать Вселенную, надо выходить в космос

Институт астрономии РАН запустит УФ-обсерваторию и создаст лунную базу

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

Как Индия стала одной из ведущих IT-стран мира и каковы ее планы на будущее

РБК
Атлас будущего Атлас будущего

Кто станет «человеческим паркетом» и кого ИИ оставит без работы?

Вокруг света
Теория поколений Теория поколений

Как появились люди X, Y, Z, альфа и чем они отличаются в разных странах?

Вокруг света
Мир экзопланет: что для космоса «норма»? Мир экзопланет: что для космоса «норма»?

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

Наука и техника
Гипотеза бабушек Гипотеза бабушек

Зачем животным старшие поколения и как они передают опыт

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

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

Наука и жизнь
Семь крапив Семь крапив

В России окультуривают ценное, полезное, но очень жгучее растение

Наука
Человек и мир агентов искусственного интеллекта Человек и мир агентов искусственного интеллекта

Три сценария для поддержания человеческой уникальности в мире ИИ

Наука
Открыть в приложении