ФГБОУ ВПО Московский государственный университет

имени М.В. Ломоносова

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

КИБКАЛО Мария Александровна

Автоматная сложность

булевых функций из классов Поста

Специальность 05.13.17 – теоретические основы информатики

АВТОРЕФЕРАТ

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

Москва – 2013

Работа выполнена на кафедре математической теории интеллектуальных систем механико-математического факультета ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова».

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

Официальные оппоненты: доктор физико-математических наук, профессор Чечкин Александр Витальевич ФГВОУ ВПО «Военная академия Ракетных войск стратегического назначения имени Петра Великого»

кандидат физико-математических наук, ведущий инженер Зайцев Денис Владимирович ООО «ЭЛ ЭС АЙ Интернешнел Ресерч»

Ведущая организация: ФГБОУ ВПО «Российский государственный гуманитарный университет»

Защита диссертации состоится 25 декабря 2013 года в 16 час. 45 мин. на заседании диссертационного совета Д 501.002.16, созданного на базе ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова», по адресу: 119991, Москва, ГСП-1, Ленинские горы, д.1, ФГБОУ ВПО МГУ имени М.В. Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова»

(Москва, Ломоносовский проспект, д.27, сектор A, 8 этаж).

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

Ученый секретарь диссертационного совета Д.501.002.16, созданного на базе ФГБОУ ВПО МГУ, доктор физико-математических наук, профессор А.А.Корнев.

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

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

При реализации вычислений в процессорах естественным образом происходит переход от математики непрерывной к математике булевой. За два десятилетия процессоры прошли путь из 16-битных к 32-битным, а затем – к 64битным. Поскольку передача данных по каналам связи происходит последовательно, актуален вопрос о последовательном вычислении булевых функций по мере появления значений их переменных, то есть о вычислении булевых функций автоматами или двоичными диаграммами решений (binary decision diagram). Эта задача была поставлена еще в 1955 году Олегом Борисовичем Лупановым1.

За последнее десятилетие по сложности двоичных диаграмм решений появилось большое число работ. Одна из основных причин в том, что сложность реализации функций в небольших устройствах, как правило, приводит к коммерческому успеху. Тем не менее, оценка автоматной сложности классов Поста2 оставалась вне поля зрения исследователей. Этот пробел заполняет настоящая работа.

Лупанов О.Б. О возможностях синтеза схем из разнообразных элементов. Докл. АН СССР. Т. 103, № 4, 1955, с. 561- Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. Наука, Москва, Понятие конечного автомата окончательно сформировалось в результате исследования дискретных преобразователей информации3,4,5,6,7,8 и оценки их сложности (например, времени работы, числа операций для построения автомата или числа состояний автомата)9,10,11,12,. В настоящей работе под сложностью автомата понимается число его состояний.

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

Для представления функций часто используются упрощенные модели конечных автоматов – двоичные диаграммы решений (Binary Decision Diagrams – BDD), впервые примененные Брайантом13. Обзор свойств и особенностей различных видов BDD дан в диссертации Грёпля14. Такой способ отличается от представления функций конечными автоматами лишь несущественными деталями15,16.

