Синтез бинарных программ с преобладанием команд переадресующего типа

В.В. Жуков

Московский государственный университет имени М.В. Ломоносова, г. Москва, 119991, Россия

ОРИГИНАЛЬНАЯ СТАТЬЯ

Полный текст PDF

DOI: 10.26907/2541-7746.2021.3-4.276-290

Для цитирования: Жуков В.В. Синтез бинарных программ с преобладанием команд переадресующего типа // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2021. – Т. 163, кн. 3–4. – С. 276–290. – doi: 10.26907/2541-7746.2021.3-4.276-290.

For citation: Zhukov V.V. Synthesis of binary programs with predominance of branching commands. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2021, vol. 163, no. 3–4, pp. 276–290. doi: 10.26907/2541-7746.2021.3-4.276-290. (In Russian)

Аннотация

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

Ключевые слова: бинарные программы, функция Шеннона, асимптотические оценки

Благодарности. Работа выполнена при финансовой поддержке Минобрнауки РФ в рамках реализации программы Московского центра фундаментальной и прикладной математики по соглашению № 075-15-2019-1621.

Литература

1. Шеннон К. Работы по теории информации и кибернетике. – М.: Изд-во иностр. лит., 1963. – 830 с.
2. Грибок С.В. О реализации функций алгебры логики в некоторых классах программ: Дис. … канд. физ.-мат. наук. – М., 2003. – 90 с.
3. Жуков В.В. Методы синтеза бинарных программ, допускающих рекурсивный вызов процедур // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетики. – 2021. – № 3. – С. 3–12.
4. Жуков В.В. Синтез некоторых типов бинарных программ, допускающих рекурсивный вызов процедур ограниченной глубины // Проблемы теоретической кибернетики: Материалы XIX междунар. конф. – Казань: Казан. фед. ун-т, 2021. – С. 53–55.
5. Ложкин С.А. Лекции по основам кибернетики. – М.: Изд. отдел фак. ВМиК МГУ, 2004. – 253 с.
6. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. – М.: Изд-во МГУ, 1984. – 137 с.

Поступила в редакцию

23.08.2021

Жуков Владимир Владимирович, аспирант факультета вычислительной математики и кибернетики

Московский государственный университет имени М.В. Ломоносова

ул. Ленинские Горы, д. 1, г. Москва, 119991, Россия

E-mail: zhvv117@gmail.com

Контент доступен под лицензией Creative Commons Attribution 4.0 License.