О реализации функций алгебры логики автоматными конвейерными схемами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

1 Общая характеристика работы.

1.1 Введение.

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

2 Оценки объема памяти, необходимой для реализации функций конвейерными схемами, синтез схем с минимальным объемом памяти.

2.1 Нижние оценки функций Шеннона для объема памяти.

2.2 Верхние оценки функций Шеннона для объема памяти.

2.3 Сложность конвейерных схем, использующих минимальный объем памяти.

3 Синтез конвейерных схем с эксклюзивным доступом к результатам вычислений.

3.1 Верхние оценки функций Шеннона для сложности схем с эксклюзивным доступом к результатам вычислений и множественным доступом к памяти.

3.2 Нижние оценки функций Шеннона для сложности схем с эксклюзивным доступом к результатам вычислений и множественным доступом к памяти.

3.3 Схемы с эксклюзивным доступом к памяти.

4 Конвейерные схемы с множественным доступом к результатам вычислений.

4.1 Поведение функции Шеннона для сложности схем с множественным доступом к результатам вычислений.

4.2 Синтез схем с множественным доступом к результатам вычислений, реализующих функции из некоторых классов.

1.1 Введение.

Задача синтеза управляющих систем является одной из основных задач математической кибернетики. Она возникла естественным образом на основе ряда задач, связанных с логическим описанием и проектированием реальных устройств, занимающихся переработкой информации. К числу подобных устройств относятся, например, интегральные схемы, сети нейронов, некоторые виды вычислительных алгоритмов.

Задача синтеза впервые получила строгую математическую постановку в работе К. Шеннона [39]. Обычно задача синтеза рассматривается для какого-либо класса управляющих систем, т.е. множества схем, наделенных определенной структурой и характеризующихся функционированием (см., например, [36]). Функционирование схемы, как правило, описывается булевской функцией (системой булевских функций). Вводится понятие сложности схемы, обычно равной сумме сложностей всех элементов, составляющих ее, после чего определяются сложность булевской функции как сложность самой простой схемы, реализующей эту функцию, и функция Шеннона, зависящая от натурального аргумента п и равная максимальной сложности булевской функции от п переменных. Задача массового синтеза состоит в изучении поведения (асимптотики) функции Шеннона при растущем значении аргумента п.

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

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

Модели, описывающие поведение вычислительных устройств, построенных "по принципу конвейера", исследовались разными авторами.

В [35] Редькиным Н.П. исследовалась задача построения матричных (решетчатых) структур из элементов с двухканальными связями, реализующих функции алгебры логики. Матричную структуру из двухканальных элементов можно рассматривать как устройство с "конвейерным" входом и с памятью. Его суть сводится к распределению вычислений, производимых в "памяти" устройства, во времени. В каждый момент времени "активной" является только одна входная булевская переменная, и в этот момент значение именно этой переменной определяет изменение содержимого памяти. Таким образом, матричные структуры из двухканальных элементов позволяют не использовать одновременно сразу все входные данные, а, наоборот, предполагают их поочередную подачу на вход структуры. В этой работе предложен метод синтеза структур рассматриваемого вида, приводятся верхняя и нижняя оценки функции Шеннона, совпадающие при числе переменных, равном степени двойки.

В [13] Кудрявцевым В.Б. рассматривается понятие прямоугольной логической сети, ориентированной на реализацию одной и той же вычислительной процедуры, применяемой к различным входным данным, подаваемым на входы логической сети в последовательные моменты времени. Прямоугольные логические сети представляют собой сети из простейших автоматов (автоматов, реализующих элементы дизъюнкции, конъюнкции, отрицания, срабатывающие с задержкой в один такт, и элемент единичной задержки с нулевым начальным состоянием). Входы одних простейших автоматов подключаются к выходам других автоматов или к входам всей схемы при помощи мгновенно срабатывающих проводников, после чего вся сеть укладывается на плоскую прямоугольную целочисленную решетку таким образом, чтобы простейшие автоматы были размещены в узлах решетки, а проводящие элементы проходили по вертикальным и горизонтальным линиям, параллельным ее сторонам. Выходы некоторых элементов сети объявляются выходами всей сети, и считается, что прямоугольная логическая сеть реализует оператор если при подаче в моменты времени ¿ = 0,1, 2,. .на входы сети наборов сто, • ■ ее выходах в моменты времени I — ¿о, ¿о + 1, ^о + 2,. будут вычисляться значения .Р(<7о), ^(о-х), ^(о^)5 — Таким образом, прямоугольные логические сети функционируют в "конвейерном" режиме, при котором на "конвейерный" вход сети подаются входные данные, а через некоторое время ¿о на "конвейерном" выходе вычисляются результаты применения оператора -Р к этим входным данным. Кроме времени задержки ¿о рассматриваются и другие сложностные характеристики сети, а именно площадь, занимаемая сетью, и радиус мгновенного действия, т.е. длина максимальной проводящей цепи, связывающей вход одного простейшего автомата с выходом другого. В [13] построены примеры реализации простейших математических операций прямоугольными логическими сетями.

