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

Грибок, Сергей Владимирович АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Москва МЕСТО ЗАЩИТЫ
2003 ГОД ЗАЩИТЫ
   
01.01.09 КОД ВАК РФ
Диссертация по математике на тему «О реализации функций алгебры логики в некоторых классах программ»
 
Автореферат диссертации на тему "О реализации функций алгебры логики в некоторых классах программ"

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

На правах рукописи

Грибок Сергей Владимирович

О РЕАЛИЗАЦИИ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ В НЕКОТОРЫХ КЛАССАХ ПРОГРАММ

Специальность 01.01.09 - дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2003

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор Ложкин Сергей Андреевич.

Официальные оппоненты: доктор физико-математических наук,

Защита диссертации состоится 5 декабря 2003 г. в 11 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан 5 ноября 2003 г.

Ученый секретарь диссертационного совета

профессор Чашкин Александр Викторович; кандидат физико-математических наук, доцент Стеценко Владимир Алексеевич.

Ведущая организация: институт прикладной математики РАН

профессор

"Тат^

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

Актуальность темы

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

Классическими примерами асимптотически оптимальных методов синтеза являются методы, разработанные О.Б.Лупановым1 для всех основных классов схем (схем из функциональных элементов, контактных схем формул и др.)

Методы О.Б.Лупанова получили дальнейшее развитие в работах С.А.Ложкина2, который разработал методы синтеза, позволяющие устанавливать асимптотические оценки высокой степени точности, то есть оценки, совпадающие на уровне второго члена асимптотического разложения, для функций Шеннона в различных классах схем

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

Большинство существующих асимптотически оптимальных методов синтеза связаны с теми или иными «схемными» моделями, то есть теоретическими моделями «аппаратной» реализации функций. В частности, к таким моделям можно отнести схемы из функциональных элементов и

1 Лупанов О.Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, вып.10. М.: Физматгиз, 1963, с.63-97

2 Ложкин С.А. Оценки высокой степени точности управляющих систем из некоторых классов // Математические вопросы кибернетики, вып к м ■ Няукя с. 1 КЧ-? ы

рос. национальная БИБЛИОТЕКА

СПетчЛиму^у ' оэ |

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

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

Машина с произвольным доступом к памяти является естественной моделью вычислений, и различные типы таких машин изучались многими авторами, однако задача массового синтеза программ для машин описанного типа рассматривалась лишь для достаточно узких классов программ. Асимптотически оптимальные методы синтеза для некоторых классов программ были предложены в работах В.А.Кузьмина4 и О.М.Касим-Заде5, а в работах А.В.Чашкина6 получены оценки функции Шеннона для среднего времени вычисления булевских функций.

3 Gregory J. Chaitin. On the length of programs for computing finite binary sequences // Journal of the ACM 13 (1966), pp.547-569

4 Кузьмин B.A. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ // Методы дискретного анализа в теории кодов и схем. Сборник трудов Института математики СО АН СССР. Вып.29, Новосибирск, 1976.

с. 11-39

5 Касим-Заде О.М. О сложности реализации функций в одном классе алгоритмов // Материалы IX межгосударственной школы-семинара «Синтез и сложность управляющих систем», Издательство механико-математического факультета МГУ, 1999. с.25-30

6 Чашкин A.B. О среднем времени вычисления значений булевых функций // Дискретный анализ и исследование операций (1997) 4, N1, с.60-78

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

Цель работы

Целью данной работы является исследование задачи синтеза программ для вычислительного устройства с произвольным доступом к памяти. Рассматриваемая модель программ содержит три основных типа команд: вычислительные команды, переадресующие команды, а также команды вызова подпрограмм. Первые два типа команд являются стандартными и рассматривались в работах В.А.Кузьмина4 и О.М.Касим-Заде5. Вычислительная команда записывает в указанную ячейку памяти результат применения базисной логической функции к содержимому заданных ячеек памяти. Переадресующая команда осуществляет переход на ту или иную команду, в зависимости от содержимого заданной ячейки памяти. Команда вызова подпрограммы записывает в указанную ячейку памяти результат работы ранее определенной подпрограммы, входные переменные которой инициализируются значениями из заданных ячеек памяти. Таким образом, рассматриваемая модель обобщает модель В.А.Кузьмина4 и расширяет возможности программ модели О.М.Касим-Заде5, применительно к реализации функций алгебры логики.

