C&SA | Contents

Volume 61 >>> № 4 July — August 2025

-->

DOI 10.34229/KCA2522-9664.25.4.3

UDC 004.89

V.K. Zadiraka¹, I.V. Shvidchenko²

¹ V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

zvk140@ukr.net

² V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

inetsheva@gmail.com

Elements of the general theory of optimal algorithms

Abstract. A general scheme for estimating the total error of a computational algorithm is presented. Optimal algorithms are constructed under the conditions of the most complete use of available information about the problem. Reserves for optimization of calculations are considered.

Keywords: computational algorithm, approximate solution, error of approximate solution, optimization of algorithms, reserves of calculations optimization, computer technologies.

full text

REFERENCES

1. Ivanov V.V. Methods of Computation on Electronic Computers: Reference Manual. Kyiv: Naukova Dumka, 1986. 584 pp.

2. Gavurin M.N. Lectures on Computational Methods. Moscow: Nauka, 1971. 248 pp.

3. Ivanov V.V., Babich M.D., Berezovsky A.I., Besarab P.N., Zadiraka V.K., Lyudvichenko V.A. Characteristics of problems, algorithms, and computers in computational mathematics software complexes. Kyiv: Institute of Cybernetics of the Academy of Sciences of the UkrSSR, 1984. 54 pp. (Preprint / IC AS UkrSSR: 84–36).

4. Tikhonov A.N. On the regularization of ill-posed problems. Doklady AN SSSR. 1963. Vol. 153, No. 1. pp. 49–52.

5. Gladky V.S. Probabilistic Computational Models. Moscow: Nauka, 1973. 300 pp.

6. Danilchenko L.S., Lyudvichenko V.A. On obtaining a priori estimates of solution time for problems in Fortran programs. Programming. 1988. No. 5. pp. 56–60.

7. Zadiraka V.K. Theory of Computation of Fourier Transform. Kyiv: Naukova Dumka, 1983. 215 pp.

8. Chentsov N.N. Statistical Decision Rules and Optimal Inferences. Moscow: Nauka, 1972. 520 pp.

9. Tikhonov A.N., Ivanov V.K., Lavrentyev M.M. Ill-posed Problems. In: Partial Differential Equations: Proceedings of a Symposium Dedicated to the 60th Anniversary of Academician Sobolev. Moscow: Nauka, 1970. pp. 224–238.

10. Traub J., Wozniakowski H. General Theory of Optimal Algorithms. Moscow: Mir, 1983. 382 pp.

11. Traub J., Wozniakowski H. Information, Uncertainty, Complexity. Moscow: Mir, 1988. 183 pp.

12. Zadiraka V.K., Tereshchenko A.M. Computer arithmetic of multi-digit numbers in sequential and parallel calculation models. Kyiv: Naukova Dumka, 2021. 152 pp. URL: https://books-nasu.org.ua/computer-arithmetics-of-multi-digits-numbers-in-sequential-and-parallel-calculation-models/.

13. Sergienko I.V., Zadiraka V.K., Lytvyn O.M. Elements of the general theory of optimal algorithms. Springer, 2021. 378 pp. https://doi.org/10.1007/978-3-030-90908-6.

14. Zadiraka V.K., Khimich O.M., Shvidchenko I.V. Models of computer computations. Cybernetics and Computer Technologies. 2022. No. 2. pp. 38–51. https://doi.org/10.34229/2707-451X.22.2.4.

15. Zadiraka V.K., Luts L.V., Shvidchenko I.V. Theory of computing integrals of rapidly oscillating functions. Kyiv: Naukova Dumka, 2023. 472 pp. https://doi.org/10.15407/978-966-1843-3.

16. Zadiraka V.K., Tereshchenko A.M., Shvidchenko I.V. Multi-digit arithmetic in sequential, parallel, and quantum computation models. Physical-Mathematical Modeling and Information Technologies. 2023. Issue 36. pp. 87–91. https://doi.org/10.15407/10.15407/fmmit2023.36.087.

17. Zadiraka V.K., Shvidchenko I.V. Methods for dealing with rounding error accumulation in solving transcomputational complexity problems. Cybernetics and Computer Technologies. 2024. No. 2. pp. 47–56. https://doi.org/10.34229/2707-451X.24.2.5.

18. Zadiraka V.K., Tereshchenko A.M., Shvidchenko I.V. S-word arithmetic and high-precision computations. Mathematical and Computer Modeling. Series: Physical-Mathematical Sciences. 2024. Issue 25. pp. 70–82. https://doi.org/10.32626/2308-5878.2024-25.70-82.