Модель конвейерного вычислительного устройства, аналогичная модели из [13], исследовалась в работах [1, 2, 3]. В этих работах рассматривалась задача реализации последовательностных операторов посредством автоматных схем, функционирующих в режиме конвейера. Эти автоматные схемы, т.е. схемы из функциональных элементов и единичных задержек, в последовательные моменты времени получают на свои входы наборы входных значений, применяют к ним один и тот же оператор и через некоторое время (время вычисления) также последовательно выдают результаты вычислений. В [1, 2, 3] была предпринята попытка оценить характеристики сложности автоматной реализации для двух конкретных операторов, а именно оператора умножения двух Л^-разрядных чисел и оператора сортировки

N К-разрядных чисел. В частности, рассматривались две меры сложности автоматных схем: время вычислений и число элементов (т.е. сложность автоматной схемы), и была выявлена взаимосвязь между временной и объемной характеристиками сложности для вышеуказанных операторов. Для операторов умножения и сортировки была получена функция, определяющая зависимость времени работы схемы от ее объема (числа ее элементов). В указанных работах приведены методы синтеза, позволяющие получать как схемы с большой сложностью и малым временем вычисления, так и схемы с малой сложностью и большим временем вычисления.

Многокритериальная оптимизация неоднократно встречалась в различных исследованиях, касающихся сложности управляющих систем.

Классической работой в этой области можно считать работу Лупа-нова О.Б. [28]. В ней рассматривается задача массового синтеза схем из функциональных элементов, реализующих функции алгебры логики и построенных в произвольном полном конечном базисе. Каждому элементу из базиса поставлены в соответствие две положительные характеристики: вес и задержка. Сложностью Ь(3) и задержкой Т(Б) схемы Б объявляются соответственно сумма весов всех ее элементов и сумма задержек элементов, лежащих на любой цепи, соединяющей любой из входов схемы с выходом. Корректность определения задержки схемы следует из того, что автором рассматриваются только "правильные" схемы, т.е. схемы, у которых все цепи, соединяющие какой-либо вход с выходом, имеют одну и ту же задержку. Вводятся функции Ь{п) и Т(п), являющиеся функциями Шеннона для сложности и задержки реализации функций алгебры логики "правильными" схемами из функциональных элементов. В работе доказано, что для любого б > 0 и любой функции алгебры логики f(x 1,^2, •••,жп) от достаточно большого числа аргументов существует "правильная" схема Я, реализующая / и такая, что

ЦБ) < (1 + е)Ь(п), Т(5) < (1 + е)Т(п).

Таким образом, в рассматриваемой задаче массового синтеза с двумя параметрами оптимизации: сложностью и глубиной, удается достичь одновременно как асимптотически наилучшей сложности, так и асимптотически наилучшей глубины.

Однако одновременной оптимизации сразу нескольких параметров управляющих систем удается достичь далеко не всегда. В частности, такой эффект был выявлен в работе Альбрехта [38]. Автором исследовались схемы из функциональных элементов, реализующие функции алгебры логики. В качестве параметров оптимизации рассматривались число функциональных элементов, составляющих схему, и площадь, занимаемая схемой, и было выявлено, что наилучшие по сложности схемы не всегда могут быть компактно размещены на плоскости и наоборот.