В работе ставятся следующие основные задачи:

• разработка асимптотически оптимальных методов синтеза программ из описанного класса и различных его подклассов, связанных с возможностью использования тех или иных типов команд с различными весами;

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

Основные результаты работы.

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

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

Научная новизна

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

на4.

Практическая ценность

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

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

Методы исследования

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

построения нижних оценок, а также другие методы дискретной математики и математической кибернетики.

Апробация работы и публикации

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

• X межгосударственная школа-семинар «Синтез и сложность управляющих систем» (Минск, 1999)

• XII межгосударственная школа-семинар «Синтез и сложность управляющих систем» (Пенза, 2001)

• XIII международная конференция «Проблемы теоретической кибернетики» (Казань, 2002)

• V международная конференция «Дискретные модели в теории управляющих систем» (Ратмино, 2003)

• XIV межгосударственная школа-семинар «Синтез и сложность управляющих систем» (Нижний Новгород, 2003)

Структура и объем диссертации

Диссертация состоит из трех глав, приложений и библиографии. Общий объем диссертации составляет 9о страниц . Библиография включает 32 наименования.

Краткое содержание работы

Первая глава является вводной: в §1.1 приведен краткий обзор исследований, связанных с содержанием диссертации, и дана постановка задачи, в §1.2 описана рассматриваемая модель и сформулированы полученные результаты, а в §1.3 исследованы вопросы полноты модели.

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

Каждой подпрограмме сопоставлено некоторое подмножество множества битовых ячеек памяти. Перед началом работы ¡-й подпрограммы в первые к, ячеек памяти, сопоставленных этой подпрограмме, записываются значения булевских входных переменных подпрограммы х,,...,*». Работа

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

Таким образом, каждая подпрограмма реализует некоторую функцию алгебры логики Считается, что программа реализует ту функцию

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

1) вычислительная команда (<р, то, ть ...., тк), которая записывают в заданную ячейку памяти то результат применения заданной логической функции ф(х|,...,хк) из набора базисных функций Б к содержимому заданных ячеек памяти Ш],.. .,шк;

2) переадресующая команда (т, кь к2), которая осуществляет переход на команду с номером к) или на команду с номером кг в зависимости от содержимого заданной ячейки памяти ш;

3) команда вызова подпрограммы (в; то, Ш|, ... , тк), которая записывает в заданную ячейку памяти то результат работы заданной ранее определенной подпрограммы с номером я, входные переменные которой инициализируются значениями из заданных ячеек памяти ть ..., т*.

Каждой команде V/ приписан некоторый неотрицательный вес Ц\у). При этом вес каждой вычислительной команды равен весу соответствующей базисной функции. Введено понятие удельного веса команды. Для вычислительной команды w ее удельный вес тс(\у) равен где

с1(\у) - это суммарное число входов и выходов данной команды. Для переадресующей команды V/ ее удельный вес равен Ц\у)/2. Вес команды вызова подпрограммы линейно зависит от числа входов к в этой команде и определяется по формуле: = цк + V, где ц > О, V > 0.

Таким образом, введены 4 основных весовых характеристики программ: минимальный удельный вес вычислительных команд удельный вес переадресующих команд "к, а также весовые коэффициенты команд вызова подпрограмм ц и v.

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

Для обозначения различных классов программ будем использовать весовой набор Если требуется обозначить, что некоторый весовой

