The article presents the results of a study aimed at expanding the theoretical basis in the field of real-time computing. The issues considered include: defining indicators of computational complexity in real time, a methodology for their quantitative assessment, identifying ways to achieve the computability of algorithms in real time, and formalizing approaches to the optimal technical implementation of real-time computing systems. The research is based on existing concepts in algorithm theory and computation theory, including real-time computation. Significant new scientific results of the research include: the introduction, along with the known indicators of temporal and spatial computational complexity, of an additional indicator of configuration computational complexity, necessary for assessing computational complexity in real time; the confirmation of the possibility of controlling temporal, spatial, and configuration complexity within the framework of a given algorithm functional solely by changing the number of computation execution threads; theoretical justification of the possibility of reducing the execution time of the configuration algorithm from exponential to polynomial or even linear by condensing the initial graph of the algorithm with the formation of strongly connected components of a set of actor functions and obtaining as a result an acyclic directed graph, whose topological sorting can be performed in linear time; determination of approaches to the optimal technical implementation of the algorithm with a given configuration, including in the form of an integrated circuit with wiring optimized based on the solution of Steiner's rectangular problem.
1. Gribkov A.A. Human Beings in a Civilization of Cognitive Technologies. Philosophy and Culture. 2024;(1):22–33. (In Russ.). https://doi.org/10.7256/2454-0757.2024.1.69678
2. Zelenskiy A.A., Kuznetsov A.P., Ilyukhin Yu.V., Gribkov A.A. Feasibility of Motion Control of Industrial Robots, CNC Machine Tools and Mechatronic Systems. Part 2. Vestnik Mashinostroeniya. 2023;102(3):213–220. (In Russ.). 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. Uemov A.I. Sistemnyi podkhod i obshchaya teoriya sistem. Moscow: "Mysl'"; 1978. 272 p. (In Russ.).
5. Gribkov A.A. Evolutionary Growth of Complexity of Systems. Part 2. Complexity of Systems and Entropy. Modern Science: Actual Problems of Theory and Practice. Series of "Cognition". 2023;(6):68–72. (In Russ.).
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. Zelenskii A.A., Gribkov A.A. An Importance of the Portability Factor for Configuring the Cycle of Real-Time Actuator Control System. Modeling, Optimization and Information Technology. 2025;13(1). (In Russ.). 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. Cormen Th.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms. Moscow: Izdatel'skii dom "Vil'yams"; 2005. 1293 p. (In Russ.).
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. Gordeev E.N., Tarastsov O.G. The Steiner Problem: A Survey. Diskretnaya Matematika. 1993;5(2):3–28. (In Russ.).
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. Lisin A.V., Faizullin R.T. Heuristic Algorithm for Finding Approximate Solution of Steiner Problem Based on Physical Analogies. Computer Optics. 2013;37(4):503–510. (In Russ.). 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. Bagov M.A., Kudaev V.C. Conversion of Terminal Net into Steiner Network. News of the Kabardino-Balkarian Scientific Center of RAS. 2015;(6–2):31–37. (In Russ.).
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. Tereshchuk V.S., Ferenets A.V., Fedorov E.Yu. Osobennosti razvodki slozhnykh elektricheskikh tsepei letatel'nykh apparatov. In: Poisk effektivnykh reshenii v protsesse sozdaniya i realizatsii nauchnykh razrabotok v rossiiskoi aviatsionnoi i raketno-kosmicheskoi promyshlennosti: Mezhdunarodnaya nauchno-prakticheskaya konferentsiya: Volume IV, 05–08 August 2014, Kazan, Russia. Kazan: Izdatel'stvo Kazanskogo gosudarstvennogo tekhnicheskogo universiteta; 2014. P. 109–111. (In Russ.).
