DOI: https://doi.org/10.26089/NumMet.v26r436

Обзор методов описания структуры алгоритмов

Авторы

  • А. С. Антонов

Ключевые слова:

задача
метод
алгоритм
реализация
параллелизм
суперкомпьютер
AlgoWiki

Аннотация

Алгоритмы являются основой всего вычислительного процесса в рамках традиционной цепочки “задача–метод–алгоритм–реализация”, а эффективное использование их свойств, структуры, особенностей и характеристик может дать многократное сокращение времени их реализации на конкретной вычислительной системе. В данной обзорной статье рассматриваются методы, используемые для описания структуры вычислительных алгоритмов. Также в статье рассматриваются доступные в сети Интернет коллекции описаний алгоритмов, дается краткая характеристика, алгоритмы из каких областей и каким образом в них описываются.


Загрузки

Опубликован

2025-12-05

Выпуск

Том 26 (2025): Выпуск 4.

Раздел

Методы и алгоритмы вычислительной математики и их приложения

Автор

А. С. Антонов

Московский государственный университет имени М.В. Ломоносова, Научно-исследовательский вычислительный центр

• ведущий научный сотрудник

Библиографические ссылки

  1. C. B. Boyer, The Arabic Hegemony. A History of Mathematics (Second ed.) (Wiley, New York, 1991).
  2. D. Knuth, The Art of Computer Programming, vol.1. Fundamental Algorithms. 3d ed. (Addison-Wesley, Reading, Massachusetts, 1997).
  3. A. A. Markov, Theory of algorithms. Proc. of the Steklov Institute of Mathematics of the USSR Vol. 42. 3–375 (1954) [in Russian].
  4. A. N. Kolmogorov, V. A. Uspenskiy, “On the definition of an algorithm,” Russian Math. Surveys. 13 (4). 3–28 (1958).
    https://www.mathnet.ru/rm7453 Cited November 30, 2025.
  5. Philosophical Dictionary. 3rd ed. / Ed. M. M. Rosental (1975).
  6. Standards Coordinating Committee 10, Terms and Definitions. The IEEE Standard Dictionary of Electrical and Electronics Terms. J. Radatz, Ed. (IEEE, New York, 1996).
  7. Dictionary of Algorithms and Data Structures.
    https://xlinux.nist.gov/dads/.Cited November 30, 2025.
  8. I. A. Selivanova and V. A. Blinov, Fundamental algorithms in C++. Construction and analysis of data processing algorithms: a teaching aid (Ural University Publishing House, Ekaterinburg, 2015).
  9. N. D. Ugrinovich, Computer science and information technology. Textbook for grades 10–11. 3rd ed. (BINOM. Knowledge laboratory, Moscow, 2006) [in Russian].
  10. D. Woodhouse, G. Johnstone, et al., Computer science ( Milton, Qld., Jacaranda Wiley, 1984).
  11. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (The MIT Press, Cambridge, Massachusetts, 2001).
  12. S. S. Skiena, The Algorithm Design Manual. 2nd ed. (Springer, New York, 2008).
  13. R. Sedgewick, Algorithms in C++. Fundamentals/Data Structures/Sorting/Searching. 3rd ed. (Addison Wesley Longman, 1999).
  14. Open Encyclopedia of Algorithmic Features.
    https://algowiki-project.org Cited November 30, 2025.
  15. W. H. Press, Numerical Recipes 3rd Edition: The Art of Scientific Computing (Cambridge University Press, Cambridge, 2007).
    https://numerical.recipes/ Cited November 30, 2025.
  16. J. von Neumann, The Collected Works of John von Neumann, Volume V (Macmillan, New York, 1963).
  17. GOST 19.701-90.
    https://protect.gost.ru/document.aspx?control=7&id=137637 Cited November 30, 2025.
  18. ISO 5807: 1985.
    https://www.iso.org/ru/standard/11955.html Cited November 30, 2025.
  19. UML: Theory and Practice. Activity Diagram.
    https://it-gost.ru/articles/view_articles/96 Cited October 13, 2025.
  20. I. Nassi and B. Shneiderman, “Flowchart techniques for structured programming,” ACM SIGPLAN Notices 8 (8), 12–26 (1973).
    doi 10.1145/953349.953350
  21. E. L. Post, “Finite Combinatory Processes – Formulation I,” J. Symbolic Logic 1 (3), 103–105 (1936).
  22. A. M. Turing, “On Computable Numbers with an Application to the Entscheidungsproblem,” Proc. London Math. Society. ser.  2, vol. 42, 230–265. ibid. ser.  2, vol. 43, 544–546. (1937).
  23. A. Church, “An Unsolvable Problem of Elementary Number Theory,” American J. Math. 58 (2), 345–363 (1936).
  24. K. Asanović, R. Bodik, B. Catanzaro, et al., The Landscape of Parallel Computing Research: A View from Berkeley EECS Technical Report UCB/EECS-2006-183 (2006).
    https://people.eecs.berkeley.edu/ krste/papers/BerkeleyView.pdf Cited November 30, 2025.
  25. K. Asanović, R. Bodik, J. Demmel, et al., The Parallel Computing Laboratory at U.C. Berkeley: A Research Agenda Based on the Berkeley View Technical Report No. UCB/EECS-2008-23 (2008).
    https://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-23.pdf Cited November 30, 2025.
  26. M. I. Cole, Algorithmic Skeletons: Structured Management of Parallel Computation (MIT Press, 1991).
  27. F. A. Rabhi and S. Gorlatch (ed.), Patterns and Skeletons for Parallel and Distributed Computing (Springer, London, 2003).
    doi 10.1007/978-1-4471-0097-3
  28. N. Wirth, Algorithms and Data Structures. Oberon version + CD (1985. Oberon version: 2004).
  29. E. M. Reingold, Basic Techniques for Design and Analysis of Algorithms. Computer science handbook / ed. A. B. Tucker (Chapman and Hall/CRC, 2004).
  30. F. Gebali, Algorithms and Parallel Computing (Wiley, 2011).
    doi 10.1002/9780470932025
  31. V. V. Voevodin and Vl. V. Voevodin, The Parallel Computing (BHV-Petersburg, St. Petersburg, 2002) [in Russian].
  32. OpenMP: Home.
    https://www.openmp.org/ Cited November 30, 2025.
  33. MPI Forum.
    https://www.mpi-forum.org/ Cited November 30, 2025.
  34. CUDA Zone.
    https://developer.nvidia.com/cuda-zone Cited November 30, 2025.
  35. G. E. Blelloch, “Programming Parallel Algorithms,” Communications of the ACM 39 (3), 85–97 (1996).
  36. J. R. Smith, The Design and Analysis of Parallel Algorithms (Oxford University Press, Oxford, 1993).
  37. McConnell J., Fundamentals of Modern Algorithms. 2nd ed. (Moscow: Tekhnosfera, 2004) [in Russian].
  38. J. JáJá, An Introduction to Parallel Algorithms (Addison Wesley Longman Publishing Co., Inc., USA, 1992).
    doi 10.1016/S0898-1221(99)90305-X
  39. K. Mehlhorn and P. Sanders, Algorithms and Data Structures: The Basic Toolbox (Springer Science & Business Media, 2008).
    doi 10.1007/978-3-540-77978-0
  40. S. G. Akl, The Design and Analysis of Parallel Algorithms (Prentice Hall, London, 1989).
  41. M. H. Alsuwaiyel, Parallel algorithms (World Scientific Publishers, 2022).
    doi 10.1142/12744
  42. G. E. Blelloch and B. M. Maggs, Parallel Algorithms.Computer science handbook / ed. A.B. Tucker/ 2nd ed. pp. 232–272.(Carnegie Mellon University, Pittsburgh, 2004).
  43. H. Casanova, A. Legrand, and Y. Robert, Parallel Algorithms (CRC PRESS, New York, 2008).
  44. S. McConnell, Code Complete: A Practical Handbook of Software Construction, 2nd ed. (Microsoft Press, USA, 2004).
  45. V. D. Parondzhanov, Algorithmic Languages and Programming: DRAKON (Publishing house Yurait, Moscow, 2022) [in Russian].
  46. A. S. Antonov and N. I. Volkov, “Information Graph Visualization Using AlgoView Software Tool,” Lobachevskii J. Math. 41 (8), 1427–1434 (2020).
    doi 10.1134/S199508022008003X
  47. A. S. Antonov and N. I. Volkov, “Study of the Algorithms Information Structure as the Basis of a Training Workshop,” Communications in Computer and Information Science. 1510, 404–414 (2021).
    doi 10.1007/978-3-030-92864-3_31
  48. G. Skryabin, T. Gadieva, and A. Antonov, “A New Version of the AlgoView System for 3D Visualization and Interactive Analysis of Information Graphs of Algorithms,” Communications in Computer and Information Science. 2241, 19–33 (2024).
    doi 10.1007/978-3-031-73372-7_2
  49. List of algorithms – Wikipedia.
    https://en.wikipedia.org/wiki/List_of_algorithms Cited November 30, 2025.
  50. DSA Tutorial – Learn Data Structures and Algorithms – GeeksforGeeks.
    https://www.geeksforgeeks.org/dsa/dsa-tutorial-learn-data-structures-and-algorithms/ Cited November 30, 2025.
  51. Parallel Algorithms of the Standard Template Library.
    https://www.modernescpp.com/index.php/parallel-algorithm-of-the-standard-template-library/ Cited November 30, 2025.
  52. Algorithmica.
    https://algorithmica.org/ Cited November 30, 2025.
  53. GitHub – Algorithmica-org/Algorithmica: A Computer Science Textbook.
    https://github.com/algorithmica-org/algorithmica Cited November 30, 2025.
  54. MAXimal : : algo.
    http://e-maxx.ru/algo/ Cited November 30, 2025.
  55. Main Page – Algorithms for Competitive Programming.
    https://cp-algorithms.com/ Cited November 30, 2025.
  56. Algorithm Repository.
    https://www.algorist.com/algorist.html Cited November 30, 2025.
  57. Algocode wiki.
    https://wiki.algocode.ru Cited November 30, 2025.
  58. Algorithms – IT wiki ru.
    https://www.it-wiki.com.ru/algorithms/ Cited October 13, 2025.
  59. Algorithm Wiki.
    https://algorithm-wiki.csail.mit.edu/ Cited October 13, 2025.
  60. Algorithm Wiki | Interactive algorithms.
    https://thimbleby.gitlab.io/algorithm-wiki-site Cited November 30, 2025.
  61. Dijkstra’s algorithm | Algorithm Wiki.
    https://thimbleby.gitlab.io/algorithm-wiki-site/wiki/Dijkstras_algorithm/ Cited November 30, 2025.
  62. Algorithms – Wikibooks, Open Books for an Open World.
    https://en.wikibooks.org/wiki/Algorithms Cited November 30, 2025.
  63. Algorithms | Brilliant Math & Science Wiki.
    https://brilliant.org/wiki/algorithm/ Cited November 30, 2025.
  64. List of Algorithms.
    https://www.scriptol.com/programming/list-algorithms.php Cited November 30, 2025.
  65. Vl. V. Voevodin, “An Open AlgoWiki Encyclopedia of Algorithmic Features: from Mobile to Extreme Scale,” Numerical Methods and Programming 16 (1), 99–111 (2015).
    doi 10.26089/NumMet.v16r111
  66. Vl. V. Voevodin, A. S. Antonov, and J. Dongarra, “AlgoWiki: an Open Encyclopedia of Parallel Algorithmic Features,” Supercomputing Frontiers and Innovations 2 (1), 4–18 (2015).
    doi 10.14529/jsfi150101
  67. Vl. Voevodin, A. Antonov, and J. Dongarra, “Why is It Hard to Describe Properties of Algorithms?,” Procedia Computer Science. 101, 4–7 (2016).
    doi 10.1016/j.procs.2016.11.002
  68. A. Antonov, A. Frolov, I. Konshin, and Vl. Voevodin, “Hierarchical Domain Representation in the AlgoWiki Encyclopedia: From Problems to Implementations,” in Communications in Computer and Information Science (Springer, Cham, 2018), 910, pp. 3–15.
    doi 10.1007/978-3-319-99673-8_1
  69. A. Popov, D. Nikitenko, A. Antonov, and Vl. Voevodin, “Formal Model of Problems, Methods, Algorithms and Implementations in the Advancing AlgoWiki Open Encyclopedia,” CEUR Workshop Proc. 2281, 1–11 (2018).
    https://ceur-ws.org/Vol-2281/paper-01.pdf Cited November 30, 2025.
  70. A. S. Antonov, “Extraction of an Explicit Level of Algorithms Implementation for Use in the Algo500 Project,” Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering 12 (1), 89–100 (2023).
    doi 10.14529/cmse230105

Лицензия

Copyright (c) 2025 А. С. Антонов

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.