коэффициент равен нулю, будем указывать 0 на соответствующем месте набора. Если требуется отметить, что в программе нельзя использовать команды некоторого вида, будем считать, что соответствующий весовой коэффициент является бесконечно большим и указывать символ со на соответствующем месте набора. Если требуется отметить, что некоторый весовой коэффициент является минимальным из всех весовых коэффициентов, будем подчеркивать соответствующий символ в наборе. Класс (Я.,со,со)-программ над базисом Б, например, состоит из программ, которые не содержат команды вызова подпрограмм, и при этом справедливо неравенство 71Б > X. Программы из этого класса будем называть одномодуль-ными программами с «легкими» переадресующими командами. Класс (А.,со,у)-программ над базисом Б состоит из программ, которые могут содержать все допустимые типы команд, но число входных параметров в командах вызова подпрограмм равно нулю, так как вес каждого такого параметра равен да. При этом выполнены неравенства: % й т|, x > v. Таким образом, в этом классе программ с помощью подпрограмм можно реализо-

вать лишь две функции: «константа 0» и «константа 1», но при этом вес команд вызова этих подпрограмм меньше или равен, чем удельный вес переадресующих и вычислительных команд. Программы из указанного класса будем называть программами с «легкими» константами. Класс (оо,Сопрограмм над базисом Б включает программы, которые не содержат переадресующих команд, а вес команд вызова подпрограмм не зависит от количества входных параметров в этих командах, и т.д.

Заметим, что (оо,оо,оо)-программы над базисом Б эквивалентны обычным схемам из функциональных элементов над базисом Б, а классы (0,цлО-программ и (Х,0,0)-программ являются вырожденными, в том смысле, что в любом из этих классов произвольную функцию алгебры логики можно реализовать с помощью программы, сложность которой не превышает некоторой константы С. Поэтому в дальнейшем эти классы программ не рассматриваются.

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

1) для того чтобы класс программ над базисом Б, не содержащий переадресующих команд, был полон, необходимо и достаточно, чтобы система функций базиса Б не содержалось целиком ни в одном из пяти пред-полных классов Т0, Ть Б, М, Ь7;

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

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

Сложность программы определяется как сумма весов всех ее команд. Каждой функции алгебры логики /(х,,...,х„) сопоставляется сложность £»■"■•"(/), равная минимальной сложности программы над базисом Б с ве-

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

совым набором реализующей эту функцию. Обычным образом оп-

ределяется функция Шеннона ¿У " ',(л) = тах£(/ Л'')(Л> гДе максимум берется по всем функциям алгебры логики f, зависящим от п переменных.

В главе 2 рассмотрены одномодульные программы, то есть программы, не содержащие команд вызова подпрограмм и состоящие таким образом из единственного модуля.

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

В §2.2 проведено построение нижних асимптотических оценок функций Шеннона в классах одномодульных программ. Рассмотрено два случая: (А,оо,оо)-программы над базисом Б, где яБ < X, или программы с «легкими» вычислительными командами, а также (Х,оо,оо)-программы над базисом Б, где лБ > X, то есть программы с «легкими» переадресующими командами. Доказаны следующие неравенства:

при условии Яв < X, где тБ - максимальное число входов у вычислительных команд веса лб;

В §2.3 получены верхние асимптотические оценки функций Шеннона в классах одномодульных программ:

Таким образом, доказана справедливость следующих утверждений.

при условии 7Сб < X;

Теорема 2.3.1 Для функции Шеннона в классе (X,да,подпрограмм над базисом Б, при условии % < справедлива следующая асимптотическая оценка

Теорема 2.3.2 Для функции Шеннона в классе (л.,со,оо)-программ над базисом Б, справедлива следующая асимптотическая оценка*

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

В главе 3 рассмотрены мультимодульные программы, то есть программы, содержащие команды вызова подпрограмм.

В §3.1 рассмотрены программы с "легкими" константами, то есть (А.,°о,у)-программы над базисом Б с минимальной весовой характеристикой V, в которых команды вызова подпрограмм не содержат входных параметров. При этом отдельно рассмотрены (А,,со,0)-программы, в которых вес команд вызова подпрограмм равен нулю. Доказаны следующие утверждения.

Теорема 3.1.1 Для функции Шеннона в классе (А.,оо,у)-программ над базисом Б, где V > О, справедлива следующая асимптотическая оценка высокой степени точности:

" для числовых функций gi(n) и g2(n) натурального аргумента п через Q(gi(n),g2(n)) будем обозначать любую функцию h(n), для которой справедливы неравенства gi(n)<h(n)<g2(n)

' Теорема 3.1.2 Для функции Шеннона в классе (\,оо,0)-программ над

базисом Б справедлива оценка:

С|2"'2 <4^'0)(и)<С22"'2

В §3.2 и §3.3 рассмотрены (ао,ц,у)-программы, не содержащие пере-адресугощих команд, причем в §3.2 рассмотрены (оо,0,у)-программы, а в §3.3 рассмотрены (оо,¿^-программы, при условии ц > 0. Рассмотрение этих классов программ удобно проводить, используя специальную модель управляющих систем - рекурсивные схемы из функциональных элементов (РСФЭ).

Определим РСФЭ над базисом Б, опираясь на понятие схемы из функциональных элементов (СФЭ) и используя индукцию по рекурсивной глубине РСФЭ.

Любая РСФЭ рекурсивной глубины к > 1 представляет собой упорядоченный набор из к СФЭ.

Шаг 1. РСФЭ Р| рекурсивной глубины 1 над базисом Б включает в себя единственную СФЭ над базисом Б. Эта РСФЭ реализует ту же функцию алгебры логики, что и составляющая ее СФЭ. Будем говорить, что этой РСФЭ соответствует расширенный базис Б1 = Б.

Шаг 8+1. Пусть построена РСФЭ Бэ рекурсивной глубины Б над базисом Б, причем Р£ реализует функцию £5 и этой РСФЭ соответствует расширенный базис Б8. Пусть Об - функциональный элемент, реализующий функцию Построим базис Б$+) = Б3 и а также построим СФЭ С8+1 над базисом 65+1- Тогда набор = Ре и 65+1 является РСФЭ рекурсивной ( глубины 8+1. Эта РСФЭ реализует ту же функцию, что и 05+1 и ей соот-

ветствует расширенный базис Б5+|.

Любая РСФЭ может быть построена за конечное число шагов согласно описанному алгоритму.

Будем называть унарной сложностью РСФЭ Е суммарное число функциональных элементов в схеме I, которое будем обозначать как

I

I

Будем называть сигнатурной сложностью РСФЭ Е суммарное число входов во всех функциональных элементах схемы 2, которое будем обозначать как ®э(£).

Обычным образом вводится сложность функции алгебры логики 4ГФЭ(Л и ¿^(я, а также функции Шеннона 1%ФЭ(п) и 1^ФЭ(п).

Несложно доказать, что при определенных весах базисных функций, (°о,0,1)-программы можно рассматривать, как РСФЭ, где в качестве слож-ностной характеристики выбрана унарная сложность, а (оо,1,0)-программы - как РСФЭ, где в качестве сложностной характеристики выбрана сигнатурная сложность.

В §3.2 доказаны следующие утверждения. Теорема 3.2.1 Для функции Шеннона Ь^'фэ(п) справедливо следующее асимптотическое равенство:

Следствием этой теоремы является аналогичная оценка функции Шеннона для (оо,0,у)-программ.

Теорема 3.2.2 Для функции Шеннона Ь(^>(п)ъ классе (<ю,0,у)-программ, где V > 0, справедливо следующее асимптотическое равенство:

В §3.3 доказаны следующие утверждения.

Теорема 3.3.1 Для функции Шеннона ЦСФЗ (я) справедливо следующее асимптотическое равенство:

Следствием этой теоремы является аналогичная оценка функции Шеннона для (оо,ц,у)-программ.

Теорема 3.3.2 Для функции Шеннона в классе (оо,ц,у)-программ, при условии 0 < ц < тск, справедливо равенство:

Зи

n\ "

Все ранее рассмотренные классы программ являлись в некотором смысле вырожденными, так как одна или более из весовых характеристик была равна со, либо 0.

В §3.4 рассмотрены невырожденные программы, то есть (A,,ji,v)-программы над базисом Б, где 0<яь<оо, 0<\<<х>, 0<ц<оо, 0<v<oo. Предложен следующий алгоритм выбора метода синтеза в указанном классе программ:

1. если минимальным из весовых коэффициентов является коэффициент яб, то используем метод синтеза для (Я,,оо,<ю)-программ, где 7tg<A,;

2. если минимальным из весовых коэффициентов является коэффициент X, то используем метод синтеза для (А.,оо,со)-программ;

3. если минимальным из весовых коэффициентов является коэффициент ц, то используем метод синтеза для (оо,^,у)-программ;

4. если минимальным из весовых коэффициентов является коэффициент v, то используем метод синтеза для (Х,«э,\>)-программ.

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

Теорема 3.4 Пусть 0<яБ<оэ, 0<Я,<оо, 0<ц<со, 0<v<oo. Тогда для функции Шеннона в классе (X,fi,v)-программ над базисом Б справедливо следующее асимптотическое равенство:

¿У (п) = ninfe ,Л, Ц, у) — (1 + 0(1)) п

Таким образом, в данной работе изучено асимптотическое поведение функций Шеннона для всех типов (Х,цлО-программ над произвольным базисом Б с произвольными неотрицательными весовыми характеристиками (при условии яБ > 0).

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

Для многократных логарифмов будем использовать следующие обозначения:

/_,(л) = 2", /0(л) = л, /„,(л) = 1оё/», 1 = 0,1,...

Теорема А.1 Если в некотором классе схем 5 для числа Яз(£,л) неизоморфных схем, которые реализуют функции алгебры логики от и переменных, и сложность которых не превышает I, справедлива оценка

N1

1

где р, д, с, а,, /?,, 1 = р,...,д, зависят только от 5 и не зависят от I и п, Ойр<д, с>0, ар+/3р>0, то для функции Шеннона (и) в этом классе схем справедлива оценка

¿»>4 (л),

где

М«) =

Г„2"

Го =

У:

ц\о%{ар +Рр) -1ояс

ар+Р>

-1;

Г, = £---Г-, г = р + 1,...,д + \,

ар+Р„

£ = 1, если / = 1, и (=0 в противном случае; г] = 1, если р = 0, и 7 = 0 в противном случае. При этом доля тех функций /(*,,...,*„), для которых

(л) 5 ¿5 (и)

стремится к нулю с ростом п.

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

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

г

Все представленные результаты получены автором самостоятельно, v Основные результаты изложены в следующих работах:

1. Грибок C.B. «О поведении функции Шеннона для бинарных программ». Материалы X межгосударственной школы-семинара «Синтез и сложность управляющих систем», Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2000. - С.4-7.

2. Грибок C.B. «Об одной модели рекурсивных схем из функциональных элементов». Материалы XII межгосударственной школы-семинара «Синтез и сложность управляющих систем», Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2001. Часть 1. - С.77-80.

3. Грибок C.B. «Оценка высокой степени точности для сложности обобщенных бинарных программ». Проблемы теоретической кибернетики. Тезисы докладов XIII международной конференции. Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2002. - С.47.

4. Грибок C.B. «Об одной модели рекурсивных схем из функциональных элементов». Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2002. N 4. - С. 31-36

5. Грибок C.B. «О нижних мощностных оценках функций Шеннона. // Материалы V международной конференции "Дискретные модели в теории управляющих систем", Издательский отдел факультета вычислительной математики и кибернетики МГУ, 2003. - С.25.

Отпечатано в копииенгре «Учебная полиграфия» Москва, Ленинские горы, МГУ, 1 Гуманитарный корпус. www.stprint.ru e-mail: zakaz@stDrint.ru тел 939-3338 Заказ № 404 тираж 50 экз. Подписано в печать 03. 11.2003 г.

118424

2.003-Д

 
Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Грибок, Сергей Владимирович

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

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

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

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

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

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

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

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

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

§3.1 Программы с легкими константами.

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

§3.3 Поведение функции Шеннона для сигнатурной сложности рекурсивных схем из функциональных элементов.

• §3.4 Синтез невырожденных мультимодульных программ

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

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

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

Первые оценки для функций Шеннона, характеризующих сложность реализации функций в некоторых основных классах управляющих систем, таких как контактные схемы, релейно-контактные схемы, формулы, схемы из функциональных элементов в произвольном полном конечном базисе, были получены в работах К.Шеннона и О.Б.Лупанова [30,18,19,20,21]. К.Шенноном был установлен порядок функции Шеннона для класса контактных схем, а О.Б.Лупановым для всех основных классов управляющих систем была найдена асимптотика соответствующих функций Шеннона. В дальнейшем, усилиями многих авторов была установлена асимптотика сложностных функций Шеннона для различных задач массового синтеза.

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

21ogn±0(iy п

В последующих работах [9-17] приводится универсальный метод получения верхних оценок функции Шеннона, позволяющий установить оценки высокой степени точности для функций Шеннона в других основных классах управляющих систем, таких как формулы и схемы из функциональных элементов, построенные в произвольном конечном полном базисе, контактные схемы из обобщенных контактов, и многих других.

В настоящей работе рассмотрены специальные классы управляющих систем, а именно некоторые классы программ для вычислительного устройства с произвольным доступом к памяти (random access machine).

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

Устройство с произвольным доступом к памяти является естественной моделью вычислений и различные типы таких устройств изучались многими авторами (например [27,28]).

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

В работе [7] рассмотрены так называемые бинарные программы. В этой модели существует два типа команд:

Основание 2 у логарифмов опускается.

1) вычислительные команды, которые записывают в заданную ячейку памяти гпз результат применения заданной двуместной логической функции f{x 1,^2) к содержимому двух заданных ячеек памяти т\ и гаг;.

2) переадресующие команды, которые осуществляют переход на команду с номером к\ или на команду с номером к-i в зависимости от содержимого заданной ячейки памяти т.

Кроме того, имеются две так называемые команды останова, при выполнении которых программа завершает работу и выдает то или иное значение, в зависимости от типа команды останова.

Сложность бинарной программы считается равной общему числу команд в программе. Естественным образом вводится сложность функции алгебры логики L(f) и функция Шеннона L(n).

В работе [6] установлена асимптотика функции Шеннона для данного класса программ:

L°(n) = £(l±o(l)).

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

1) Программы, состоящие только из вычислительных команд. Как показано в [7], этот класс управляющих систем эквивалентен классу схем из функциональных элементов (см., например, [26]), поэтому для соответствующей функции Шеннона справедливы оценки, полученные в [15] для класса схем из функциональных элементов:

2) Бинарные программы, где все ячейки памяти в вычислительных командах, в которые происходит запись результата вычисления, различны. В [7] показано, что этот класс управляющих систем эквивалентен одному из видов релейно-контактных схем, рассмотренному в [21], и установлена асимптотика соответствующей функции Шеннона:

2 п

3) Бинарные программы, состоящие только из переадресующих команд. Этот класс управляющих систем впервые был рассмотрен в работе [29]. Обычно рассматривается графическое представление данного типа бинарных программ в виде контактных схем из ориентированных контактов (см., например, [22]), в которых отсутствуют ориентированные циклы, имеется один исток, являющийся входом схемы, и два стока, являющиеся ее выходами. При этом выходы помечены символами 0 и 1, а из каждой невыходной вершины выходит ровно два контакта, один из которых помечен символом входной переменной, а другой - символом ее отрицания. В современных публикациях этот класс управляющих систем носит название BDD - 'Binary Decision Diagram' (Бинарная Решающая Диаграмма) и изучается многими авторами (см., например, [26]). В работе [7] установлена асимптотика функции Шеннона для этого класса: i3(n) = ^( 1+0(1)), п а из результатов работы [16] вытекает следующая асимптотическая оценка высокой степени точности для этой функции Шеннона:

Также рассматривались некоторые частные случаи BDD: а) Свободные бинарные решающие диаграммы (Free BDD) - бинарные решающие диаграммы, в которых никакой путь от корня к листу не содержит двух контактов, помеченных символами одинаковых переменных (см., например, [26,32]). б) Упорядоченные бинарные решающие диаграммы (Ordered BDD) -бинарные решающие диаграммы, в которых переменные упорядочены таким образом, что ни на одном пути от корня к листу переменная с большим номером не может встретиться раньше переменной, номер которой меньше (см., например, [26,32]). в) Строго упорядоченные бинарные решающие диаграммы с кратностью считывания к (k-SOBDD), то есть бинарные решающие диаграммы, в которых все переменные xi,.,xn упорядочены некоторым образом, и любой путь от корня к листу содержит ровно пк контактов и все эти переменные встречаются в нем в указанном порядке сначала один раз, потом второй раз и т.д. (см., например, [17,26,32]). г) Упорядоченные бинарные решающие диаграммы с кратностью считывания к (к-ОВББ) определяются аналогично к-ЗОВББ, с той лишь разницей, что в вычисляющих путях возможны пропуски переменных (см., например, [17,26,32]).

