Методы эффективной генерации машин Тьюринга, решающих NP-трудные задачи
https://doi.org/10.21285/2227-2917-2024-3-556-569
EDN: QJQXZL
Аннотация
Целью исследования является анализ программной реализации концепции генерации машин Тьюринга, решающих NP-трудные задачи. Формулируется математическая постановка проблемы генерации машин, представленная как решение задач ресурсного планирования для удобства адаптации к программным решениям, используемым для задач проектирования расписания занятий или, более широко, для задач сетевого планирования. Представлены программные решения представления данных, частично использующие технические решения для задачи проектирования расписания занятий. Приведено описание основных стратегий (процедурная семантика методов) сокращения переборов (глубокий возврат, «смотри вперед» и др.). В них также используются технические решения для задачи проектирования расписания занятий и других стратегий (например, применение оракула), которые не использовались для задачи проектирования расписания занятий. Целью исследования является анализ промежуточных результатов программной реализации концепции генерации машин Тьюринга, решающих NP-сложные задачи. Обсуждаются дальнейшие планы по разработке программного комплекса для генерации машин Тьюринга, который может стать открытой платформой для обучения студентов теории алгоритмов и информационным технологиям, проведения всеми желающими экспериментов по определению не полиномиальной сложности решения определенной серии NP-трудных задач, сгенерированными машинами Тьюринга.
Об авторах
В. И. Мартьянов
Иркутский национальный исследовательский технический университет ; Байкальский государственный университет ; Иркутский государственный университет
Россия
Россия
Мартьянов Владимир Иванович, д.ф-м.н., профессор кафедры автомобильных дорог
Author ID: 2477
664074, г. Иркутск, ул. Лермонтова, 83
664003, г. Иркутск, ул. Ленина, 11
664003, г. Иркутск, ул. Карла Маркса, 1
А. С. Волков
Байкальский государственный университет
Россия
Россия
Волков Андрей Сергеевич, аспирант
664003, г. Иркутск, ул. Ленина, 11
Список литературы
1. Мартьянов В.И. Проект программного комплекса генерации машин Тьюринга, решающих NP- трудные задачи // Известия вузов. Инвестиции. Строительство. Недвижимость. 2023. Т. 13. № 2. С. 285– 297. https://doi.org/10.21285/2227-2917-2023-2-285-297. EDN: UAEWDT.
2. Мартьянов В.И. Логико-эвристические методы сетевого планирования и распознавание ситуаций // Проблемы управления и моделирования в сложных системах. Самара, 2001. С. 203–215.
3. Мартьянов В.И., Архипов В.В., Каташевцев М.Д., Пахомов Д.В. Обзор приложений логико-эвристических методов решения комбинаторных задач высокой сложности // Современные технологии. Системный анализ. Моделирование. 2010. № 4 (28). С. 205–211. EDN: NRBKXP.
4. Мартьянов В.И., Сухорутченко В.В., Окунцов В.В. Планирование информационных потоков в иерархической системе // Прикладные системы. М.: ИАП РАН, 1992. С. 46–58.
5. Лагутенков А.В. Криптовалюты. Правила применения // Наука и жизнь. 2018. № 2. С. 22–26.
6. Kharpal A. All You Need to Know About the Top 5 Cryptocurrencies // Yahoo! Finance. 2017. Режим доступа: https://finance.yahoo.com/news/know-top-5-cryptocurrencies-093231173.html (дата обращения: 20.05.2024).
7. Wilson-Nunn D., Zenil H. On the Complexity and Behaviour of Cryptocurrencies Compared to Other Markets // Cornell University: arxiv. 2014. P. 1–16. https://doi.org/10.48550/arXiv.1411.1924.
8. Еремеев А.В., Заозерская Л.А., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. 2000. Т. 7. № 2. С. 22–46. EDN: IBBFDL.
9. Мартьянов В.И., Вяткин И.В., Могильницкий Э.Ю. Теоретический и реализационный аспекты некоторых классов задач сетевого управления // Проблемы управления и моделирования в сложных системах. Самара, 1999. С. 203–208.
10. Мартьянов В.И. NP-трудные задачи: автоматическое доказательство теорем и машины Тьюринга // Baikal Research Journal. 2021. Т. 12. № 4. С. 1–9. https://doi.org/10.17150/2411-6262.2021.12(4).11. EDN: HJXXGO.
11. Кнут Д.Э. Искусство программирования для ЭВМ: Основные алгоритмы. М.: Мир, 1976. 736 с.
12. Кнут Д.Э. Искусство программирования для ЭВМ: Сортировка и поиск. М.: Мир, 1978. 848 с.
13. Мартьянов В.И., Кулик Н.С., Пахомов Д.В., Большаков Э.А. Проект системы управления региональной сетью автомобильных дорог (СУРАД) Иркутской области // Вестник Иркутского государственного технического университета. 2014. № 4 (87). С. 118–183. EDN: SBNFNJ.
14. Кулик Н.С., Мартьянов В.И., Пахомов Д.В. Построение графа автомобильных дорог для системы взимания платы с большегрузного транспорта // Вестник Иркутского государственного технического университета. 2016. № 4 (111). С. 96–101. https://doi.org/10.21285/1814-3520-2016-4-96-101. EDN: VVSOFF.
15. Мартьянов В.И., Пахомов Д.В., Архипов В.В. Сетевое планирование содержания сети автомобильных дорог Иркутской области // Новые технологии в инвестиционно-строительной сфере и ЖКХ: сб. науч. трудов. (г. Иркутск, 14 апреля 2005 г.). Иркутск, 2005. Т. 1. С. 123–129.
16. Мартьянов В.И. Теоретико-множественные модели данных в задаче расчета вторичных структур РНК // System Analysis and Mathematical Modeling. 2022. Т. 4. № 4. С. 343–357. https://doi.org/10.17150/2713-1734.2022.4(4).343-357. EDN: VUNLFX.
17. Мартьянов В.И., Корольков Ю.Д. Теоретико-множественные модели сложных систем и алгоритмы интеллектуальной поддержки. Иркутск: Изд. дом БГУ, 2020. 125 с.
18. Martyanov V.I., Katashevtsev M.D. Computer Processing of Distorted Video Sequences Obtained by Mobile Road Laboratories // IOP Conference Series: Materials Science and Engineering. 2019. Vol. 667. Iss. 1. P. 1–9. http://doi.org/10.1088/1757-899X/667/1/012060.
19. Мартьянов В.И. Теоретико-множественный анализ организации данных учебного процесса и алгоритмы проектирования расписания с элементами искусственного интеллекта // Известия Байкальского государственного университета. 2020. Т. 30. № 4. С. 575–585. https://doi.org/10.17150/2500-2759.2020.30(4).575-585. EDN: QKOCYX.
20. Щербина О.А. Удовлетворение ограничений и программирование в ограничениях // Интеллектуальные системы. 2011. Т. 15. № 1-4. С. 53–170. EDN: PWUSTF.
21. Hentenryck van P. Constraint Satisfaction in Logic Programming. Cambridge: The MIT Press, 1989. 224 p.
22. Стюарт И. Величайшие математические задачи. М.: Альпина нон-фикшн, 2015. 584 с.
23. Разборов А.А. Алгебраическая сложность. М.: Московский центр непрерывного математического образования, 2016. 32 с.
24. Fortnow L. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton: Princeton University Press. 2017. 176 p.
25. Leeuwen van J. Handbook of Theoretical Computer Science. Cambridge: The MIT Press, 1990. 1014 p.
26. Knuth D.E. Postscript about NP-hard problems // ACM SIGACT News. 1974. Vol. 6. Iss. 2. P. 15–16. https://doi.org/10.1145/1008304.1008305.
27. Aaronson S. The Scientific Case for P≠NP // Shtetl-Optimized. 2014. Режим доступа: https://scot-taaronson.blog/?p=1720 (дата обращения: 20.05.2024).
28. Aaronson S. Quantum Computing Since Democritus Lecture 6: P, NP, and Friends // Shtetl-Optimized. 2006. Режим доступа: https://scottaaronson.blog/?p=149 (дата обращения: 20.05.2024).
29. Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. New York: John Wiley & Sons, 1985. 476 p.
30. Wegener I. Complexity Theory: Exploring the Limits of Efficient Algorithms. New York: Springer, 2005. 320 p.
Рецензия
Для цитирования:
Мартьянов В.И., Волков А.С. Методы эффективной генерации машин Тьюринга, решающих NP-трудные задачи. Известия вузов. Инвестиции. Строительство. Недвижимость. 2024;14(3):556-569. https://doi.org/10.21285/2227-2917-2024-3-556-569. EDN: QJQXZL
For citation:
Martyanov V.I., Volkov A.S. Methods for efficient generation of Turing machines to solve NP-hard problems. Izvestiya vuzov. Investitsii. Stroitelstvo. Nedvizhimost. 2024;14(3):556-569. (In Russ.) https://doi.org/10.21285/2227-2917-2024-3-556-569. EDN: QJQXZL
Просмотров:
69
Послать статью по эл. почте 