Как правило случается так, что путем увеличения одной из сложностных характеристик управляющих систем можно добиваться уменьшения других. В этом случае характеристики сложности управляющих систем выступают как параметры-антагонисты, и задачу массового синтеза можно сформулировать несколько иным образом. Задачу массового синтеза можно поставить как изучение поведения (асимптотики) функции Шеннона Ь(п, гх, 7*2, • • ■ > гт) для той или иной характеристики сложности при растущем значении аргумента п и при различных ограничениях 7*2, •. •, гт на другие меры сложности.

Решению подобных задач было посвящено немало работ.

В [4] Власкиным В.М. исследовалась связь между сложностью и глубиной схем из функциональных элементов, реализующих так называемые ступенчатые функции в базисе, состоящем из элементов конъюнкции и дизъюнкции. Как оказалось, при синтезе схем, вычисляющих ступенчатые функции, сложность и глубина схемы выступают как параметры-антагонисты. Под сложностью схемы подразумевалось количество элементов в ней, а под глубиной - длина максимальной ориентированной цепи. Ступенчатая функция была определена как функция, которая равна нулю на каком-либо числе первых наборов значений своих переменных (если их лексикографически упорядочить) и равна единице на остальных наборах. Пусть а - некоторый набор из 0 и 1 длины п. Обозначим через На{х\,., хп) ступенчатую функцию, которая равна нулю на тех и только тех наборах значений переменных которые лексикографически меньше, чем а.

Обозначим через К (а) число групп подряд идущих нулей в наборе а, а через Т(ка) и Ь(ка,Т) соотвественно минимальную глубину схемы из функциональных элементов, реализующей функцию /га, и сложность реализации этой функции схемами с глубиной, не превышающей Т. Автором было доказано, что для любой ступенчатой функции /га, существенно зависящей от всех своих переменных, и для любого Т > Т(/ъа) выполняется нижняя оценка

Ь(К,Т) + 0.5 Т > п + К (а) - 1.

С другой стороны, им была получена верхняя оценка: для любой последовательности ступенчатых функций • • •, £п),п —> оо, при разумных ограничениях на числа T{ri) выполняется неравенство 1 L{hnan,T{n)) + 0.5Т(п) < (п + К{ап)){ 1 + о(1)).

Работы [5, 6, 7, 8, 9] посвящены исследованию задач информационного поиска. В них для базовых задач поиска ставится проблема оптимального синтеза, которая состоит в построении информационного графа, решающего заданную задачу информационного поиска и имеющего наименьшую сложность. Авторами рассматривались три сложностных характеристики алгоритма поиска: объем памяти, время поиска в худшем случае и среднее время поиска. Помимо оценивания вышеперечисленных характеристик алгоритмов поиска была затронута задача одновременной оптимизации решения задач информационного поиска как по времени поиска, так и по объему памяти. Как уже было сказано выше, решение задачи информационного поиска состояло в построении информационного графа, решающего эту задачу. На неформальном уровне суть этого графа состоит в том, чтобы для каждого "запроса" к информационной базе получать ответ (или множество ответов) на этот "запрос" путем недетерминированного "путешествия" по этому графу от начальной вершины к конечным. При этом каждая из конечных вершин означает некоторый ответ на " запрос", и на каждом шаге можно выполнить некоторую элементарную команду (или задать некоторый вопрос), от результата выполнения которой зависит дальнейшее движение по информационному графу. Для произвольного информационного графа U были определены величины T(U), T(U) и Q(U), равные соответственно наихудшему времени поиска (т.е. максимальному времени движения по информационному графу U для всевозможных запросов), среднему времени поиска и объему памяти (т.е. числу ребер информационного графа U). В качестве одного из результатов, полученных в перечисленных работах, для некоторых задач поиска I была выявлена явная зависимость функции Шеннона Т(/, q) от параметра q, где функция Т(1, д) определялась следующим образом

T(I,q) = inf(T(i7)| U решает /, Q(U) < q).

В статье [10] Карповой H.A. рассматривается класс схем из