Для двух последних классов программ в [17] в случае к > 2 получены следующие оценки для соответствующих функций Шеннона:

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

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

Существенным обобщением модели, введенной в работе [7], послужила модель, рассмотренная в работе [6]. Основные отличия этой модели от предыдущей заключаются в следующем:

1) в модели рассмотрены вектор-функции к-значной логики;

2) вычислительные команды могут реализовать произвольные функции (не только двуместные, как в [7]) из заданного конечного множества базисных функций В;

3) вычислительные команды могут иметь несколько выходов, то есть одна команда может записывать в несколько ячеек памяти результаты вычисления нескольких функций;

4) имеется только одна команда останова, а выходное значение (набор выходных значений) программы определяется значением (набором значений), которое к моменту останова оказалось в специальной выделенной ячейке памяти (наборе ячеек памяти).

Каждой команде ш приписан некоторый вес Л(о;) Сложность программы определяется как сумма весов всех команд в программе.

Введено понятие удельного веса команды. Для вычислительной команды и удельный вес команды ж(и>) равен Л(а>)/б?(а>), где - это суммарное число входов и выходов данной команды. Для переадресующей команды Т удельный вес команды А(Т) равен Л(Т)/2.

Для этой модели в [6] установлена асимптотика функции Шеннона:

Ьв{п) ~ 8{В)кп/щ где 6(В) - это минимальной удельный вес команд. Для случая вектор-функций /г-значной логики, состоящих из тп функций от п переменных, в [6] также представлена асимптотика соответствующей функции Шеннона следующего вида:

Ьв(п,тп) ~ 8(В)тпкп/ \о%к{тпкп).

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

Следующие характеристики рассматриваемой модели ограничивают ее, по сравнению с моделью в [6]:

1) рассмотрена реализация функций алгебры логики (в отличие от [6], где рассмотрены вектор-функции в /г-значной логике);

2) каждая вычислительная команда имеет ровно один выход, и реализует ровно одну функцию из заданного конечного множества базисных функций алгебры логики Б (в отличие от [6], где возможна реализация нескольких функций с помощью одной вычислительной команды);

Следующие характеристики обобщают рассматриваемую модель, по сравнению с моделью в [6]:

1) программа представлена в виде набора подпрограмм, каждой из которых соответствует отдельное множество ячеек памяти;

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

Вес и удельный вес вычислительных и переадресующих команд определяются аналогично [6]. Вес в (и) команды вызова подпрограммы ш линейно зависит от числа входов к в этой команде и определяется по формуле: з(и>) = ¡1к + и, где ¡1 > 0, и > 0.

Таким образом, введены 4 основных весовых характеристики программ: минимальный удельный вес вычислительных команд 7Гудельный вес переадресующих команд Л, а также весовые коэффициенты команд вызова подпрограмм /¿их/.

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

Если в программе разрешены только вычислительные (переадресующие) команды, то мы, по существу, имеем дело с обычными схемами из функциональных элементов (соответственно ВОБ), которые достаточно хорошо изучены и в данной работе специально не рассматриваются. В работе не рассматриваются также вырожденные случаи, при которых тгб — 0 или А = 0. В то же время подробно рассматривается случай, когда программа не может содержать переадресующих команд, который приводит нас к модели так называемых рекурсивных схем из функциональных элементов (РСФЭ). Эта модель управляющих систем расширяет обычные схемы из функциональных элементов, позволяя определять новые функциональные элементы в процессе синтеза и использовать эти элементы в дальнейшем наравне с базисными.

