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

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

Арктическую Сибирь объединили собачьи упряжки Арктическую Сибирь объединили собачьи упряжки

Собачьи упряжки используют в Восточно-Сибирской Арктике уже 9 тысяч лет

Наука и жизнь
На аллеях Аполлона На аллеях Аполлона

Остафьево: образ места, где всё буквально дышит поэзией

Знание – сила
Слово редактора Слово редактора

На самом деле, нет более открытых миру людей, чем яхтсмены

Y Magazine
Любовь к животным и санкции Любовь к животным и санкции

Почему рынок кормов — перспективное направление для инвестиций

Агроинвестор
Поговорим о космологии Поговорим о космологии

Пять работ, посвященных космологии, с комментариями специалиста

Знание – сила
Динозавры за Полярным кругом Динозавры за Полярным кругом

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

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

Как в СССР подчинили фантастику пропаганде социалистических достижений

Наука и жизнь
«Позеленение» Арктики: как его оценить и о чём оно свидетельствует «Позеленение» Арктики: как его оценить и о чём оно свидетельствует

Как арктические экосистемы приспосабливаются к изменениям климатических условий

Наука и жизнь
Болотные семафоры Болотные семафоры

Дупеля летят к нам из жарких поясов экваториальной Африки...

Наука и жизнь
Наука под знаком «Аненербе» Наука под знаком «Аненербе»

Наука может прекрасно себя чувствовать и в тиранических режимах

Знание – сила
Тихая гавань русских литераторов Тихая гавань русских литераторов

Усадьбе Остафьево повезло, в ее облике с давних времен мало что менялось

Знание – сила
Удивительный трубкозуб Удивительный трубкозуб

Ожившей химерой с прошедших веков трубкозуба, шутя, обзывают

Знание – сила
Последняя загадка Пушкина Последняя загадка Пушкина

«Пушкин и Погорелое Городище» – тема, вынесенная на периферию пушкинистики

Знание – сила
Будет не жирно? Будет не жирно?

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

Агроинвестор
Палеонтологи СПбГУ проследили эволюцию мозга крокодилов Палеонтологи СПбГУ проследили эволюцию мозга крокодилов

Ученые создали 3D-модель мозга древних параллигаторов

Знание – сила
Экологическая модернизация Экологическая модернизация

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

Агроинвестор
Делянка лирохвоста Делянка лирохвоста

Большая птица-лира живет во влажных лесах восточной Австралии и Тасмании

Знание – сила
Бизнес на энтузиазме Бизнес на энтузиазме

Перспективы мясного скотоводства в России неоднозначные

Агроинвестор
Июньская метель снежноцвета Июньская метель снежноцвета

Снежноцветы считаются красивейшими деревьями, и с этим трудно не согласиться

Наука и жизнь
На «зеленой» волне На «зеленой» волне

Какие экологические технологии внедряют отечественные аграрии

Агроинвестор
Испанские авианосцы на мировом рынке Испанские авианосцы на мировом рынке

Что помогло определиться с основными требованиями к универсальному авианосцу

Наука и техника
«Нечестная» игра Баше «Нечестная» игра Баше

Как найти выигрышную стратегию в игре Баше?

Наука и жизнь
У эволюции нет конкретной цели, но есть результат У эволюции нет конкретной цели, но есть результат

Как происходит видообразование, с чего начинается и через какие этапы проходит

Наука и жизнь
Недолгий триумф «арийской физики» Недолгий триумф «арийской физики»

В какой тупик может завести себя наука, если станет служанкой нацизма

Знание – сила
Наука и жизнь. Архив: 1941—1945 годы Наука и жизнь. Архив: 1941—1945 годы

О чем писали в журнале «Наука и жизнь» в годы Великой Отечественной войны?

Наука и жизнь
Художники Художники

Рассказ Александра Маркова «Художники»

Знание – сила
«Кто богат детьми, богат и любовью, а любовь всего светлее»: Н.М. Карамзин – отец семейства «Кто богат детьми, богат и любовью, а любовь всего светлее»: Н.М. Карамзин – отец семейства

Николай Карамзин известен как «первый наш историк и последний летописец»

Знание – сила
Самое древнее чувство Самое древнее чувство

Как у животных представлено чувства обоняния и вкуса

Наука и жизнь
Что «видели» астероиды? Что «видели» астероиды?

Чем астероиды интересны астрономам?

Наука и жизнь
Книга как искусство Книга как искусство

На протяжении долгих веков книга являлась главным хранителем информации

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