1 Здесь и везде далее по тексту для любой неотрицательной функции а(п), зависящей от натурального аргумента п, запись О(а(п)) используется для обозначения неотрицательной функции Ь(п) такой, что существует константа С, для которой при всех п выполняется неравенство 6(п) < С а(п), а с помощью о(а(п)) обозначается функция Ь(п) такая, что —> 0 при п оо. Запись а(п) х Ъ(п) означает, что а{п) = 0(Ь(п)) и одновременно Ь{п) = 0(о(п)). функциональных элементов, в котором накладываются ограничения на число "одновременно запоминаемых" промежуточных результатов или "число регистров" в схеме без ограничения на ветвление выходов элементов. Определяются понятия сложности L(E) схемы Е как числа элементов в ней, ширины схемы р(Е) как максимального числа входов у функциональных элементов, входящих в схему, и толщины схемы t(E) как минимального числа "регистров" необходимого для записи всех промежуточных результатов вычислений в схеме. Последнее понятие требует уточнения. Для определения толщины схемы из функциональных элементов требуется произвести "распределение" всех ее элементов по "регистрам". Распределение по регистрам происходит двухэтапно. Сначала все элементы схемы нумеруются так, чтобы любой элемент в схеме имел номер не меньше, чем номер любого элемента, к которому он подключен своим входом. На втором этапе каждому элементу схемы ставится в соответствие некоторый "регистр" так, чтобы выполнялось следующее условие: если выход элемента с номером г подается на вход элемента с номером j, то в схеме не существует элемента с номером /с, г < к < j, которому поставлен в соответствие тот же самый "регистр", что и элементу с номером г. Среди всех "распределений" элементов схемы по "регистрам" выбирается тот, который использует наименьшее число "регистров", а само это число регистров называется толщиной схемы. В работе рассматривается базис Б, состоящий из функциональных элементов, реализующих всевозможные функции алгебры логики, и все схемы строятся именно в этом базисе. Пусть W(n) - это функция Шеннона для ширины реализации функций алгебры логики схемами толщины 1, a LPj(n) - функция Шеннона для сложности реализации функций алгебры логики схемами толщины, не превосходящей t, и ширины, не превосходящей р. В [10] доказано, что

1)

2) для всех р > W{n)

LPtl(n) х 2np;

3) для всех р > log2 п

Lpfi(n) х 2ПР;

4) для всех фиксированных £ > 3 и р > 2

2 п

Уже на основе перечисленных выше работ видно многообразие моделей памяти, рассматриваемых разными авторами. Эти модели условно можно разбить на две большие группы: память как "запоминающее устройство" и память как " разветвляющее устройство".

К моделям памяти как " запоминающего устройства" можно отнести такие модели, в которых память используется для хранения некоторых промежуточных результатов вычислений, для "переноса" этих результатов в следующий момент времени (что встречается в управляющих системах, процесс функционирования которых распространен во времени), а также для хранения алгоритмов вычислений (т.е. программ, согласно которым осуществяются вычисления). В частности, такие модели появляются в работах [13, 1, 2, 3], в которых рассматриваются управляющие системы, функционирующие на базе автоматных схем (т.е. схем с единичными задержками), в [5, 6, 7, 8, 9], где под памятью понимается объем информационного графа, решающего задачу поиска, в [10], в которой память (или регистры) используется для хранения промежуточных результатов вычислений в схемах из функциональных элементов.

Стоит также упомянуть об еще одном классе управляющих систем с памятью, выступающей в роли "запоминающего устройства", а именно вычислительных программах, рассматриваемых в [14, 11]. В этих работах изучается сложность реализации функций соответственно двухзначной и /с-значной логики некоторыми видами программ. Рассматривается вычислительная машина, состоящая из адресуемой памяти со свободным доступом и управляющего устройства, хранящего неизменяемую программу. Память состоит из ячеек, каждая из которых способна хранить некоторое число из {0,1,., к — 1}. Программа состоит из команд. Команды могут быть двух типов: вычислительные и управляющие. Вычислительные команды вызывают выполнение некоторых операций над содержимым ячеек памяти машины с последующей записью результатов, а управляющие команды влекут передачу управления (условный переход от одной команды программы к другой) или остановку работы машины. В рамках описанной модели авторами получена асимптотика поведения функции Шеннона для сложности реализации функций программами.