В данной работе исследована массовая задача синтеза для всех классов программ с произвольными неотрицательными весовыми характеристиками (при условии 7Гб > 0) и получены асимптотические оценки для соответствующих функций Шеннона.

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

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

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

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

В третьей главе рассмотрены мультимодульные программы, то есть программы, содержащие команды вызова подпрограмм. Вначале рассмотрены так называемые программы с легкими константами, то есть программы с минимальной весовой характеристикой I/, в которых команды вызова подпрограмм не содержат входных параметров. Для этой модели верхние и нижние оценки функции Шеннона совпадают с точностью до второго члена асимптотического разложения. Отдельно рассмотрен частный случай, когда 1/ = 0. Оказалось, что в этом случае функция Шеннона растет по порядку как 2П/2. Также изучены программы с минимальной весовой характеристикой /л, не содержащие переадресующих команд. Изучение этого класса программ проведено в терминах рекурсивных схем из функциональных элементов. Отдельно рассмотрен частный случай, когда ¡1 = 0. Оказалось, что в этом случае функция Шеннона имеет линейную относительно п асимптотику. В последней части главы получено общее выражение для асимптотики функции Шеннона в классах программ, содержащих команды всех типов с произвольными положительными весовыми характеристиками.

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

Основные результаты диссертации опубликованы в [1]-[5].

 
Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Грибок, Сергей Владимирович, Москва

