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

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