В диссертации рассматриваются как булевы и k-значные функции (т.е.

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

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

Сложности автоматов и диаграмм решений, представляющих булевы функции, посвящена обширная литература. Рассматривались конкретные функции (сумматоры, умножители, пороговые функции, мультиплексоры, Shannon С.Е. A Mathematical Theory of Communication, Bell System Technical Journal, Volume 27, 1948, pp. 379-423, 623- Клини С.К.. Представление событий в нервных сетях и конечных автоматах. В Шеннон К.Э., Маккарти Дж. (ред.), Автоматы, Издательство иностранной литературы, Москва, 1956, с. 15- 5 Мур Э.Ф., Умозрительные эксперименты с последовательностными машинами. В Шеннон К.Э., Маккарти Дж. (ред.), Автоматы, Издательство иностранной литературы, Москва, 1956, с.179- 6 Минский М. Вычисления и автоматы, Мир, Москва, 7 Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. Наука, Москва, 8 Гилл А. Введение в теорию конечных автоматов. Мир, Москва, 9 Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений, Издательский дом «Вильямс», Москва, 10 Yu S., Chapter 2. Regular Languages, In: Rozenberg G., Salomaa A. (eds.) Handbook of Formal Languages, Springer-Verlag, 1998, pp. 41- 11 Wegener I. The Сomplexity of Boolean Аunctions. John Wiley & Sons Ltd. and B.G. Teubner, Stuttgart, 12 Wegener I. The Сomplexity of Boolean Аunctions. John Wiley & Sons Ltd. and B.G. Teubner, Stuttgart, 13 Bryant R.E. Graph Based Algorithms for Boolean Functions Manipulation, IEEE Transactions on Computers, Volume C-35, Number 8, 1986, pp. 677- 14 Grpl С. Binary Decision Diagrams for Random Boolean Functions; Dissertation, Humboldt Universitt zu Berlin, Wegener I. Branching Programs and Binary Decision Diagrams. Theory and Applications, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 16 Champarnaud J.-M., Duchamp G., Finite Automata and Boolean Functions. Proceedings of SCI’2001 (Systemics, Cybernetics and Informatics), XIV, Orlando, FL, 2001, pp. 126- функции бита скрытого веса и др.)17,18,19,20. Наибольший интерес исследователей вызвала функция прямого доступа к памяти (мультиплексор). Эта функция реализована во многих электронных схемах и замечательна тем, что при прямом обратном – сложность 22, Автоматная сложность класса всех булевых функций была впервые рассмотрена А.Д. Кузьминым24. Он получил для нее оценку функции Шеннона и отметил, что ее график имеет пилообразный вид:

Позже результаты Кузьмина были повторены и уточнены25,26,27. Хип и Мерсер28 получили формулу для максимальной сложности ROBDD и отметили осцилляции графика функции Шеннона. Шампорно и Пен получили (в терминах конечных автоматов) ту же оценку функции Шеннона для 2 и привели формулу 17 Hosaka K., Takenaga Y., Yajima S. On the Size of Ordered Binary Decision Diagrams Representing Threshold Functions, Proceedings of ISAAC’1994 (International Symposium on Algorithms and Computation), Springer-Verlag, 1994, pp. 87- 18 Sawitzki D. Lower Bounds on the OBDD Size of Graphs of Some Popular Functions. In: Vojt P., Bielikov M., Charron-Bost B., Skora O. (eds.): SOFSEM 2005, Lecture Notes in Computer Science 3381, Springer Verlag, 2005, pp. 298– 19 Bollig B. The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function. Information Processing Letters, Volume 106, Issue 4, 2008, pp. 171– 20 Bollig B., Range N., Wegener I. Exact OBDD Bounds for Some Fundamental Functions. Theory of Computing Systems, Volume 47, Number 2, 2010, pp. 593– 21 Michon J.-F., Yuns J.-B., Valarcher P. On Maximal QROBDD of Boolean Functions. Theoretical Informatics and Applications, Volume 39, Issue 4, 2005, pp. 677- 22 Wegener I. Branching Programs and Binary Decision Diagrams. Theory and Applications, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 23 Bollig B., Lbbing M., Sauerhoff M., Wegener I. On the Complexity of the Hidden Weighted Bit Function for Various BDD Models.

Theoretical Informatics and Applications, Volume 33, 1999, pp. 103- 24 Кузьмин А.Д. Реализация функций алгебры логики автоматами, нормальными алгорифмами и машинами Тьюринга.

Проблемы кибернетики, Выпуск 13, Наука, Москва, 1955, с. 75- 25 Lee C.Y. Representation of Switching Circuits by Binary Decision Programs. Bell System Technical Journal, Volume 38, 1959, pp.

985- 26 Liaw H.-T., Lin C.-S. On the OBDD-Representation of General Boolean Functions. IEEE Transactions on Computers, Volume 41, Number 6, 1992, pp. 661- 27 Breitbart Y., Hunt III H., Rosenkrantz D. On the Size of Binary Decision Diagrams Representing Boolean Functions, Theoretical Computer Science, Volume 145, Issue 1-2, 1995, pp. 45- 28 Heap M.A., Mercer M.R. Least Upper Bounds on OBDD Sizes, IEEE Transactions on Computers, Volume 43, Issue 6, 1994, pp.

764- 29 Champarnaud J.-M., Pin J.-E. A Maxmin Problem on Finite Automata. Discrete Applied Mathematics, Volume 23, Issue 1, 1989, pp. 91- где величина определяется через обращение функции () = 2 + или сравнение величин 2 и 22. Более детально функция Шеннона класса 2 была исследована Грёплем30,31,32. Он описал поведение ее графика вблизи особых точек вида = 2 + (вершин «зубцов» графика) и привел асимптотические оценки и точные формулы максимальной сложности QROBDD и ROBDD. Для нахождения параметра, входящего в состав формул, используется функция () = + log и ее оценки или сравнение величин 2 и 22. В работе Мишона, Юнеса и Валаршера33 введено понятие сложной функции из (имеющей QROBDD максимальной сложности), приведена диаграмма решений сложной функции и рассмотрены некоторые свойства и метрические характеристики сложных функций.

Сложность упорядоченных N-арных диаграмм решений для M-значных функций, рассматривалась Дворжаком34. В работе Грубера и Хольцера исследовалась средняя сложность детерминированных и недетерминированных автоматов, представляющих конечные языки. Сложность классов конечных языков длины, равной мощности входного алфавита, рассматривалась в статье Бржозовски и Константинидиса36.

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

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

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

Grpl C., Prmel H.J., A. Srivastav. Size and Structure of Random Ordered Binary Decision Diagrams (Extended Abstract). In:

Krob D., Meinel C., Morvan M. eds., STACS 98, Lecture Notes in Computer Science 1373, Springer-Verlag, 1998, pp. 238- 31 Grpl С. Binary Decision Diagrams for Random Boolean Functions; Dissertation, Humboldt Universitt zu Berlin, 32 Grpl C., Prmel H.J. and Srivastav A. On the Evolution of the Worst-Case OBDD Size, Information Processing Letters, Volume 77, Issue 1, 2001, pp. 1– 33 Michon J.-F., Yuns J.-B., Valarcher P. On Maximal QROBDD of Boolean Functions. Theoretical Informatics and Applications, Volume 39, Issue 4, 2005, pp. 677- 34 Dvorak V. Bounds on the Sizes of Decision Diagrams. Journal of Universal Computer Science, Volume 3, Issue 1, 1997, pp. 2- 35 Gruber H., Holzer M. On the Average State and Transition Complexity of Finite Languages, Theoretical Computer Science, Volume 387, Issue 2, 2007, pp. 167- 36 Brzozowski J., Konstantinidis S. State-Complexity Hierarchies of Uniform Languages of Alphabet-Size Length, Theoretical Computer Science, Volume 410, 2009, pp. 3223- Научная новизна.

представляющих булевы функции и конечные языки.

Построены автоматы максимальной или асимптотически максимальной сложности, представляющие функции из классов Поста,,, для всех, = 2,3,6,7. Получены точные формулы и/или асимптотика функции Шеннона для классов Поста. Согласно полученным результатам классы решетки Поста разбиваются на 3 группы в соответствии с асимптотическим поведением функции Шеннона.

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

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

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

Работа имеет теоретический характер. Ее результаты могут быть полезны специалистам-исследователям Московского государственного университета им. М. В. Ломоносова, Института прикладной математики им. М.

В. Келдыша РАН, Вычислительного центра им. А. А. Дородницына РАН, Института математики им. С. Л. Соболева СО РАН, Нижегородского государственного университета им. М. В. Лобачевского, Новосибирского государственного университета, Санкт-Петербургского государственного университета.

Практическая значимость.

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

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

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

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

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

Международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ академика В.А. Садовничего, секция «Интеллектуальные системы и компьютерные науки», 30 марта - 2 апреля 2009 г.

XVI Международная конференция студентов, аспирантов и молодых ученых «Ломоносов», 13-18 апреля 2009 г.

3. X международный научный семинар «Дискретная математика и ее приложения», 1-6 февраля 2010 г.

4. Научная конференция «Ломоносовские чтения», 16-25 апреля 2010 г.

Международный молодежный научный форум «ЛОМОНОСОВапреля 2011 г.

Научная конференция «Ломоносовские чтения», 11-25 ноября 2011 г.

X Международная конференция «Интеллектуальные системы и компьютерные науки», 5-10 декабря 2011 г.

8. XI международный семинар «Дискретная математика и ее приложения», посвященный 80-летию со дня рождения академика О.Б. Лупанова, 18-23 июня 2012 г.

Международный молодежный научный форум «ЛОМОНОСОВапреля 2013 г.

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

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

Точные формулы и асимптотики функции Шеннона для классов Поста.

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

Несводимость автоматной сложности булевых функций к другим мерам сложности булевых функций.

Публикации. Основное содержание диссертации опубликовано в работах автора, список которых приведен в конце автореферата [1–9].

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

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

ограничивая общности, можем считать, что = {0,1, … 1}, = {0,1, … 1}. Конечный алфавит мощности 2 будем обозначать через = {0,1}. Наборы из элементов алфавита можно рассматривать как слова длины в алфавите.

Обозначим через множество всех непустых слов конечной длины в алфавите Конечным языком в алфавите назовем любое непустое конечное подмножество. Множество языков в алфавите обозначим через ().

M-коллекцией языков из множества () назовем семейство попарно не пересекающихся языков {1, … 1 }. Множество M-коллекций языков из обозначим через (). Для M-коллекции языков из будем считать, что Определим детерминированный конечный автомат (ДКА) и инициальный конечный автомат (ИКА) согласно37. Конечным автоматом назовем набор где : – функция переходов, : – функция выходов.

Инициальным конечным автоматом (ИКА) 0 назовем конечный автомат с выделенным начальным состоянием 0 : 0 = (,,,,, 0 ).

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

Обозначим представимость языка в автомате 0 через 0 ~. Не ограничивая общности, считаем, что = \{0}.

ИКА 0 = (,,,,, 0 ) представляет M-коллекцию языков говорим также, что коллекция представима в автомате 0. Представимость коллекции в автомате 0 обозначим через 0 ~.

Обозначим через = { || = } множество слов длины и через = { | } – множество слов длины не более в алфавите.

множества языков () обозначим () = () и () = Сложностью ( ) автомата назовем || – число состояний в автомате. Cложностью языка () назовем величину Cложностью M-коллекции () назовем величину Функциями Шеннона множества () назовем величины Множество можно рассматривать как n-мерный N-значный куб = …. Через будем обозначать n-мерный двоичный куб. Через, Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. Наука, Москва, обозначим множество M-значных функций, определенных на,, = {|: } и положим, = 0,. Через 2 обозначим множество всех булевых функций от переменных и положим 2 = 0 2. Если, Существует взаимно-однозначное соответствие между языками из () и функциями из 2, определяемое условием ( = 1. Будем говорить, что в этом случае язык соответствует функции, ~. Будем считать, что автомат 0, представляющий язык (), представляет и соответствующую ему функцию 2 – 0 ~.

Назовем сложностью () булевой функции сложность () языка, ~. Функцией Шеннона множества булевых функций 2 назовем величину (, ) = max (). Аналогично определяется взаимнооднозначное соответствие между M-коллекциями из ( ()) и функциями из соответствует функции, ~. Будем считать, что автомат 0, представляющий коллекцию ( ()), представляет и соответствующую ей функцию Назовем сложностью () функции, сложность () Mколлекции, ~. Функцией Шеннона множества функций, назовем величину, (, ) = max ().

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

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

Найден простой способ вычисления параметра (высоты обратного дерева), входящего в состав формул сложности построенных автоматов. При этом не требуется сравнение величин вида 2 и 22 или обращение функций вида () = 2 +. В Приложении А приведены формулы вычисления высоты обратного дерева для построенных сложных автоматов.

В Главе 2 предложенные методы используются для оценки автоматной сложности замкнутых классов булевых функций. Приведем обозначения замкнутых классов, введенных Постом38,39, и их описания:

и/или 1.

, = 1, … 4 – все монотонные функции, все монотонные функции сохраняющие 0 и/или 1.

, = 1,2,3 – все самодвойственные -функции, все монотонные самодвойственные функции, все самодвойственные функции.

, = 2, … – все монотонные -функции, удовлетворяющие условию, = 2, … – все монотонные функции, удовлетворяющие условию, = 2, … – все монотонные -функции, удовлетворяющие условию, = 2, … – все монотонные функции, удовлетворяющие условию Вышеперечисленные классы образуют решетку Поста40.

и асимптотика функции Шеннона, а также построены автоматы, 38 Post E. Two-valued Iterative Systems. Princeton University Press, 39 Post E. Introduction to a General Theory of Elementary Propositions, American Journal of Mathematics, Volume 43, Number 1, 1921, pp. 163- 40 Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. Наука, Москва, представляющие самые сложные функции в классах. Показано, что классы 2, = 1,4,5,8, существенно сложнее в автоматном смысле, чем соответствующие классы.Считаем далее, что,, положим такая функция (), что существует такая функция, (), что Теорема 2.4. 2 и {, = 1,4,5,8} существует такая функция асимптотические оценки функции Шеннона и построены автоматы, представляющие сложные функции. Показано, что числовая ось, представляющая аргумент функции Шеннона (число переменных), распадается на последовательность пар интервалов, на бльших из которых функция Шеннона асимптотически равна сложности построенных функций, а на меньших превосходит ее не более, чем вдвое.

{1, 2, 3, 4 } существует такая функция (), что Для функции выполнено оценка { 2, = 2,3,6,7} существует такая функция,2 (), что Для функции,2 выполнено оценка функция, 2 (), что Для функции, выполнено асимптотическая оценка {, = 2,3,6,7} существует такая функция, (), что Для функции, выполнено асимптотическая оценка Далее рассматривается автоматная сложность классов Поста, 3.

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

существует такая функция, (), что 2, > max(log( + 1 log( + 2)), loglog( + 2) + 1), { \, = 1,4,5,8} существует такая функция, (), что выполнено () + 2] имеет место асимптотическая оценка Приведенные выше утверждения суммирует Теорема 2.15, опирающаяся на известные оценки сложности41.

Теорема 2.15. Для следующих классов достижимы точные значения автоматной сложности:

Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. Наука, Москва, Таким образом, имеет место разбиение решетки классов Поста на три пояса в соответствии с асимптотикой автоматной сложности. На Рис. 1 изображена решетка Поста с поясами, обозначенными черным, серым и белым цветами.

Рис. 1. Разбиение решетки классов Поста в соответствии с асимптотикой автоматной Пусть = { } – строго возрастающая последовательность,. Если – один из классов первого пояса 1, 2, 3, 4, 1, 3, 1, 4, 5, 8,,,, или его подмножество, положим (, ) =. Если – один из классов третьего пояса, (, ) =.

Назовем константой автоматной сложности последовательности функций { }, ( ) и представляющих их автоматов {, }, где – класс Поста, величины (если пределы существуют). Назовем константой автоматной сложности для и где – класс Поста или его подмножество, величину (если предел существует).

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

Теорема 3.1. 1, [, (),, ( + 1)) существует такая Mколлекция языков,, ( ()), что Теорема 3.2. При для функции Шеннона, верно Теорема 3.3. 1, (, ( 1),, ()] существует такая Mколлекция языков,, ( ()), что и при ~ В Главе 4 рассматриваются другие меры сложности булевых функций и их классов, а также их соотношение с автоматной сложностью.

Покрывающим автоматом для ИКА, представляющего конечный язык, назовем автомат, представляющий (не обязательно конечный) язык Покрывающим автоматом для ИКА, представляющего Mколлекцию языков (), назовем автомат, представляющий M-коллекцию (не обязательно конечных) попарно не пересекающихся языков = {1, … 1 },, =, где – максимальная длина слова в языках 1, … 1.

Обозначим через то, что автомат является покрывающим для ИКА.

Сложностью покрытия автомата назовем величину ( ) = min ( ). Cложностью покрытия языка () назовем величину () = min ( ). Cложностью покрытия M-коллекции () назовем величину () = min ( ). Сложностью покрытия () функции из 2 или, считаем сложность покрытия соответствующего языка или коллекции.

Cmpeanu C., Sntean N., S., Yu S. Minimal Cover Automata for Finite Languages, In: Champarnaud J.-M., Maurel D., Ziadi D.

eds., WIA’98, Lecture Notes in Computer Science 1660, Springer-Verlag, 1999, pp. 43- Было показано43,44,45,46, что для некоторых языков можно построить покрывающие автоматы значительно меньшей сложности, чем автоматы, представляющие эти языки. Однако, для сложных функций из теорем Главы 2 и сложных коллекций из теорем Главы 3 это не так:

Теорема 4.1. Для функции Теорема 4.2. Для коллекции {,,,,, } выполнено То есть, построение покрывающих автоматов для этих функций и коллекций не приводит к уменьшению сложности.

Булеву функцию от переменных можно представить в виде полинома Жегалкина47, причем существует взаимно-однозначное соответствие между булевыми функциями и полиномами Жегалкина:

Сложность полинома Жегалкина () функции определяется как число ненулевых коэффициентов. Сложности реализации булевых функций полиномами Жегалкина и конечными автоматами не связаны друг с другом. Так, для функции 0, равной единице лишь на наборе 0 выполнено (0 ) = 2 и (0 ) = + 1. В cвою очередь, сложность полиномов Жегалкина для булевых функций, представляемых сложными автоматами может кардинально отличаться.

Теорема 4.3. При существуют функции и для которых Автоматная сложность классов Поста коррелирует с некоторыми другими мерами сложности. Например, классы Поста распадаются относительно логарифма мощности класса на те же 3 пояса. Для классов первого пояса 43 Champarnaud J.-M., Michon J.-F. Automata and Binary Decision Diagrams, In: Champarnaud J.-M., Maurel D., Ziadi D. eds., WIA’98, Lecture Notes in Computer Science 1660, Springer-Verlag, 1999, pp. 178- 44 Champarnaud J.-M., Duchamp G., Finite Automata and Boolean Functions. Proceedings of SCI’2001 (Systemics, Cybernetics and Informatics), XIV, Orlando, FL, 2001, pp. 126- 45 Champarnaud J.-M., Pin J.-E. A Maxmin Problem on Finite Automata. Discrete Applied Mathematics, Volume 23, Issue 1, 1989, pp. 91- 46 Krner H. A Time and Space Efficient Algorithm for Minimizing Cover Automata for Finite Languages, International Journal of Foundations of Computer Science, Volume 14, Issue 6, 2003, pp. 1071– 47 Яблонский С.В. Введение в дискретную математику. Наука, Москва, выполнено log || = (2 )48,49,50,51. Для классов второго пояса выполнено log || ( )52,53,54,55. Для классов третьего пояса log || = ().

Функция Шеннона для сложности схем из функциональных элементов для классов первого пояса имеет порядок ( ), для классов второго пояса – )56,57,58, для классов третьего пояса – ().

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