К моделям памяти как " запоминающего устройства" можно отнести такие модели, в которых память используется для обеспечения множественного доступа к промежуточным результатам вычислений, т.е. обеспечения многократного использования этих результатов в последующих вычислениях.

Одной из первых работ, где была рассмотрена одна из таких моделей, является [26], в которой получена асимптотическая оценка сложности реализации произвольной функции алгебры логики схемами из функциональных элементов, в которых выход каждого элемента может быть соединен с небольшим числом входов других элементов, т.е. схемами, в которых каждый промежуточный результат используется небольшое число раз из-за ограничения на ветвление выходов элементов.

В [20]-[22] рассматриваются так называемые схемы из функциональных элементов с глубиной ветвления к, А; = 0,1,. в произвольном полном базисе Б. Базис Б разбивается на две компоненты: Б' и Б". В компоненту Б' попадают все самые "легкие" функциональные элементы из базиса Б, т.е. функциональные элементы, приведенные веса которых совпадают с приведенным весом рв базиса а в компоненту Б" - все остальные. Схемами с глубиной ветвления к, к = 0,1,. называются такие схемы, в которых отсутствуют цепи, состоящие только из элементов Б' и содержащие более к элементов с ветвящимися выходами. В работах [20, 21] получены оценки высокой степени точности для функции Шеннона ¿^(п) для сложности реализации функций алгебры логики схемами с глубиной ветвления к = 0,1. Эти оценки имеют вид: где константа хб зависит только от базиса и может быть определена следующим образом: Хб = 1 в том случае, если функциональные элементы из множества Б' реализуют либо только линейные функции, либо только конъюнкции переменных, либо только дизъюнкции переменных, и хб = 0 в противном случае.

Как видно функции Шеннона для сложности реализации функций алгебры логики схемами с глубиной ветвления 0 и 1 имеют одну и ту же асимптотику и отличаются только на уровне вторых членов своих асимптотических разложений. Таким образом, становится актуальной задача получения оценок сложности управляющих систем, имеющих высокую степень точности, т.е. оценок на уровне остаточных членов асимптотического разложения функций Шеннона.

ЬС/{П)=РБ- 1 +

2 - к + хб) п + к п ± 0(1) п

Напомним, что первые оценки для функций Шеннона, характеризующих сложность реализации функций в некоторых основных классах управляющих систем, таких как контактные схемы, релейно-контактные схемы, формулы, схемы из функциональных элементов в произвольном полном конечном базисе, были получены в работах К. Шеннона и О.Б.Лупанова [39, 23, 24, 25, 27]. К. Шенноном был установлен порядок функции Шеннона для класса контактных схем, а О.Б.Лупановым для всех основных классов управляющих систем была найдена асимптотика соответствующих функций Шеннона. Работа С.В.Яблонского [36], в которой была выявлена асимптотика функции Шеннона для сложности реализации булевских функций из так называемых инвариантных классов, образующих континуальное семейство, положило начало исследованиям, связанным с распространением перечисленных результатов вширь. В дальнейшем, усилиями многих авторов была установлена асимптотика сложностных функций Шеннона для различных задач массового синтеза.

Вместе с тем до появления работ Ложкина С.А. [15]-[20] не были известны оценки функций Шеннона с точностью до более чем одного члена их асимптотических разложений. Первый результат был получен в [15], где доказывается, что для функции Шеннона

-Л

Ь (п), характеризующей сложность реализации булевских функций ориентированными контактными схемами, выполняется равенство У/ 210^1)' п \ п

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

Щ(п) = РБ г- 1 + -г.- •

1(^2 п \ \cyg2 п )

В настоящей работе рассматривается класс так называемых параллельно-последовательных конвейерных схем, реализующих функции алгебры логики. Конвейерные схемы представляют собой автоматные схемы, построенные в базисе, состоящем из функциональных элементов и элемента единичной задержки. Эти схемы функционируют в течение нескольких подряд идущих тактов (моментов времени), в каждый из которых на входы конвейерной схемы поступают значения некоторых булевских переменных, а на последнем такте на выходе схемы формируется значение вычисляемой функции, зависящей от этих переменных. То, значения каких именно переменных поступают на входы и в какой именно момент времени, определяется конвейером, т.е. матрицей, состоящей из булевских переменных, строки которой соответствуют тактам, а столбцы - входам схемы.