1. Грибок C.B. О поведении функции Шеннона для бинарных программ. Материалы X межгосударственной школы-семинара "Синтез и сложность управляющих систем", Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2000. - С.4-7.

2. Грибок C.B. Об одной модели рекурсивных схем из функциональных элементов. Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2002. N 4. С. 31-36

3. Грибок C.B. О построении нижних оценок для функции Шеннона. Материалы V международной конференции "Дискретные модели в теории управляющих систем", Издательский отдел факультета вычислительной математики и кибернетики МГУ, 2003. С.25.

4. Касим-Заде О.М. О сложности реализации функций в одном классе алгоритмов. Материалы IX межгосударственной школы-семинара "Синтез и сложность управляющих систем", Издательство механико-математического факультета МГУ, 1999. С.25-30.

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

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

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

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

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

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

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

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

13. Ложкин С.А., О сложности реализации произвольных булевых функций в некоторых классах BDD. Труды Международной школы-семинара "Дискретная математика и математическая кибернетика" М.: МАКС Пресс, 2001. С.18-19

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

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

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

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

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

19. Чашкин А.В., О среднем времени вычисления значений булевых функций. Дискретный анализ и исследование операций. 1997. 4, N 1, 1997. С.60-78

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

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

22. Chakravarty S., A characterization of Binary Decision Diagrams. IEEE Transactions on Computers, vol.42, no.2, (1993), 129-137.

23. S. Cook and R. Reckhow. Time bounded random access machines. J. Сотр. Sys. Sci., 7:354-375, 1973.

24. J. Katajainen, J. van Leeuwen, and M. Penttonen. Fast simulation of Turing machines by random access machines. SIAM J. Comput., 17:7788, 1988.

25. Lee C., Representation of switching circuits by binary decision programs. Bell Syst. Tech. J., no.7, (1959), 985-999.

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

27. Wegener I. Branching programs and binary decision diagrams. SIAM Publishers, 2000. 408 p.

28. Zilic Z., Vranesic Z.G., Using decision diagrams to design ULMs for FPGAs. IEEE Transactions on Computers, vol.47, no.9, (1998), 971981