В статье излагаются результаты исследования, направленного на расширение теоретической базы в области вычислений в реальном времени. К числу рассматриваемых вопросов относятся: определение показателей вычислительной сложности в реальном времени, методология их количественной оценки, выявление способов достижения вычислимости алгоритмов в реальном времени, формализация подходов к оптимальной технической реализации вычислительных систем реального времени. Проведенные исследования опираются на существующие представления теории алгоритмов и теории вычислений, в том числе, вычислений в реальном времени. К числу значимых новых научных результатов проведенного исследования относятся: введение, наряду с известными показателями временной и пространственной вычислительной сложности, дополнительного показателя конфигурационной вычислительной сложности, необходимого для оценки вычислительной сложности в реальном времени; констатация возможности управления временной, пространственной и конфигурационной сложностью в рамках заданного функционала алгоритма исключительно за счет изменения числа потоков исполнения вычислений; теоретическое обоснование возможности снижения времени выполнения алгоритма конфигурирования с экспоненциального до полиномиального или даже линейного за счет конденсации исходного графа алгоритма с образованием из сильно связанных компонент совокупности функций-акторов и получения в результате ациклического ориентированного графа, топологическая сортировка которого выполнима за линейное время; определение подходов к оптимальной технической реализации алгоритма с заданной конфигурацией, в том числе, в виде интегральной схемы с разводкой, оптимизируемой на основе решения прямоугольной задачи Штейнера.
1. Грибков А.А. Человек в цивилизации когнитивных технологий. Философия и культура. 2024;(1):22–33. https://doi.org/10.7256/2454-0757.2024.1.69678
2. Зеленский А.А., Кузнецов А.П., Илюхин Ю.В., Грибков А.А. Реализуемость управления движением промышленных роботов, станков с ЧПУ и мехатронных систем. Часть 2. Вестник машиностроения. 2023;102(3):213–220. https://doi.org/10.36652/0042-4633-2023-102-3-213-220
3. Yamada H. Real-Time Computation and Recursive Functions Not Real-Time Computable. IRE Transactions on Electronic Computers. 1962;EC-11(6):753–760. https://doi.org/10.1109/TEC.1962.5219459
4. Уемов А.И. Системный подход и общая теория систем. Москва: «Мысль»; 1978. 272 с.
5. Грибков А.А. Эволюционный рост сложности систем. Часть 2. Сложность систем и энтропия. Современная наука: актуальные проблемы теории и практики. Серия: Познание. 2023;(6):68–72.
6. Asperti A. A Formal Proof of Borodin-Trakhtenbrot's Gap Theorem. In: Certified Programs and Proofs: Third International Conference, CPP 2013: Proceedings, 11–13 December 2013, Melbourne, VIC, Australia. Cham: Springer; 2013. P. 163–177. https://doi.org/10.1007/978-3-319-03545-1_11
7. Зеленский А.А., Грибков А.А. Значение фактора портовости для конфигурирования цикла акторной системы управления реального времени. Моделирование, оптимизация и информационные технологии. 2025;13(1). https://doi.org/10.26102/2310-6018/2025.48.1.037
8. Bartlett M., Frisch A.M., Hamadi Yo., Miguel Ia., Tarim S.A., Unsworth Ch. The Temporal Knapsack Problem and Its Solution. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: Second International Conference, CPAIOR 2005, 31 May – 1 June 2005, Prague, Czech Republic. Berlin, Heidelberg: Springer; 2005. P. 34–48. https://doi.org/10.1007/11493853_5
9. Kahn A.B. Topological Sorting of Large Networks. Communications of the ACM. 1962;5(11):558–562. https://doi.org/10.1145/368996.369025
10. Кормен Т., Лейзерсон Ч., Ривест Р. Штайн К. Алгоритмы: построение и анализ. Москва: Издательский дом «Вильямс»; 2005. 1293 с.
11. Hong S., Rodia N.С., Olukotun K. On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs. In: SC '13: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, 17–21 November 2013, Denver, Colorado, USA. New York: Association for Computing Machinery; 2013. https://doi.org/10.1145/2503210.2503246
12. Tarjan R. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing. 1972;1(2):146–160. https://doi.org/10.1137/0201010
13. Gabow H.N. Path-Based Depth-First Search for Strong and Biconnected Components. Information Processing Letters. 2000;74(3–4):107–114. https://doi.org/10.1016/S0020-0190(00)00051-X
14. Bundy A., Wallen L. Breadth-First Search. In: Catalogue of Artificial Intelligence Tools. Berlin, Heidelberg: Springer; 1984. P. 13. https://doi.org/10.1007/978-3-642-96868-6_25
15. Hashemi M., Gong Sh., Ni J., Fan W., Prakash B.A., Jin W. A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation. In: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24), 03–09 August 2024, Jeju, South Korea. 2024. P. 8058–8066. https://doi.org/10.24963/ijcai.2024/891
16. Eswaran K.P., Tarjan R.E. Augmentation Problems. SIAM Journal on Computing. 1976;5(4):653–665. https://doi.org/10.1137/0205044
17. Гордеев Э.Н., Тарасцов О.Г. Задача Штейнера. Обзор. Дискретная математика. 1993;5(2):3–28.
18. Melzak Z.A. On the Problem of Steiner. Canadian Mathematical Bulletin. 1961;4(2):143–148. https://doi.org/10.4153/CMB-1961-016-2
19. Cockayne E.J. On the Efficiency of the Algorithm for Steiner Minimal Trees. SIAM Journal on Applied Mathematics. 1970;18(1):150–159. https://doi.org/10.1137/0118014
20. Лисин А.В., Файзуллин Р.Т. Эвристический алгоритм поиска приближённого решения задачи Штейнера, основанный на физических аналогиях. Компьютерная оптика. 2013;37(4):503–510. https://doi.org/10.18287/0134-2452-2013-37-4-503-510
21. Kou L., Markowsky G., Berman L. A Fast Algorithm for Steiner Trees. Acta Informatica. 1981;15(2):141–145. https://doi.org/10.1007/BF00288961
22. Багов М.А, Кудаев В.Ч. Преобразование терминальной сети в сеть Штейнера. Известия Кабардино-Балкарского научного центра РАН. 2015;(6–2):31–37.
23. Kahng A.B., Robins G. On Optimal Interconnections for VLSI. New York: Springer; 1995. 286 p. https://doi.org/10.1007/978-1-4757-2363-2
24. Терещук В.С., Ференец А.В., Федоров Е.Ю. Особенности разводки сложных электрических цепей летательных аппаратов. В сборнике: Поиск эффективных решений в процессе создания и реализации научных разработок в российской авиационной и ракетно-космической промышленности: Международная научно-практическая конференция: Том IV, 05–08 августа 2014 года, Казань, Россия. Казань: Издательство Казанского государственного технического университета; 2014. С. 109–111.
