Научный журнал Байкальского государственного университета
System Analysis &
Mathematical Modeling
Издается с 2019 года
Menu
РусскийEnglish

Информация о статье

Название статьи:

Применение многопоточных вычислений при генерации машин Тьюринга, решающих NP-трудные задачи

Авторы:
Мартьянов В.И., доктор физико-математических наук, старший научный сотрудник, Лаборатория математического моделирования, Байкальский государственный университет, г. Иркутск, Российская Федерация, martvliv@mail.ru
Для цитирования:
Мартьянов В.И. Применение многопоточных вычислений при генерации машин Тьюринга, решающих NP-трудные задачи / В.И. Мартьянов. — DOI 10.17150/2713-1734.2025.7(3).297-323. — EDN BEMZFK // System Analysis & Mathematical Modeling. — 2025. — Т. 7, № 3. — С. 297–323.
В рубрике:
МАТЕМАТИЧЕСКИЕ НАУКИ
Год: 2025 Том: 7 Номер журнала: 3
Страницы: 297-323
Тип статьи: Научная статья
УДК: 519.6(082)
DOI: 10.17150/2713-1734.2025.7(3).297-323
Аннотация:
Рассматриваются вопросы создания программного комплекса формирования Детерминированных Машин Тьюринга (DМТ), решающих NP-трудные задачи, с использованием многопоточных вычислений. Рассматривается формализация постановки задач формирования машин Тьюринга, представленная как решение проблемы ресурсного планирования для адаптации программных решений, разработанных для генерации расписаний занятий учебных заведений (классический пример задач сетевого планирования). Разработаны технические решения организации данных для многопоточных вычислений, использующие технологические установки представления задач сетевого планирования. Описаны модернизации стратегий (процедурная семантика) уменьшения переборов (неполное восстановление среды точки возврата, «чем хуже, тем лучше» и др.) при использовании многопоточных вычислений. Следует отметить, что и модернизированные стратегии используют некоторые технические приемы решения задач сетевого планирования, а также ряда иных приемов (например, применение оракула), которые не использовались для задач сетевого планирования. В статье подведен промежуточный итог применения программного комплекса с многопоточными вычислениями, который реализует концепцию генерации машин Тьюринга, решающих NP-сложные задачи. Рассмотрены планы применения многопоточных вычислений для создания комплекса программ для формирования машин Тьюринга, которые могут реализовать открытую платформу для обучения теории алгоритмов и информационным технологиям, а также проведения испытаний, доказывающих не полиномиальную алгоритмическую сложность расчета серии NP-трудных задач (ранее сгенерированными машинами Тьюринга).
Ключевые слова: задачи сетевого планирования, стратегии уменьшения переборов, программирование в ограничениях, многопоточные вычисления, неполное восстановление среды точки возврата
Информация о статье: Дата поступления: 17 июня 2025 г.; дата принятия к публикации: 27 сентября 2025 г.; дата онлайн-размещения: 23 октября 2025 г.
Скачать полный текст статьи
Список цитируемой литературы:
  • Мартьянов В.И. Методы эффективной генерации машин Тьюринга, решающих NP-трудные задачи / В.И. Мартьянов, А.С. Волков. - DOI 10.21285/2227-2917-2024-3-556-569. - EDN QJQXZL // Известия вузов. Инвестиции. Строительство. Недвижимость. - 2024. - Т. 14, № 3 (50). - С. 556-569.
  • Мартьянов В.И. Проект программного комплекса генерации машин Тьюринга, решающих NP-трудные задачи / В.И. Мартьянов. - DOI 10.21285/2227-2917-2023-1-285-297. - EDN UAEWDT // Известия вузов. Инвестиции. Строительство. Недвижимость. - 2023. - Т. 13, № 2 (45). - С. 285-297.
  • Мартьянов В.И. Логико-эвристические методы сетевого планирования и распознавание ситуаций / В.И. Мартьянов // Проблемы управления и моделирования в сложных системах. - Самара, 2001. С. 203-215.
  • Обзор приложений логико-эвристических методов решения комбинаторных задач высокой сложности / В.И. Мартьянов, В.В. Архипов, М.Д. Каташевцев, Д.В. Пахомов. - EDN NRBKXP // Современные технологии. Системный анализ. Моделирование. - 2010. - № 4 (28). - С. 205-211.
  • Мартьянов В.И. Планирование информационных потоков в иерархической системе / В.И. Мартьянов, В.В. Сухорутченко, В.В. Окунцов // Прикладные системы. - Москва, 1992. - С. 46-58.
  • Лагутенков А.В. Криптовалюты. Правила применения / А.В. Лагутенков // Наука и жизнь. - 2018. - № 2. - С. 22-26.
  • Kharpal A. All You Need to Know About the Top 5 Cryptocurrencies / A. Kharpal // Yahoo! Finance. - 2017. - 14 December. - URL: https://finance.yahoo.com/news/know-top-5-cryptocurrencies-093231173.html.
  • Wilson-Nunn D. On the Complexity and Behaviour of Cryptocurrencies Compared to Other Markets / D. Wilson-Nunn, H. Zenil // Cornell University: arxiv. - 2014. - URL: https://doi.org/10.48550/arXiv.1411.1924.
  • Еремеев А.В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / А.В. Еремеев, Л.А. Заозерская, А.А. Колоколов. - EDN IBBFDL // Дискретный анализ и исследование операций. Серия 2. - 2000. - Т. 7, № 2. - С. 22-46.
  • Мартьянов В.И. Теоретический и реализационный аспекты некоторых классов задач сетевого управления / В.И. Мартьянов // Проблемы управления и моделирования в сложных системах : междунар. конф. Самара, 15-17 июня 1999 г. - Самара, 1999. - С. 203-208.
  • Мартьянов В.И. NP-трудные задачи: автоматическое доказательство теорем и машины Тьюринга / В.И. Мартьянов. - DOI 10.17150/2411-6262.2021.12(4).11. - EDN HJXXGO // Baikal Research Journal. - 2021. - Т. 12, № 4. - C. 11.
  • Кнут Д.Э. Искусство программирования для ЭВМ / Д.Э. Кнут. - Москва : Мир, 1976. - Т. 1: Основные алгоритмы. - 734 c.
  • Кнут Д.Э. Искусство программирования для ЭВМ / Д.Э. Кнут. - Москва : Мир, 1978. - Т. 3: Сортировка и поиск. - 848 с.
  • Проект системы управления региональной сетью автомобильных дорог (СУРСАД) Иркутской области / В.И. Мартьянов, Н.С. Кулик, Д.В. Пахомов, Э.А. Большаков. - EDN SBNFNJ // Вестник Иркутского государственного технического университета. - 2014. - № 4 (87). - С. 118-123.
  • Кулик Н.С. Построение графа автомобильных дорог для системы взимания платы с большегрузного транспорта / Н.С. Кулик, В.И. Мартьянов, Д.В. Пахомов. - DOI 10.21285/1814-3520-2016-4-96-101. - EDN VVSOFF // Вестник Иркутского государственного технического университета. - 2016. - № 4 (111). - С. 96-101.
  • Мартьянов В.И. Сетевое планирование содержания сети автомобильных дорог Иркутской области / В.И. Мартьянов, Д.В. Пахомов, В.В. Архипов // Новые технологии в инвестиционно-строительной сфере и ЖКХ : сб. науч. трудов конф., Иркутск, 14 апр. 2005 г. - Иркутск, 2005. - Т. 1. - С. 123-129.
  • Мартьянов В.И. Теоретико-множественные модели данных в задаче расчета вторичных структур РНК / В.И. Мартьянов. - DOI 10.17150/2713-1734.2022.4(4).343-357. - EDN VUNLFX // System Analysis and Mathematical Modeling. - 2022. - Т. 4, № 4. - С. 343-357.
  • Мартьянов В.И. Теоретико-множественные модели сложных систем и алгоритмы интеллектуальной поддержки / В.И. Мартьянов, Ю.Д. Корольков. - Иркутск : Изд. дом БГУ, 2020. - 125 с.
  • Martyanov V.I. Computer Processing of Distorted Video Sequences Obtained by Mobile Road Laboratories / V.I. Martyanov, M.D. Katashevtsev. - DOI 10.1088/1757-899X/667/1/012060 // IOP Conference Series: Materials Science and Engineering. - 2019. - Vol. 667, iss. 1. - P. 1-9.
  • Мартьянов В.И. Теоретико-множественный анализ организации данных учебного процесса и алгоритмы проектирования расписания с элементами искусственного интеллекта / В.И. Мартьянов. - DOI 10.17150/2500-2759.2020.30(4).575-585. - EDN QKOCYX // Известия Байкальского государственного университета. - 2020. - Т. 30, № 4. - С. 575-585.
  • Щербина О.А. Удовлетворение ограничений и программирование в ограничениях / О.А. Щербина. - EDN PWUSTF // Интеллектуальные системы. - 2011. - Т. 15, № 1-4. - С. 53-170.
  • Hentenryck van P. Constraint Satisfaction in Logic Programming / van P. Hentenryck. - Cambridge : The MIT Press, 1989. - 224 p.
  • Стюарт И. Величайшие математические задачи / И. Стюарт. - Москва : Альпина нон-фикшн, 2015. - 584 с.
  • Разборов А.А. Алгебраическая сложность / А.А. Разборов. - Москва, 2016. - 32 с.
  • Fortnow L. The Golden Ticket: P, NP, and the Search for the Impossible / L. Fortnow. - Princeton : Princeton University Press. 2017. - 176 p.
  • Leeuwen van J. Handbook of Theoretical Computer Science / van J. Leeuwen. Cambridge : The MIT Press, 1990. - 1014 p.