ДИСКРЕТНЫЕ ДЕТЕРМИНИРОВАННЫЕ ПРОЦЕССЫ: РЕАЛЬНОЕ ВРЕМЯ, ПАРАЛЛЕЛИЗМ, СЛОЖНОСТЬ, ЯЗЫКИ ОПИСАНИЯ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Рассмотрены модели и языки, предназначенные для описания и управления выполнением в реальном времени дискретных детерминированных процессов. Процессы разделены на свободные и зависимые от реального времени, введены характеристики сложности процессов, учитывающие фактор одновременности (параллелизма) при их выполнении. Предложены унифицированные операции композиции вычислимых функций, на основе которых создан язык, позволяющий в естественной форме описывать параллелизм алгоритмических процессов. Показано, каким образом фактор реального времени может быть отражен в процессах путем расширения языка примитивами управления изменением состояний процесса в зависимости от контролируемого времени.

Об авторах

В. П. Кутепов

Национальный исследовательский университет “МЭИ”

Email: kutepov@appmat.ru
Москва, Россия

Список литературы

  1. Agha G., Mason I., Smith S. Talcott C. Towards a Theory of Actor Computations// Third International Conf. on Concurrency Theory (CONCUR ‘92). Springer-Verlag, 1992. P. 565–579.
  2. Вальковский В.А., Котов В.Е., Марчук А.Г., Миренков Н.Н. Элементы параллельного программирования // Радио и связь. 1983. 240 c.
  3. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984. 264 c.
  4. Keller R.M. Parallel Program Schemata and Maximal Parallelism // J. ACM. 1973. V.20. № 3. P. 514–537.
  5. Milner R. A Calculus of Communicating Systems // Lecture Notes in Computer Science. Springer-Verlag, 1980. P. 184.
  6. Хоар Ч. Взаимодействующие параллельные процессы. М.: Мир, 1992. 184 с.
  7. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика. 1979. № 1. С. 45–58.
  8. Кутепов В.П. Модели и языки для описания параллельных процессов // Изв. РАН. ТиСУ. 2018. № 3. С. 116–127.
  9. Хьюз К., Хьюз Т. Параллельное и распределенное программирование с использованием С++. М.: Вильямс, 2004. 667 с.
  10. Cesarini F., Thompson S. ERLANG Programming: a Concurrent Approach to Software Development. Sebastopol, California, O’Reilly Media, 2009. 496 p.
  11. Кутепов В.П., Шамаль П.Н. Реализация языка функционального параллельного программирования FPTL на многоядерных компьютерах // Изв. РАН. ТиСУ. № 3. С. 46–60.
  12. Кутепов В.П., Зубов М.И. Реализация и экспериментальное исследование эффективности упреждающего параллелизма // Вестн. МЭИ. 2019. № 4. C. 119–126.
  13. Кутепов В.П., Ефанов А.А. Параллельные процессы и программы: модели, языки, реализация на системах // Программные продукты и системы. 2020. Т. 33. № 3. С. 375–384.
  14. Кутепов В.П. Интеллектуальное управление процессами и загруженностью в вычислительных системах // Изв. РАН. ТиСУ. 2007. № 5. С. 58–73.
  15. Бражникова Ю.Н., Горицкий Ю.А., Кутепов В.П., Панков Н.А. Исследование методов прогнозирования загруженности компьютеров и компьютерных систем // Программные продукты и системы. 2015. № 2. С. 135–146.
  16. Кутепов В.П., Фальк В.Н. Алгоритмические параллельные процессы и их сложность // Вестн. МЭИ. 2020. № 3. С. 102–110.
  17. Apt K. Formal Justification of a Proof System for Communicating Sequential Process // J. ACM. 1983. V. 30. № 1. P. 197–216.
  18. Pnueli A. Temporal Logic of Programs // Proc. 18-th IEEE Sympos. of Foundation of Computer Science. Tel Aviv, Israel, 1977. P. 46–57.
  19. Lamport L. The Temporal Logic of Actions // ACM Transactions on Programming Languages. 1993. V. 7. № 3. P. 1–52.
  20. Stanford Encyclopedia of Philosophy. Temporal Logic. 2019. Р. 1–17. https://plato.stanford.edu/entries/logic-temporal/
  21. Allen J.F. Maintaining Knowledge About Temporal Intervals // Communications of ACM. 2010. V. 26. № 11. P. 832–843.
  22. Orgun M., Wadge W. Theory and Practice of Temporal Logic Programming // J. Logic Programming. 1992. V. 13. P. 413–440.
  23. Buchi J.R. On a Decision Method in Restricted Second Order Arithmetic // Proc. Intern. Congr. Logic, Method and Philos., Sci. Stanford University, 1960. P. 1–12.
  24. Vardi M.Y., Wolper P. Reasoning About Infinite Computations // Information and Computation. 1994. V. 115. № 1. P. 1–37.
  25. Finger M., Gabbay Dov. Adding a Temporal Dimension to a Logic System // J. Logic, Language and Information. 1992. V. 1. P. 203–233.
  26. Gabbay P., Pnueli A., Shelah S., Stavi J. On the Temporal Analysis of Fairness // The ACM Sympos. on Principles of Programming Languages. Las Vegas, 1980. P. 163–173.
  27. Клини С. Введение в метаматематику. М.: Из-во иностр. лит., 1957. 520 c.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).