О реализации функций алгебры логики в некоторых классах программ

• Автор: Грибок, Сергей Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 90 с.

Содержание

Глава 1. Введение

§1.1 Общая характеристика работы

§1.2 Постановка задачи и формулировка полученных

результатов

§1.3 Критерий полноты программ

Глава 2. Одномодульные программы

§2.1 Структура одномодульных программ

§2.2 Нижние оценки функций Шеннона

§2.3 Верхние оценки функций Шеннона

Глава 3. Мультимодульные программы

§3.1 Программы с легкими константами
§3.2 Поведение функции Шеннона для унарной сложности
рекурсивных схем из функциональных элементов
§3.3 Поведение функции Шеннона для сигнатурной сложности
рекурсивных схем из функциональных элементов
§3.4 Синтез невырожденных мультимодульных программ
Приложение А. Общие формулы для вычисления нижних мощностных оценок функции Шеннона
Приложение В. Вычисление экстремумов некоторых функций
Приложение С. Некоторые результаты из теории универсальных матриц
Литература
Глава 1. Введение
§1.1 Общая характеристика работы
Задача синтеза управляющих систем является одной из основных задач математической кибернетики. Она возникла естественным образом на основе ряда задач, связанных с логическим описанием и проектированием реальных устройств, занимающихся переработкой информации. К числу подобных устройств относятся, например, интегральные схемы, сети нейронов, некоторые виды вычислительных алгоритмов.
Задача синтеза получила строгую математическую постановку в работе К. Шеннона [30]. Обычно задача синтеза рассматривается для какого-либо класса управляющих систем, то есть множества схем, наделенных определенной структурой и характеризующихся функционированием (см. например [25]). Функционирование схемы, как правило, описывается булевской функцией или системой булевских функций. Вводится понятие сложности схемы, обычно равной сумме сложностей всех элементов, составляющих ее, после чего определяется сложность булевской функции, как сложность самой простой схемы, реализующей эту функцию, и функция Шеннона, зависящая от натурального аргумента п, которая равна максимальной сложности булевских функций от п переменных. Задача массового синтеза состоит в изучении поведения (установлении асимптотики) функции Шеннона при растущем значении аргумента п.
Первые оценки для функций Шеннона, характеризующих сложность реализации функций в некоторых основных классах управляющих систем, таких как контактные схемы, релейно-контактные схемы, формулы, схемы из функциональных элементов в произвольном полном конечном базисе, были получены в работах К.Шеннона и О.Б.Лупанова [30,18,19,20,21]. К.Шенноном был установлен порядок функции Шеннона для класса контактных схем, а О.Б.Лупановым для всех основных классов управляющих систем была найдена асимптотика соответствующих функций Шеннона. В дальнейшем, усилиями многих авторов была установлена асимптотика сложностных функций Шеннона для различных задач массового синтеза.
Вместе с тем до появления работ С.А.Ложкина [8-15] не были известны оценки функций Шеннона с точностью до более чем одного члена

их асимптотических разложений. Первый результат был получен в [8], где доказывается, что для функции Шеннона LK{n), характеризующей сложность реализации булевских функций ориентированными контактными схемами, выполняется равенство
21ogn±Q(l) п ) '
В последующих работах [9-17] приводится универсальный метод получения верхних оценок функции Шеннона, позволяющий установить оценки высокой степени точности для функций Шеннона в других основных классах управляющих систем, таких как формулы и схемы из функциональных элементов, построенные в произвольном конечном полном базисе, контактные схемы из обобщенных контактов, и многих других.
В настоящей работе рассмотрены специальные классы управляющих систем, а именно некоторые классы программ для вычислительного устройства с произвольным доступом к памяти (random access machine).
Рассмотрим вычислительное устройство, содержащее упорядоченное множество ячеек памяти, в которых могут храниться результаты промежуточных вычислений. В каждый момент времени вычислительное устройство обрабатывает некоторую команду содержащейся в нем программы и, в зависимости от типа этой команды, может записывать информацию в некоторые ячейки памяти, считывать информацию из ячеек памяти, а также определять следующую команду для обработки.
Устройство с произвольным доступом к памяти является естественной моделью вычислений и различные типы таких устройств изучались многими авторами (например [27,28]).
В данной диссертации работа устройства с произвольным доступом к памяти изучается с точки зрения сложности программ из некоторых классов, реализующих произвольные функции алгебры логики. Подобные модели изучались в работах [6,7]. В настоящей работе рассмотрена весьма общая модель программ, обобщающая и уточняющая результаты, полученные в работах [6,7].
В работе [7] рассмотрены так называемые бинарные программы. В этой модели существует два типа команд:
‘Основание 2 у логарифмов опускается.

где д > 1 и поэтому < Л^/д, и что минимальное значение произведения П^1 при условии (7) для действительных переменных достигается, если все А;* равны Л^ДдЛ^).
Следовательно, учитывая (2), (3) и то, что
п <2о%Ь, В < Л^, N0 < Л^/д
получим
м(гБ+1)В-М+п-^:1 Ъ£. м{тБ+1)в-М+п-Мь^
С' п57^ < (ЛГ6/(ЛГсд))ЛГь/? <
^м(гв+1)Д-М-Д^ ^М(ГВ + 1)Д_М-Д^
<с« (Ъ/(Нсд))*/я <Сд {В/(Ад))*/я =
= с^М^Тв+1~1/,ТБ)в~м . (8)
Легко видеть, что после всех выполненных доопределений программа полностью определена. Перемножая оценки (1), (4), (5) и (8), получим, что число неэквивалентных канонических (Б_, А, оо, оо)-программ, при условии 7гб = 1 /(тд + 1) < А, оценивается сверху следующей величиной:

СЬ ьА((тБ+1)/2-е2)м(тв+1-1/<гБ)В+А((тБ+1)/2-е2)-М (М1/'твАд
В )

Найдем значение параметра д, которое максимизирует выражение (9). Нетрудно убедиться в том, что максимальное значение функции действительного аргумента (С'х)с'!х на отрезке [1,оо) в случае С' > е достигается при 1 = 1, ав случае С' < е - при х = е/С'. Следовательно, если
М1/<ТБА
в <е’
то максимум (9) достигается при д > 1 и оценивается сверху величиной
С££( гв+1-£з)£, (10)
где £3 = тт(2е2,1/(7£) > 0- Если же
М1^ВА Б “ 6’