В работе изучаются параллельно-последовательные конвейерные схемы, т.е. схемы, у которых все входы разделяются на две группы. На первую группу входов на протяжении всего времени работы схемы подаются значения одних и тех же булевских переменных, а на вторую - поочередно значения всех остальных переменных, причем так, что значение каждой переменной подается на вход только один раз.

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

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

Для некоторых из этих классов в работе устанавливаются асимптотические оценки высокой степени точности для функции Шеннона, т.е. оценки функции Шеннона на уровне асимптотики второго члена ее асимптотического разложения.

Работа состоит из четырех глав.

В первой главе описывается рассматриваемая модель конвейерной схемы, даются основные определения и формулируются полученные результаты.

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

В третьей главе исследуются классы конвейерных схем с эксклюзивным доступом к результатам вычислений. В частности, для класса схем с эксклюзивным доступом к результатам вычислений и множественным доступом к памяти получены оценки высокой степени точности для функции Шеннона, характеризующей сложность при различных ограничениях на объем используемой в схемах памяти. Как оказалось, увеличение количества допустимой памяти приводит к уменьшению сложности схем. Для класса схем с эксклюзивным доступом как к памяти, так и к результатам вычислений доказан противоположный результат. Функция Шеннона для сложности реализации функций алгебры логики такими схемами не зависит от ограничений на объем используемой памяти даже на уровне второго члена ее асимптотического разложения. Кроме того, доказано, что при реализации любых функций алгебры логики, отличных от константы, параллельными конвейерными схемами, построенными в ряде базисов, к которым, например, относятся базис } или базис, состоящий из функциональных элементов, реализующих всевозможные /г-местные функции, увеличение числа используемых задержек не приводит к сокращению сложности схем.

В четвертой главе рассматриваются схемы с множественным доступом к результатам вычислений. Для класса таких схем, как и для класса схем с эксклюзивным доступом к памяти и результатам вычислений, ограничения на объем доступной памяти не влияют на асимптотику функции Шеннона для сложности реализации произвольной функции алгебры логики. С другой стороны, приводится пример некоторого множества функций, при реализации которых использование всего лишь одной дополнительной задержки приводит к уменьшению сложности в константное число раз.

Результаты, вошедшие в работу, опубликованы в [31]-[34].

1. Ал-Доври Абдул Саттар Абдул Джабар. Функциональная мера сложности вычислений в автоматных схемах. // Диссертация на соискание ученой степени кандидата физико-математических наук.- М., 1994.

2. Ал-Доври Абдул Саттар Абдул Джабар. Оценки функциональной сложности автоматной реализации оператора умножения. // Депонировано в ВИНИТИ РАН, 1995.

3. Ал-Доври Абдул Саттар Абдул Джабар. Оценки функциональной сложности автоматного решения задачи о сортировке. // Депонировано в ВИНИТИ РАН, 1995.

4. Власкин В.М. О сложности и глубине схем, реализующих ступенчатые функции алгебры логики. // МГУ им. М.В.Ломоносова. Факультет Вычислительной математики и кибернетики. Кафедра математической кибернетики. Дипломная работа. М., 1995.

5. Гасанов Э.Э. Мгновенно решаемые задачи поиска. // Дискретная математика (1996) 8, 3. С. 119-134.

6. Гасанов Э.Э. Функционально-сетевые базы данных и сверхбыстрые алгоритмы поиска. // Изд. центр РГГУ. М., 1997.

7. Гасанов Э.Э., Луговская Ю.П. Константный в худшем случае алгоритм поиска идентичных объектов. // Дискретная математика (1999) И, 4. С. 139-144.

8. Гасанов Э.Э. Оптимальное решение базовых задач хранения и поиска в информационно-графовой модели данных. // Диссертация на соискание ученой степени доктора физико-математических наук.- М., 1999.

9. Карпова H.A. Вычисления с ограниченной памятью. // Математические вопросы кибернетики. Вып.2. М.: Наука, 1989. - С. 131-144.