B последнем параграфе приведены формулировки основных результатов в терминах QROBDD и ROBDD.

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

получены асимптотические оценки функции Шеннона и построены автоматы, Яблонский С.В. Введение в дискретную математику. Наука, Москва, Коршунов А.Д. Число k-неразделенных семейств подмножеств n-элементного множества (k-неразделенных булевых функций). Часть 1. Случай четных n и = 2. Дискретный анализ и исследование операций, Серия 1, Том 10, № 4, 2003, c.

31- 50 Коршунов А.Д. Число k-неразделенных семейств подмножеств n-элементного множества (k-неразделенных булевых функций). Часть II. Случай нечетных n и = 2. Дискретный анализ и исследование операций, Серия 1, Том 12, № 1, 2005, c. 12- 51 Коршунов А.Д. Число k-неразделенных семейств подмножеств n-элементного множества (k-неразделенных булевых функций). Часть III. Случай 3 и произвольных n. Дискретный анализ и исследование операций, Серия 1, Том 12, № 3, 2005, c. 60- 52 Коршунов А.Д. О мощности и структуре некоторых замкнутых классов Поста (семейств подмножеств конечного множества), Модели и методы оптимизации, Наука, Новосибирск, 1988, с. 159- 53 Коршунов А.Д. О числе и строении монотонных булевых функций. В: Лупанов О.Б. (ред.) Дискретная математика и ее приложения: Сборник лекций молодежных научных школ по дискретной математике и ее приложениям. Часть 1, МГУ им.