10. Касим-Заде О. М. О сложности реализации функций в одном классе алгоритмов. // М.: Изд-во механико-математического факультета МГУ, 1999. С. 25-30.

11. Кудрявцев В.В., Алешин С.В., Подколзин A.C. Введение в теорию автоматов. // М.: Наука, 1985.

12. Кудрявцев В.Б. Основы теории однородных структур. // М.: Наука, 1990. С. 265-287.

13. Кузьмин В.А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ. // Методы дискретного анализа в теории кодов и схем. Сборник трудов. N29. Новосибирск, 1976. С. 11-39.

14. Ложкин С.А. О синтезе ориентированных контактных схем. // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1995. N 2. С. 36-42.

15. Ложкин С.А. Новые, более точные оценки функций Шеннона для сложности управляющих систем. // Дискретный анализ и исследование операций. 1995. Т.2, N 3. С. 77-78.

16. Ложкин С.А. О синтезе некоторых типов схем на основе сдвиговых разбиений, порожденных универсальными матрицами. // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 1996. N 1. С. 62-69.

17. Ложкин С.А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов. // М., 1996. (Препр./ ИПМ РАН; N 36).

18. Ложкин С.А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов. // Проблемы теоретической кибернетики. Тезисы докладов XI Международной конференции 10-14 июня 1996 г. - М., 1996. - С. 123-125.

19. Ложкин С.А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов. // Математические вопросы кибернетики. Вып.6. М.: Наука, 1996. - С. 89-214.

20. Ложкин С.А. Асимптотические оценки высокой степени точности для сложности управляющих систем. // Диссертация на соискание ученой степени доктора физико-математических наук. М., 1997.

21. Лупанов О. Б. О синтезе контактных схем. // ДАН СССР, 1958. -Т.119, N1. С. 23-26.

22. Лупанов О. Б. Об одном методе синтеза схем. // Изв. вузов, М.: Радиофизика, 1958. - T.l, N.1. - С. 120-140.

23. Лупанов О. Б. О сложности реализации функций алгебры логики формулами. // Проблемы кибернетики. Вып.З. М.: Физматгиз, 1960. - С. 61-80.

24. Лупанов О. Б. Об одном классе схем из функциональных элементов (формулы с частичной памятью). // Проблемы кибернетики. Вып.7. М.: Физматгиз, 1962. - С. 61-114.

25. Лупанов О. Б. О сложности реализации функций релейно-контактными схемами. // Проблемы кибернетики. Вып.11. М.: Наука, 1964. - С. 25-48.

26. Лупанов О. Б. О схемах из функциональных элементов с задержками. // Проблемы кибернетики. Вып.23. М.: Наука, 1970. - С. 43-82.

27. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. // М.: Изд-во МГУ, 1984.

28. Нигматуллин Р.Г. Сложность булевых функций. // М.: Наука, 1991.

29. Никитин A.A. О сложности реализации функций алгебры логики в некоторых классах автоматных схем. // Труды III международной конференции "Дискретные модели в теории управляющих систем" Красновидово'98 М.: Диалог-МГУ, 1998. - С. 79-81.

30. Никитин А.А. О сложности реализации функций алгебры логики в некоторых классах автоматных схем. // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика.1999. N 3. С. 41-49.

31. Никитин А.А. Об объеме памяти, необходимом для реализации функций алгебры логики автоматными конвейерными схемами. // Труды IV международной конференции " Дискретные модели в теории управляющих систем" Красновидово'2000. М.: МАКС-пресс,2000. С. 89-91.

32. Редькин Н.П. Однородные структуры из двухканальных элементов. // Автоматика и телемеханика, N4. М.: Наука, 1972. - С. 84-89.

33. Яблонский С.В. Основные понятия кибернетики. // Проблемы кибернетики. Вып.2. М.: Физматгиз, 1959. С. 7-38.

34. Яблонский С.В. Введение в дискретную математику. // М.: Наука, 1986.

35. Albrecht A. Zur Kompliziertheit der Realisierung Boolesher Functio-nen durch F-V-Schemata. // EIK 15 (1979) 3, S.159-171.

36. Shannon C.E. The synthesis of two-terminal switching circuits. // Bell Syst. Techn., 1949. V.28, N1. P.59-98.