М.В. Ломоносова, Механико-математический факультет, Москва, 2001, с. 34- 54 Сапоженко А.А. О числе антицепей в многослойных ранжированных множествах, Дискретная математика, 1989, Том 1, Выпуск 2, с. 110- 55 Емеличев А.В., Сапоженко А.А. О числе монотонных самодвойственных функций. Материалы Второго Всесоюзного семинара по дискретной математике и ее приложениям. Издательство МГУ, Москва, 1988, с. 140- 56 Лупанов О.Б. Об одном методе синтеза схем. Известия вузов. Радиофизика, 1, 1958, с. 120- 57 Угольников А.Б. О реализации функций из замкнутых классов схемами из функциональных элементов. Математические вопросы кибернетики, Выпуск 1, Москва, Наука, 1988, с. 89- 58 Угольников А.Б. О реализации монотонных функций схемами из функциональных элементов. Проблемы кибернетики, Выпуск 32, Москва, Наука, 1976, с. 167- представляющие сложные функции. Показано, что числовая ось, представляющая аргумент функции Шеннона (число переменных), распадается на последовательность пар интервалов, на бльших из которых функция Шеннона асимптотически равна сложности построенных функций, а на меньших превосходит ее не более, чем вдвое. Разработан оригинальный метод синтеза сложных автоматов, представляющих монотонные функции, для чего используется специальное отображение единичного куба в множество монотонных булевых функций.

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

Получены точные значения и асимптотика функции Шеннона для классов конечных языков () и (). Построены автоматы, представляющие самые сложные коллекции языков. Такие автоматы моделируют процесс выбора одного из возможных решений при N альтернативах на каждом шаге. Найден простой способ вычисления параметра (высоты обратного дерева), входящего в состав формул сложности построенных автоматов. При этом не требуется сравнение величин вида 2 и 22 или обращение функций вида () = 2 +.

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

Благодарности. Автор выражает глубокую благодарность академику, профессору В.Б. Кудрявцеву и д.ф.-м.н., профессору Д.Н. Бабину за постановку задач, постоянную поддержку и внимание к работе.

Работы автора по теме диссертации Основное содержание диссертации опубликовано в следующих работах автора:

Кибкало М.А. О сложности представления коллекции языков в конечных автоматах, Интеллектуальные системы, Том 13, Выпуск 1-4, 2010, сс.

347- Кибкало М.А. Об автоматной сложности некоторых классов булевых функций, Интеллектуальные системы, Том 14, Выпуск 1-4, 2010, сс. 319-322.

Кибкало М.А. Об автоматной сложности классов Поста булевых функций, Интеллектуальные системы, Том 15, Выпуск 1-4, 2011, сс. 379-400.

Кибкало М.А. Представление коллекций языков в конечных автоматах. Труды Международной конференции «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ академика В.А. Садовничего, секция «Интеллектуальные системы и компьютерные науки», 2009, сс. 358-359.

Кибкало М.А. О сложности представления коллекций языков в конечных автоматах. Материалы докладов XVI Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», секция «Математика и механика», 2009, сc. 32-33.

Кибкало М.А. Представление коллекций языков автоматами.

Материалы X международного семинара «Дискретная математика и ее приложения», Cекция «Теория интеллектуальных систем и автоматов», 2010, сс.

361 – 363.

Кибкало М.А. Автоматная сложность классов Поста. Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2011», секция «Математика и механика», подсекция «Математика», 2011.

Кибкало М.А. Оценки автоматной сложности классов булевых функций. Материалы X Международной конференции «Интеллектуальные системы и компьютерные науки», 2011.

Кибкало М.А. Об автоматной сложности некоторых классов Поста булевых функций. Материалы XI международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О.Б. Лупанова, Cекция «Теория интеллектуальных систем и автоматов», 2012, сс. 343-346.