WWW.KONFERENCIYA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Конференции, лекции

 

ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ

им. М. В. КЕЛДЫША

РОССИЙСКОЙ АКАДЕМИИ НАУК

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

им. М. В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

ДИСКРЕТНАЯ МАТЕМАТИКА

И ЕЕ ПРИЛОЖЕНИЯ

СБОРНИК ЛЕКЦИЙ

VII Москва 2013 Институт прикладной математики им. М. В. Келдыша Российской Академии Наук Московский государственный университет им. М.В. Ломоносова Механико-математический факультет

ДИСКРЕТНАЯ МАТЕМАТИКА

И ЕЕ ПРИЛОЖЕНИЯ

СБОРНИК ЛЕКЦИЙ

МОЛОДЕЖНЫХ НАУЧНЫХ ШКОЛ

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

И ЕЕ ПРИЛОЖЕНИЯМ

VII Москва Издание осуществлено при M34 поддержке Российского фонда фундаментальных исследоваУДК 519. ний по проекту 13–01– Дискретная математика и ее приложения: Сборник лекций молодежных М научных школ по дискретной математике и ее приложениям. Выпуск VII.

Под редакцией А. В. Чашкина. — М.: Изд-во ИПМ РАН, 2013. — 56 с.

Седьмой выпуск лекций содержит лекции, прочитанные на IX молодежной научной школе по дискретной математике и ее приложениям, проходившей в Москве в ИПМ им. М. В. Келдыша РАН с 16 по 21 сентября 2013 г. при поддержке Российского фонда фундаментальных исследований (проект 13–01–06831). Для студентов, аспирантов и научных работников в области дискретной математики и математической кибернетики.

Научное издание

ДИСКРЕТНАЯ МАТЕМАТИКА

И ЕЕ ПРИЛОЖЕНИЯ

Сборник лекций Выпуск VII Под общей редакцией А. В. ЧАШКИНА Редакционная группа:

Ю. В. Бородина, Е. Е. Трифонова, А. Д. Яшунский Ответственный за выпуск О. С. Дудакова c Коллектив авторов,

СЛОЖНОСТЬ РАСШИФРОВКИ

ПОРОГОВЫХ ФУНКЦИЙ

Н. Ю. Золотых Нижегородский государственный университет им. Н. И. Лобачевского, Нижний Новгород, пр. Гагарина, д. zolotykh@vmk.unn.ru Предлагается обзор основных результатов, касающихся задачи расшифровки пороговой функции многозначной логики: строение и мощность наименьшего разрешающего множества, сложность расшифровки и др. Лекция является переработанным вариантом статьи [1].

1. Определения и предварительные результаты Пусть = {0, 1,..., 1}, 1. Обозначим (, ) множество всех функций : {0, 1}, в частности, (, 2) — множество всех булевых функций переменных. Рассмотрим некоторый класс (, ).

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

По-видимому, впервые задача расшифровки рассматривалась В. К. Коробковым и Т. Л. Резником [2–4] для класса монотонных булевых функций. Сложность расшифровки монотонных булевых функций установил Ж. Ансель [5].

Оптимальный по числу вопросов и используемой памяти алгоритм расшифровки предложил Н. А. Соколов [6]. Задачу расшифровки монотонных функций многозначной логики рассматривали В. К. Коробков [7], В. Б. Алексеев [8], А. В. Сержантов [9] и др. М. В. Горяинов и А. А. Сапоженко [10] предложили алгоритм расшифровки монотонных функций на частично упорядоченных множествах. Другие сведения о монотонных функциях и задаче расшифровки монотонных функций приведены в обзоре А. Д. Коршунова [11]. Рассматриваются задачи расшифровки функций из других классов (А. А. Вороненко, В. В. Осокин, Э. Э. Гасанов и др.). Задача интенсивно изучается в рамках теории тестов [12] и вычислительной теории машинного обучения (Computational Learning Theory) [13].

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

Обозначим (, ) множество всех пороговых функций, заданных на, т. е.

множество пороговых функций -значной логики переменных. В частности, (, 2) — множество всех булевых пороговых функций переменных.

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

Задача расшифровки пороговых функций тесно связана с проблемой оценки числа таких функций. Заметим, что задача оценки числа пороговых функция является весьма сложной. До сих пор не известна асимптотика числа пороговых булевых функций. Из результатов Л. Шлефли [15] о числе открытых областей, получаемых при разбиении -мерного пространства гиперплоскостями, легко получить верхнюю оценку:

С. Яджима и Т. Ибараки [16] получили первую нетривиальную нижнюю оценку:

Ю. А. Зуев [17, 18] доказал, что тем самым установив асимптотику логарифма числа булевых пороговых функций:

При доказательстве асимптотики использовался один комбинаторно-вероятностный результат о (±1)-матрицах, полученный А. М. Одлыжко [19]. Другой подход к получению асимптотического равенства (2), также использующий лемму Одлыжко, предложил А. А. Ирматов [20].



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

Для числа пороговых функций -значной логики А. А. Ирматов и Ж. Д. Ковиянич [22] получили нижнюю оценку:

справделивую для достаточно больших. Отсюда и из оценки Шлефли получается асимптотика логарифма числа таких функций:

Для пороговых функций -значной логик двух переменных в [23] получена оценка:

Пусть — алгоритм расшифровки в классе (, ). Обозначим через (, ) число обращений к оракулу при расшифровке функции.

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

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

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

Рассмотрим два примера. Если — класс монотонных функций переменных, то для любой функции ее тупиковое разрешающее множество единственно, совпадает со множеством существенных точек и состоит из верхних нулей и нижних единиц функции [2, 8].

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

Пусть (, ) — мощность наименьшего разрешающего множества для функции относительно класса. Длиной обучения в классе называется Нетрудно видеть, что поэтому Нетрудно видеть, что для любого класса Под средней мощностью наименьшего разрешающего множества в классе понимаем величину Если — полиэдр (выпуклое многогранное множество) в R, то обозначим Vert множество его вершин. Если R, то обозначим Conv — выпуклую оболочку множества, а Cone — коническую оболочку этого множества (множество всех неотрицательных линейных комбинаций).

2. Характеризация разрешающего множества Обозначим Легко видеть, что для функции (, 2), тождественно равной 0 или 1, поэтому Итак, (, ) и (, ) зависят от экспоненциально, поэтому далее в первую очередь нас будет интересовать асимптотика величин (, ) и (, ) при стремлении и фиксированном.

Следующее построение хорошо известно в пороговой логике. С каждой функцией (, ) в пространстве коэффициентов 0, 1,..., свяжем так называемый конус ( ) разделяющих функционалов, заданный как множество решений следующей системы:

Пусть ( ) ( = 0, 1). Рассмотрим подсистему системы (3):

Утверждение. Для того, чтобы множество = 0 1, ( ) ( = 0, 1) было разрешающим для (, ), необходимо и достаточно, чтобы система неравенств (3) была эквивалентна системе неравенств (4).

Можно доказать, что в системе (3) найдется минимальная подсистема, эквивалентная всей системе:

Следствие 1. Для любой (, ) множество = 0 1, где (, ) ( = 0, 1), является тупиковым разрешающим тогда и только тогда, когда = ( ) ( = 0, 1).

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

Следствие 2. Для любой (, ) существует единственное тупиковое разрешающее множество ( ) = 0 ( ) 1 ( ), совпадающее с множеством всех существенных точек функции.

Теорема Оценивая | Vert Conv ( )| сверху, В. Н. Шевченко [24] доказал, что Более точную (при фиксированном ) оценку получил Т. Хегедюш [25] на основе результатов [26] о числе вершин в неявно заданных целочисленных полиэдрах:

Полиэдр называется целочисленным, если все его вершины целые. Рассмотрим полиэдр = { R : 0 }, где Z, 0 Z, и целочисленный полиэдр Z = Conv( Z ). Проблемой получения оценок | Vert Z | занимались В.Н. Шевченко, С.И. Веселов, А. Ю. Чирков, А. С. Хейес, Д. К. Ларман, И. Барани, Р. Хоу, Л. Ловаш, У. Кук, М. Хартманн, Р. Каннан, К. МакДиармид и др. (см. обзор работ в [27]).

Полное описание структуры разрешающего множества дает следующая Теорема где = 1 и объединение берется по всем = (1, 2,..., ), 0, таким, что неравенство (1) является пороговым для функции.

На ее основе для (, ) получена первая нетривиальная оценка снизу.

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

В частности, в [30] получена двусторонняя оценка:

Долгое время существовала гипотеза (, ) = (log2 ) (для любого фиксированного 2 и ). Гипотеза доказана в [1], см. также [31]. При доказательстве используется новая характеризация [32] тупикового разрешающего множества пороговой ( функции.





Теорема Следствие На рис. 1 изображены множества 0 ( ) и 1 ( ) для функция (2, 4), заданной пороговым неравенством 21 + 2 3. Наименьшее разрешающее множество образуют точки В рассматриваемом случае имеем ( ) = Cone{(1), (2) }, где (1) = (2) (1) = (3, 2), (2) = (1) (2) = (0, 1).

Условие (5) близко к свойству разделенности, введенному В. Н. Шевченко в [33] в связи с исследованием задачи о числе вершин неявно заданных целочисленных полиэдров. Обозначим Z+ множество неотрицательных целых чисел. Говорят, что множество Z обладает свойством разделенности [33], Развивая соответствующий аппарат, удается доказать следующий результат.

Приведем один результат о средней мощности наименьшего разрешающего множества пороговой функции. М. Энтони, Г. Брайтуэлл, Д. Коэн, Дж. ШоуТейлор [34] показали, что Этот результат можно обобщить (см. [35]) на случай пороговых функций -значной логики:

3. Длина обучения пороговой функции двух переменных Возможные значения мощности наименьшего разрешающего множества пороговой функции, зависящей от двух переменных, суть 3 и 4. Таким образом, справедлива (0, 7) Рассмотрим функцию (2, ) (для произвольного 5), определяемую пороговым неравенством 31 + 22 6. В этом случае (см. рис. 2) множество ( ) содержит 3 точки: (2, 0), (0, 3), (1, 2). Точка (0, 4), например, не принадлежит ( ), так как никакая опорная к Conv 1 ( ) прямая, проходящая через (0, 4), не является разделяющей для 0 ( ), 1 ( ).

Для функции (2, ), 8, определяемой пороговым неравенством 31 + 22 13, разрешающее множество () состоит из 4 точек: (3, 2), (1, 5), (4, 1), (0, 7) (см. рис. 3).

Более того, среднее значение мощности наименьшего разрешающего множества пороговой функции двух переменных асимптотически равно 7/2.

Теорема Отсюда получаем интересное геометрическое Следствие. Среди ограниченных областей, получаемых при разбиении плоскости параметров 1, 2 всеми прямыми 1 1 + 2 2 = 1, где (1, 2 ) принадлежит множеству {0, 1,..., 1}2, встречаются только треугольники и четырехугольники, причем их количества асимптотически равны.

Аналогичный результат получается, если разбивать плоскость параметров 1, 2 прямыми 1 1 +2 2 = 1, где (1, 2 ) {1, 2,..., }2 и т. п. В частности, на рис. 4 представлено разбиение указанными прямыми первой четверти плоскости.

4. Алгоритмы расшифровки пороговых функций В. Н. Шевченко [14] предложил для расшифровки пороговых функций алгоритм 0, у которого при любом фиксированном величина (0 ) ограничена полиномом от log. Т.Хегедюш [25] показал, что Н. Ю. Золотых, В. Н. Шевченко [38] и Т. Хегедюш [39] построили алгоритм 1, для которого (1 ) = (log ). Из теоремы 4 следует, что (1 ) = (log1 ).

Более того, применяя результаты М. Ю. Мошкова [40, 41] в теории тестов, можно построить (ср. [39]) алгоритм, для которого Итак, справедлива Теорема 8.

Для = 2 в [28, 42] построен алгоритм, для которого Работа выполнена в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007–2013 годы», госконтракт 11.519.11.4015.

Золотых Н. Ю., Чирков А. Ю. Сложность расшифровки пороговых функций многозначной логики // Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О. Б. Лупанова (18–23 июня 2012 г.) / Под редакцией О.М. Касим-Заде. — М.: Изд-во механикоматем. факультета МГУ. — 2012. — С. 63–77.

Сложность расшифровки пороговых функций Коробков В. К., Резник Т. Л. О некоторых алгоритмах вычисления монотонных функций алгебры логики // Доклады АН СССР. — 1962. — V. 147, № 5. — С. 1022–1025.

Коробков В. К. Оценка числа монотонных функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики // Доклады АН СССР. — 1963. — V. 150, № 4. — C. 744–747.

Коробков В. К. О монотонных функциях алгебры логики // Проблемы кибернетики. Вып. 13. — М.: Наука, 1965. — C. 5–28.

Hansel G. Sur le nombre des fonctions boolennes monotones de variables // C. R. Acad. Sci. — Paris, 1966. — V. 262, № 20. — P. 1088–1090.

Соколов Н. А. Оптимальная расшифровка монотонных булевых функций // Журн. вычисл. математики и матем. физики. — 1987. — V. 27, № 12. — C. 1878–1887.

Коробков В. К. Некоторые обобщения задачи «расшифровки» монотонных функций алгебры логики // Дискретный анализ. Сб. тр. Вып. 5. — Новосибирск: изд-во Ин-та матем. СО АН СССР, 1965. — C. 19–25.

Алексеев В. Б. О расшифровке некоторых классов монотонных многозначных функций // Журн. вычисл. математики и матем. физики. — 1976. — V. 16, № 1. — C. 189–198.

Сержантов А. В. Оптимальный алгоритм расшифровки некоторых классов монотонных функций // Журн. вычисл. математики и матем.

физики. — 1983. — V. 23, № 1. — C. 206–212.

Горяинов М. В., Сапоженко А. А. О расшифровке монотонных функций на частично упорядоченных множествах // Дискретный анализ и исследование операций. — 1995. — Т. 2, № 3. — С. 79–80.

Коршунов А. Д. Монотонные булевы функции // Успехи матем. наук. — 2003. — Т. 58, № 5. — C. 5–108.

Чегис И. А., Яблонский С. В. Логические способы контроля работы 12.

электрических схем // Тр. Матем. ин-та АН СССР. — 1958. — Т. 51. — Angluin D. Queries and concept learning // Machine Learning. — 1988. — 13.

Шевченко В. Н. О расшифровке пороговых функции многозначной логики // Комбинаторно-алгебраические методы в прикл. матем. — Горький: Горьковский гос. ун-т, 1987. — С. 155–163.

Schlfli L. Gesammelte mathematisce Abhanglugen. Band 1. — Basel:

15.

Verlag Birkhuzer, 1950.

Yajima S., Ibaraki T. A lower bound of the number of threshold functions // 16.

IEEE Trans. on Electronic Comput. — 1965. — V. 14, № 6. — P. 929–929.

Зуев Ю. А. Асимптотика логарифма числа пороговых функций алгебры логики // Доклады АН СССР. — 1989. — Т. 306, № 3. — С. 528–530.

Зуев Ю. А. Комбинаторно-вероятностные и геометрические методы в 18.

пороговой логике // Дискретная математика. — 1991. — Т. 3, № 2. — Odlyzko A. M. On subspaces spanned by random selection of ±1 vectors // 19.

J. Combin. Theory, A. — 1988. — V. 47, № 1. — С. 124–133.

Ирматов А. А. О числе пороговых функций // Дискретная математика. — 1993. — Т. 5, № 3. — С. 40–43.

Зуев Ю. А. Пороговые функции и пороговые представления булевых 21.

функций // Матем. вопросы кибернетики. Вып. 5. — М.: Физматлит, Ирматов А. А., Ковиянич Ж. Д. Об асимптотике логарифма числа 22.

пороговых функций -значной логики // Дискретная математика. — Koplowitz J., Lindenbaum M., Bruckstein A. M. The number of digital 23.

straight lines on an grid // IEEE Trans. Inform. Theory. — 1990. — Шевченко В. Н. О некоторых функциях многозначной логики, связанных с целочисленным программированием // Методы дискретного анализа в теории графов и схем. Вып. 42. — Новосибирск: Ин-т матем. СО АН СССР, 1985. — С. 99–108.

Hegeds T. Geometrical concept learning and convex polytopes // Proc.

25.

7th Ann. ACM Conf. on Computational Learning Theory. — New York:

ACM Press, 1994. — P. 228–236.

Cook W., Hartmann M., Kannan R., McDiarmid C. On integer points in 26.

polyhedra // Combinatorica. — 1992. — V. 12, No 1. — P. 27–37.

Веселов С. И., Чирков А. Ю. Оценки числа вершин целых полиэдров // 27.

Дискретный анализ и исследование операций. Серия 2. — 2007. — Т. 14, Шевченко В. Н., Золотых Н. Ю. О сложности расшифровки пороговых функций -значной логики // Доклады Академии наук. — 1998. — Золотых Н. Ю., Шевченко В. Н. О нижней оценке сложности расшифровки пороговых функций -значной логики // Журн. вычисл. матем.

и матем. физики. — 1999. — Т. 39, № 2. — С. 346–352.

Золотых Н. Ю. Оценки мощности минимального разрешающего множества пороговой функции многозначной логики // Матем. вопросы кибернетики. Вып. 17. — М.: Физматлит, 2008. — С. 159–168.

Chirkov A. Yu., Zolotykh N. Yu. On the number of irreducible points in 31.

polyhedra. arXiv:1306.4289. — 2013.

Сложность расшифровки пороговых функций Золотых Н. Ю., Чирков А. Ю. О верхней оценке мощности минимального разрешающего множества пороговой функции // Дискретный анализ и исследование операций. — 2012. — Т. 19, №5. — С. 35–46.

Шевченко В. Н. О числе крайних точек в целочисленном программировании // Кибернетика. — 1981. — № 2. — С. 133–134.

Antony M., Brightwell G., Shawe-Taylor J. On exact specification by 34.

labelled examples // Discrete Applied Mathematics. — 1995. — V. 61, Вировлянская М. А., Золотых Н. Ю. Верхняя оценка средней мощности минимального разрешающего множества пороговой функции многозначной логики // Вестник Нижегород. гос. ун-та им. Н. И. Лобачевского. Матем. моделирование и оптимальное управление. — Нижний Новгород.: изд-во ННГУ, 2003. — С. 238–246.

Золотых Н. Ю. О сложности расшифровки пороговых функций, зависящих от двух переменных // Материалы XI Межгосударственной школы-семинара «Синтез и сложность управляющих систем».

Часть I. — М.: Изд-во Центра прикладных исследований при механикоматем. ф-те МГУ, 2001. — С. 74–79.

Alekseyev M. A., Basova M. G., Zolotykh N. Yu. The average cardinality 37.

of the minimal teaching set of a threshold function on a two-dimensional rectangular grid. arXiv:1307.1058. — 2013.

Золотых Н. Ю., Шевченко В. Н. Расшифровка пороговых функций 38.

-значной логики // Дискретный анализ и иссл. операций. — 1995. — Hegeds T. Generalized teaching dimensions and the query complexity of 39.

learning // Proc. 8th Ann. ACM Conf. on Computational Learning Theory (COLT’95). — New York: ACM Press, 1995. — P. 108–117.

Мошков М. Ю. Об условных тестах // Доклады АН СССР. — 1982. — 40.

Мошков М. Ю. Условные тесты // Проблемы кибернетики. Вып. 40. — 41.

М.: Наука, 1983. — C. 131–170.

Золотых Н. Ю. Пороговые функции, зависящие от двух переменных:

42.

сложность расшифровки и мощность разрешающего множества // Материалы четвертой молодежной научной школы по дискретной математике и ее приложениям. — М.: Изд-во механико-матем. факультета МГУ, 2000. — С. 48–54.

СВОЙСТВА ЦЕЛОЧИСЛЕННЫХ

ПАСКАЛЬ-ФУНКЦИЙ, ДОКАЗУЕМЫЕ НА ОСНОВЕ

АРИФМЕТИКИ ПО МОДУЛЮ Санкт-Петербургский государственный университет, Санкт-Петербург, Университетская наб., д. 7/ В рамках конечно-дискретной математики ниже предлагаются математические модели целочисленных вычислений по модулю, особенно при = 216, характерного для IBM-совместимых персональных компьютеров.

Эти модели более точно отражают практику использования компьютеров.

Вводятся РАМ (равнодоступная адресная машина), РАСП (равнодоступная адресная машина с хранимой программой) и паскаль-программы, использующие арифметические операции по модулю с остатками из сегмента [[/2], [/2] 1 + ( mod 2)].

Описывается язык индексных логик первого порядка, позволяющий сформулировать математические свойства таких всюду применимых паскаль-программ. Доказывается P-SPACE-полнота задачи проверки тождественной истинности в таких логиках, содержащих арифметические операции по модулю. Устанавливается, что размера памяти 2+2 достаточно для вычисления продолжения посредством любой наперед заданной константой РАСП-программы по модулю с памятью до всюду применимой.

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

Использование в этом случае традиционной для языка паскаль записи вызова функции или предиката в выражении (в дальнейшем используется терСвойства целочисленных паскаль-функций мин «индексный терм») не требует уточнения способа вычисления выражения. В случае же использования незавершаемого выражения, обозначенного знаком ?, при одной интерпретации имеет место равенство ? * 0 = 0 (при параллельном вычислении значений всех подвыражений) или равенство ? * 0 =?

(при последовательном вычислении значений всех подвыражений).

В работе [1] определены РАМ и РАСП как модели целочисленных вычислений, использующие один (по существу, динамический) линейный массив для записи целых чисел произвольной длины.

Определим понятия РАМ и РАСП по модулю, использующие арифметические операции по модулю с остатками, принадлежащими сегменту [[/2], [/2] 1 + ( mod 2)]. Здесь [/2] — целая часть от деления на 2, ( mod 2) — остаток от деления на 2. Последовательность таких остатков от деления на является целым числом, записанным по основанию с цифрами из сегмента [[/2], [/2] 1 + ( mod 2)]. Предлагается использовать один массив целых чисел из этого же сегмента, но произвольной размерности (одномерный, двухмерный,... ), одной и той же для каждой программы. Длина массива по каждому измерению не превосходит. При этом исходные данные располагаются в первых измерениях для РАМ и РАСП, а программа для РАСП вместе со счетчиком команд располагается в последних измерениях. Кроме того, счетчик команд находится в самых последних измерениях массива. Признаком конца данных (и начала программы для РАСП, а также начала счетчика команд) может служить дополнительное измерение, использующее в качестве двух границ своего измерения только одну и ту же константу, например, единицу.

Таким образом, в массиве любой РАМ- и РАСП-программы по модулю может быть только конечное число элементов, но это число не может быть ограничено сверху (из-за возможно растущего числа измерений массивов в последовательности как РАМ-, так и РАСП-программ).

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

Прежде всего, вводится понятие индексного терма, определение которого получается из определения терма (см., например, [2]) с помощью замены слова «терм» на слова «индексный терм» и добавления в определение индексного терма следующей дополнительной конструкции: индексным термом является любая переменная для массива, за которой следует последовательность разделенных запятой индексных термов, заключенная в квадратные скобки. Постоянным индексным термом называется индексный терм, не содержащий предметных переменных или массивов. Таким образом разрешается испольН. К. Косовский зовать элементы массивов с одним и тем же для РАМ и РАСП по модулю числом измерений и с разным числом измерений для паскаль-программ по модулю.

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

Речь идет о диапазонах вида 1..2, где 1 и 2 — постоянные индексные термы. В случае, когда 1 = 2, вместо диапазона 1..1 разрешается использовать постоянный индексный терм 1. Это расширяет возможности языка паскаль, предоставленные при описании в нем массивов, поскольку вместо диапазона может находиться один постоянный индексный терм вместо его повторного указания через две последовательные точки (..).

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

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

Аналогично может быть определено понятие тождественно истинной индексной формулы в конечной сигнатуре по модулю с учетом интерпретации паскаль-функций и паскаль-предикатов, вычислимых по модулю с остатками из сегмента [[/2], [/2] 1 + ( mod 2)].

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

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

Чисто логический вариант следующей теоремы был сформулирован в [3].

Определение понятия P-SPACE-полноты задачи можно найти в [1].

Теорема 1. Каковы бы ни были натуральное число (при 2) и содержащая {+,, *, 0;

Тогда Теорема Тогда Теорема 12 [27].

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

Положим (;, ) = max (), где максимум берется по всем не всюду определенным матрицам из строк и столбцов, имеющих определенных элементов и (1 ) символов *.

Э. И. Нечипорук получил следующий результат.

Теорема Тогда В некотором смысле окончательное (при естественном ограничении, что число полюсов существенно меньше сложности) асимптотически точное решение задачи о сложности реализации не всюду определенных матриц вентильными схемами глубины 2 было предложено А. Е. Андреевым в 1987 г.

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

Э. И. Нечипоруком исследовалась [28] сложность реализации следующей последовательности булевых матриц. Пусть — простое число и = 2. Обозначим через, квадратную булеву матрицу порядка, получающуюся из диагональной матрицы циклическим сдвигом ее столбцов на (mod ) позиций. Из этих блоков образуем квадратную матрицу порядка :

Теорема 15 [28]. Всякая минимальная вентильная схема, реализующая матрицу, состоит из 3/2 вентилей, т. е. ( ) = 3/2.

Несколько позже аналогичные результаты были получены E. Ламаньей и Дж. Севиджем [35], а также Р. Тарьяном [41, 42] (для матриц Адамара).

В обзоре по вентильным схемам О. Б. Лупанова [21] (в котором отражены все перечисленные выше результаты, за исключением теорем 3 и 14) были поставлены три задачи.

1. Получить асимптотическое выражение для роста функции Шеннона (, ) в случае, когда величины log и log имеют одинаковый порядок роста.

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

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

Первая из этих задач, как уже говорилось, решена Н. Пиппенджером [36, 39] — см. теорему 3.

Вторую задачу решил в 1985 г. А. Е. Андреев [1].

Теорема Продвижения в решении третьей задачи оказались связаны с построением семейств (, )-редких матриц (у которых никакие строк не имеют общих единиц, т. е. без единичных подматриц размера ) — подробнее см., например, [5,7]. Построение (2, 2)-редких матриц с числом единиц порядка 3/2 привело [28, 35, 41] к получению нижней оценки сложности реализации этих матриц вентильными схемами, равной по порядку 3/2, построение (3, 3)-редких матриц с числом единиц порядка 5/3 — к получению [23, 37] нижней оценки сложности реализации этих матриц вентильными схемами, равной по порядку 5/3. В 1985 г. А. Е. Андреев [2] для любого построил пример ( (1), (1))редкой -матрицы с числом единиц порядка21/ и получил для этой матрицы нижние оценки порядка 21/ для сложности ее реализации вентильными схемами. Последний результат несколько усилен в работах [31, 34].

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

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

Теорема 17 [6]. Существует последовательность { } циклических булевых матриц порядка, такая что для некоторых положительных 1 и при всех достаточно больших выполняются неравенства В работе [7] этот результат несколько усилен — доказано существование циклических матриц сложности по порядку не менее log5 при реализации произвольными вентильными схемами и по порядку не менее log4 — при реализации вентильными схемами глубины 2.

Теперь остановимся на задаче о сложности реализации вентильными схемами матриц с заданной площадью информационной части.

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

Отметим, что, вообще говоря, величина информационной площади матрицы не инвариантна относительно операции транспонирования матрицы. Кроме того, очевидно, что в матрице среди элементов не менее () элементов нулевые.

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

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

Аналогично определяется и функция Шеннона 01 (, ; ).

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

Теорема Тогда На использовании теоремы 18 основано асимптотически точное решение двух известных задач. Первая из них поставлена в 1963 г. Р. Беллманом [32] (для частного случая) и в 1964 г. Е. Страусом [40] (в общем виде) и заключается в нахождении для произвольного одночлена 1 2... его сложности (1 2... ) вычисления — минимального числа умножений, достаточного для вычисления по переменным 1,..., одночлена 1 2.... Вторая поставлена в 1969 г. Д. Кнутом [8, разд. 4.6.3., упр. 32] и состоит в нахождении сложности (1, 2,..., ) вычисления набора из степеней одной переменной, определяемой аналогично.

В работе [4] на основе теоремы 18 установлены такие верхние оценки в задачах Беллмана — Страуса и Кнута (эти оценки уточнены в [12]): для любой последовательности наборов натуральных чисел 1 (), 2 (),..., () (), В статье [11] установлено, что указанные верхние оценки для почти всех наборов 1 (), 2 (),..., () () асимптотически неулучшаемы.

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

Пусть = ( ) — целочисленная матрица размера с неотрицательными элементами. Ориентированный граф без ориентированных циклов будем называть вентильной схемой с кратными путями (или вентильной схемой с предписанным числом путей), реализующей матрицу, если: в выделено вершин — входных полюсов и вершин — выходных полюсов; в нет ориентированных путей от одного входа к другому, от одного выхода к другому, от выхода к входу; для любой пары (, ), 1, 1, число ориентированных путей от -го входа к -му выходу равно в точности. Аналогично случаю классических вентильных схем, через () обозначим число ребер (вентилей) схемы и положим () = min (), где минимум берется по всем схемам, реализующим матрицу.

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

Теорема 19.

Этот результат сформулирован в [39], а его доказательство можно восстановить, объединив доказательства из [39] и [38].

Тем самым для обеих модификаций вентильных схем при слабых ограничениях на число полюсов (входов и выходов) установлена асимптотика роста функций Шеннона и предложен метод синтеза вентильных схем, дающий для почти всех матриц асимптотически минимальную верхнюю оценку. Однако при попытках получения асимптотически точных оценок сложности индивидуальных последовательностей матриц при реализации классическими схемами возникают стандартные трудности с доказательством нижних оценок, в той или иной степени близких к «мощностной», которые удается так или иначе преодолеть лишь в некоторых случаях (см., например, [2, 23, 28, 35, 41]).

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

Лемма [17]. Пусть вершинам вентильной схемы, приписаны наборы Доказательство. Будем вести доказательство индукцией по числу вершин схемы, в которые входит хотя бы один вентиль. Для схемы, не содержащей ни одного вентиля, утверждение леммы очевидно.

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

Лемма доказана.

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

Из леммы непосредственно выводится Теорема 20. Для любой ненулевой целочисленной матрицы с неотрицательными элементами справедливо неравенство Оказывается, что нижняя оценка из теоремы 20 является хорошей базой для исследования асимптотического поведения сложности индивидуальных последовательностей матриц фиксированного размера, что подтверждает следующая Теорема 21. Для произвольного натурального и произвольной последовательности матриц { } с неотрицательными элементами, каждая из которых имеет размер либо 2, где, либо 2, где, либо 3 3, при условии ( ) выполняется соотношение Доказательство верхней оценки этой теоремы в идейном плане не сильно отличается от доказательства верхних оценок сложности вычисления систем одночленов (см., например, работы [13–15]) и технически достаточно тяжелое: например, доказательство верхней оценки в случае матриц размера занимает примерно 70 страниц. Частичное разъяснение природы трудностей, возникающих при доказательстве верхней оценки теоремы 2 дает следующий факт. Казалось бы логично вытекающее из теоремы 21 предположение о том, что, возможно, при всех фиксированных значениях и для матриц размера величина () асимптотически растет как 3 log3 (), оказывается неверным уже для квадратных матриц порядка 4.

Обозначим через (, ) матрицу размера 2 2, определяемую следующим образом. Первой строкой матрицы (, ) является набор длины 2, первая половина разрядов которого равна, а вторая половина — 0. Остальные 21 строки матрицы (, ) получаются из первой строки последовательным циклическим сдвигом на один разряд вправо. Тогда элементы матрицы (, ) задаются равенствами При условии = (log ) справедливо асимптотическое раТеорема 22.

венство Доказательство этой теоремы очень похоже на доказательство теоремы из [16].

Следствием теоремы 22 является такое утверждение: при выполнении ким образом, приведен пример последовательности матриц размера 2 2, для которой устанавливаемую теоремой 20 нижнюю оценку можно усилить асимптотически в 2/( + 1) раз.

Теперь перейдем к задаче о сложности реализации недоопределенных матриц вентильными схемами с кратными путями. Пусть = ( ) — матрица, элементами которой являются целые неотрицательные числа и элементы * (символ * соответствует неопределенному элементу).

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

Матрица = ( ) называется доопределением матрицы = ( ) такого же размера, если в матрице все элементы определены (нет символов *), и для любого определенного элемента матрицы справедливо равенство Пусть — недоопределенная матрица, в которой все определенные элементы целочисленны и неотрицательны. Положим где инфимум берется по всем доопределениям матрицы до целочисленной матрицы с неотрицательными элементами.

Очевидно, что инфимум достигается.

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

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

Обозначим через = () полностью определенную (возможно пустую) матрицу, получающуюся из матрицы путем вычеркивания неполностью определенных строк. Положим 0 () = ( ) если матрица непустая, и 0 () = 1 в случае отсутствия полностью определенных строк в матрице.

Выделим три подмножества множества {1, 2,..., } номеров строк матрицы. Через 1 обозначим множество номеров таких строк, в которых первый элемент является определенным, а второй элемент — символ *, через 2 — множество номеров таких строк, в которых первый элемент является символом *, а второй элемент — определенный, и, наконец, через — множество номеров строк, оба элемента которых являются определенными.

Положим Здесь максимумы в числителях (по ) берутся по всем определенным элементам, стоящим в неполностью определенных строках (т. е. в строках, в которых второй элемент — символ *), а максимумы в знаменателях (по ) берутся по всем определенным элементам, стоящим в полностью определенных строках.

Теперь положим Теорема 23 [18]. Для произвольной последовательности недоопределенных матриц = (), = 1, 2,..., фиксированного размера 2, все определенные элементы которых неотрицательны, при условии () (сумма берется по всем определенным элементам матрицы ) выполняется соотношение Работа выполнена при финансовой поддержке РФФИ (проект 11–01–00508).

Андреев А. Е. О сложности реализации транзитивных отношений вентильными схемами // Физическое и математическое моделирование дискретных систем. — М.: МЭИ, 1985. — № 56. — С. 11–21.

Андреев А. Е. Об одном семействе булевых матриц // Вестник Московского университета. Сер. 1. Математика. Механика. — 1986. — № 2. — Андреев А. Е. О сложности реализации вентильными схемами недоопределенных матриц // Математические заметки. — 1987. — Т. 41, Гашков С. Б., Кочергин В. В. Об аддитивных цепочках векторов, вентильных схемах и сложности вычисления степеней // Методы дискретного анализа в теории графов и сложности. — Новосибирск, 1992. — Гашков С. Б., Сергеев И. С. О сложности линейных булевых операторов с редкими матрицам // Дискретный анализ и исследование операций. — 2010. — Т. 17, № 3. — С.3–18.

Гринчук М. И. О сложности реализации циклических булевых матриц вентильными схемами // Известия ВУЗов. Математика. — 1988. — Гринчук М. И., Сергеев И. С. Редкие циркулянтные матрицы и нижние оценки сложности некоторых булевых операторов // Дискретный анализ и исследование операций. — 2011. — Т. 18, № 5. — С.38–53.

Кнут Д. Е. Искусство программирования для ЭВМ, т. 2. 1-е издание. — Кочергин В. В. О сложности вычислений в конечных абелевых группах // ДАН СССР. — 1991. — Т. 317, № 2. — С. 291–294.

Кочергин В. В. О сложности вычислений в конечных абелевых группах // Математические вопросы кибернетики, вып. 4. — М.: Наука, 1992. — С. 178–217.

Кочергин В. В. О сложности вычислений одночленов и наборов степеней // Дискретный анализ. — Новосибирск: Издательство Института математики СО РАН, 1994. — (Тр./РАН. Сиб. отделение. Ин-т математики; Т. 27) — С. 94–107.

Кочергин В. В. О двух обобщениях задачи об аддитивных цепочках // 12.

Труды IV Международной конференции «Дискретные модели в теории управляющих систем» (19–25 июня 2000 г.). — Москва, «МАКС Пресс», Кочергин В. В. О сложности вычисления пары одночленов от двух 13.

переменных // Дискретная математика. — Т. 17, вып. 4. — 2005. — Кочергин В. В. О сложности вычисления систем одночленов от двух 14.

переменных // Труды VII Международной конференции «Дискретные модели в теории управляющих систем» (Покровское, 4–6 марта 2006 г.). — М.: МАКС Пресс, 2006. — С. 185–190.

Кочергин В. В. О сложности вычисления системы из трех одночленов от трех переменных // Математические вопросы кибернетики, вып. 15. — М.: Физматлит, 2006. — С. 79–155.

Кочергин В. В. Об одном соотношении двух мер сложности вычисления систем одночленов // Вестник Московского университета. Сер. 1.

Математика. Механика. — 2009, № 4. — С. 8–13.

Кочергин В. В. О сложности вентильных схем с кратным числом путей // Материалы XVIII Международной школы-семинара «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова (Пенза, 28 сентября – 03 октября 2009 г.). — М.: Изд-во механикоматематического факультета МГУ, 2009. — С. 51–56.

Кочергин В. В. О реализации недоопределенных матриц из двух столбцов вентильными схемами с кратными путями // Вестник Нижегородского университета им. Н. И. Лобачевского. — 2012. — Вып. 5, часть 2. — Лупанов О. Б. О вентильных и контактно-вентильных схемах // Доклады АН СССР. — 1956. — Т. 111, № 6. — С. 1171–1174.

Лупанов О. Б. О синтезе некоторых классов управляющих систем // 20.

Проблемы кибернетики, вып. 10. — М.: Физматгиз, 1963. — C. 63–97.

Лупанов О. Б. О вентильных схемах // Acta Cybernetica. — 1980. — 21.

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

Мельхорн К. Некоторые замечания, касающиеся булевых сумм // Кибернетический сборник. Вып. 18. — М.: Мир, 1981. — С. 39–45.

Нечипорук Э. И. О синтезе вентильных схем // Проблемы кибернетики, вып. 9. — М.: Физматгиз, 1963. — C. 37–44.

Нечипорук Э. И. О вентильных схемах // Доклады АН СССР. — 25.

Нечипорук Э. И. О сложности вентильных схем, реализующих булевские матрицы с неопределенными элементами // Доклады АН СССР. — 1965. — Т. 163, № 1. — С. 40–42.

Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики, вып. 21. — М.: Наука, 1969. — C. 5–102.

Нечипорук Э. И. Об одной булевской матрице // Проблемы кибернетики, вып. 21. — М.: Наука, 1969. — C. 237–240.

Орлов В. А. Реализация «узких» матриц вентильными схемами // Проблемы кибернетики, вып. 22. — М.: Наука, 1970. — C. 45–52.

Чашкин А. В. О сложности булевых матриц, графов и соответствующих им булевых функций // Дискретная математика. — 1994. — Т. 6, Alon N., Rnyai L., Szab T. Norm-graphs: variations and applications // 31.

J. Combinat. Theory. Ser. B. — 1999. — V. 76, № 3. — P. 280–290.

Bellman R. E. Addition chains of vectors (Advanced problem 5125) // 32.

Amer. Math. Monthly. — 1963. — V. 70. — P. 765.

Jukna S., Sergeev S. Complexity of linear Boollean operators // 33.

Foundations and Trends in Theoretical Computer Science. — В печати.

Kllar J., Rnyai L., Szab T. Norm-graphs and bipartite Turn 34.

numbers // Combinatorica. — 1996. — V. 16, № 3. — P. 399–406.

Lamagna E. A., Savage J. E. Computational complexity of some monotone 35.

functions // Proc. 15th SWAT Conference. — Long Beach: IEEE Comput.

Soc. Press, 1974. — P. 140–144.

Pippenger N. On evaluation of powers and related problems // Proc. 36.

Ann. IEEE Symp. on Found. of Computer Sci. (Houston, TX, 25–27 Oct.

1976.) — P. 258–263.

Pippenger N. On another Boolean matrix // Theoretical Computer 37.

Science. — 1980. — V. 11, I. 1. — P. 49–56.

Pippenger N. On evaluation of powers and monomials // SIAM J.

38.

Comput. — 1980. — V. 9, N 2. — P. 230–250.

Pippenger N. The mimimum number of edges in graphs with prescribed 39.

paths // Math. Systems Theory. — 1979. — V. 12, № 4. — P. 325–346.

Straus E. G. Addition chains of vectors // Amer. Math. Monthly. — 1964. — 40.

Tarjan T. G. Complexity of lattice-configurations // Studia Sci. Math.

41.

Hungar. — 1975. — V. 10. — P. 203–211.

Tarjan T. G. Complexity of monotone networks for computing 42.

conjunctionns // Ann. Discrete Math. — 1978. — № 2. — P. 121–133.

ПОЛУЧЕНИЕ НИЖНИХ ОЦЕНОК СЛОЖНОСТИ

СХЕМ МЕТОДОМ ЗАМЕНЫ БАЗИСОВ

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

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

Известные к настоящему времени способы получения нижних оценок сложности схем для конкретных булевых функций зачастую предполагают достаточно простые базисы, как правило, содержащие лишь одно- и двухвходовые элементы. Возьмем, скажем, метод «забивания» переменных на входах схем булевыми константами. Этот метод позволил, например, установить сложность реализации линейных булевых функций схемами в базисах { &,, }, { &, }, {, } [2]. Основан он на использовании следующих простых свойств схем в базисе { &,, } (а также и в базисах Свойство 1. Пусть в схеме имеются +2 входов, на которые подаются переменные 1, 2,..., и булевы константы 0 и 1. Если на вход какого-либо элемента схемы подается булева константа (т. е. тождественный нуль или тождественная единица), то этот элемент можно удалить из схемы так, что реализуемая этой схемой функция не изменится.

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

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

Представим теперь, что рассматриваются схемы в базисе {1 &... &, 1 · · ·, }, где 3. Очевидно, что схемы в этом базисе по-прежнему обладают вторым свойством, но вот первое свойство в каких-то случаях может и не выполняться (например, если на один вход трехвходового конъюнктора подается константа 1, а на два других входа подаются и ). В результате получение нужной нижней оценки сложности схем «стандартным» методом забивания переменных будет затруднено или даже вообще окажется невозможным. Но оказывается, что полученные нижние оценки схем в простых базисах (скажем, из двухвходовых элементов) можно эффективно использовать для получения аналогичных оценок для схем в более сложных базисах.

Суть рассматриваемого подхода к получению новых оценок сложности заключается в замене одного («сложного») базиса другим (более «простым») базисом.

Пусть — произвольный базис с положительными весами элементов, а — схема в базисе. Как обычно, сумму весов всех элементов будем считать сложностью схемы, а обозначать эту величину будем через ().

Для произвольной реализуемой в базисе булевой функции положим ( ) = min (), где минимум берется по всем схемам в базисе, реализующим. Число ( ) задает (по определению) сложность реализации функции схемами в базисе ; схему в базисе, реализующую булеву функцию, будем считать минимальной, если () = ( ).

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

Теорема 1. Пусть булева функция реализуема схемой в базисе и схемой в базисе *, а функции из * реализуемы схемами в базисе и выполН. П. Редькин няются неравенства Тогда выполняется и неравенство Доказательство. Пусть задана произвольная булева функция, реализуемая схемами в базисах и *. Построим для нее минимальную схему * в базисе *, для которой выполняется условие Воспользуемся условием теоремы и все функции *,..., * реализуем минимальными схемами (блоками) 1,...,, построенными в базисе ; из (1) для сложностей блоков 1,..., следуют оценки Все элементы в схеме * заменим отвечающими им блоками (элемент за- * меняется при этом блоком, 1 ). В результате такой замены вместо схемы * в базисе * получим некоторую схему в базисе, реализующую прежнюю функцию. Из (3) и (4) получаем * ( ) (), а это означает, что неравенство (2) выполняется. Теорема доказана.

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

2. Оценка сложности для монотонных симметрических Рассмотрим базис, содержащий элементы 1, 2, 3, реализующие соответственно функции 1 = 1 &... &, 2 = 1 · · ·, * =, где — некоторое заданное натуральное число не меньше трех, а вес каждого элемента равен единице (т. е. сложность схем будет определяться числом элементов в них).

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

Нижнюю оценку получим с использованием теоремы 5. Для этого возьмем базис 1 = { &, } и у этого базиса положим веса надежных элементов равными 1, а веса ненадежных элементов равными 1. Базис 1 отличается от базиса из предыдущего примера лишь отсутствием в нем инверсии;

условия согласованности базиса 1 с базисом 1 выполняются. Кроме того, рассматриваемый здесь базис 1 отличается от одноименного базиса из [11] лишь уменьшенными в 1 раз весами всех элементов; из этого факта и теоремы 2 из [11] получаем неравенство (это неравенство можно вывести и непосредственно, фактически повторяя рассуждения при доказательстве нижней оценки теоремы 2 из [11]). Остается воспользоваться теоремой 5, позволяющей и для рассматриваемого базиса 1 с использованием (14) моментально получить требуемую нижнюю оценку. Теорема доказана.

Замечание. Основная теорема 5 и особенно представленные примеры ее использования в чем-то достаточно конкретизированы. Вместе с тем (и об этом уже говорилось ранее) возможны изменения как в исходном утверждении, т. е. в основной теореме, так и в постановках конкретных задач, решаемых с использованием этой теоремы. Например, надежная и ненадежная части одного и того же базиса могут не совпадать (в этом случае множество функций, реализуемых надежными элементами, не совпадает с множеством функций, реализуемых ненадежными элементами); в отличие от приведенных примеров в каких-то случаях веса у разных элементов одного и того же базиса (как у надежных, так и ненадежных) могут различаться; в схемах могут возникать другие неисправности, скажем, константные неисправности произвольного типа [9] на выходах элементов, неисправности на входах элементов, инверсные неисправности. Нетрудно заметить, что и в этих случаях можно воспользоваться основной теоремой 5 или подходящей ее модификацией.

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

Редькин Н. П. Доказательство минимальности некоторых схем из функциональных элементов // Проблемы кибернетики. — 1970. — Вып. 23. — С. 83–101.

Гринчук М. И. О монотонной сложности пороговых функций // Методы дискретного анализа в теории графов и сложности. — Вып. 52. — Новосибирск, 1992. —С. 41–48.

Фиников Б. И. Об одном семействе классов функций алгебры логики и их реализации в класса -схем // Доклады АН СССР. — 1957. — Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики. — 1965. — Вып. 14. — C. 31–110.

Редькин Н. П. О сложности булевых функций с малым числом единиц // Дискретная математика. — 2004. — Т. 16, № 4. — C. 20–31.

Редькин Н. П. Дискретная математика. — М.: Физматлит, 2009.

Яблонский С. В. Элементы математической кибернетики. — М.: Высшая школа, 2007.

Редькин Н. П. Надежность и диагностика схем. — М.: Изд-во МГУ, Редькин Н. П. О минимальной реализации линейной функции схемой 10.

из функциональных элементов // Кибернетика. — 1971. — № 6. — Редькин Н. П. Асимптотически минимальные самокорректирующиеся 11.

схемы для одной последовательности булевых функций // Дискретный анализ и исследования операций. — 1996. — Т. 3, № 2. — C. 62–79.

СОДЕРЖАНИЕ

Н. Ю. Золотых Свойства целочисленных паскаль-функций, доказуН. К. Косовский В. В. Кочергин Теория вентильных схем (современное состояние)... Н. П. Редькин Получение нижних оценок сложности схем методом замены базисов.................................

Похожие работы:

«Лекция № 8-9. Накопители на жестких дисках Лекция № 8-9. Накопители на жестких дисках Содержание: Что такое жесткий диск Новейшие достижения Принципы работы накопителей на жестких дисках Несколько слов о наглядных сравнениях Форматирование дисков Форматирование низкого уровня Организация разделов на диске Форматирование высокого уровня Основные компоненты накопителей на жестких дисках Рабочий слой диска Оксидный слой Тонкопленочный слой Двойной антиферромагнитный слой Головки чтения/записи...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ УЧ ЕБНО- М ЕТОДИЧЕС КИЙ КОМ ПЛЕ КС по дисциплине Б2.В.ДВ1 – БИОЛОГИЧЕСКАЯ БЕЗОПАСНОСТЬ В ЛАБОРАТОРИИ Код и направление 111900.62 – Ветеринарно-санитарная подготовки экспертиза Профиль бакалавриат подготовки Квалификация Ветеринарно-санитарная экспертиза (степень) выпускника Факультет...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГАОУ ВПОКАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИНСТИТУТ УПРАВЛЕНИЯ И ТЕРРИТОРИАЛЬНОГО РАЗВИТИЯ Е.М.Пудовик А.Р.Нуриева Демография КОНСПЕКТ ЛЕКЦИЙ КАЗАНЬ 2014 Пудовик Е.М., Нуриева А.Р. Демография: Конспект лекций/ Е.М.Пудовик, А.Р.Нуриева. – Казань: К(П)ФУ, 2014. – 59 с Аннотация В курсе рассматриваются основы теории народонаселения, теория формирования и развития демографии как самостоятельной общественной науки, методы анализа...»

«оит в казахстане Пункты westernunion в ювао Пусковое устройство 3-х фазных эл Двигателей при однофазном подключении Путевки членам профсоюза в 2010 году Рейд-1 г Самара Рaботa в оренбурге резчик стеклa Рaботa в сaнкт-петербурге тц континент Рабочая тетрадь для 2-х 3-х классов биболетова Рaботa в белоруссии в деревнях Путевки в лагерь евпаторию Пункты оплaты интернет билaйн в белгороде Птицы остaющиеся зимой в городе Реле регулятор рр-24 г Пункт вторсырья в сaлaвaте Путевки из новокузнецка в...»

«В. Н. Шивринский НАВИГАЦИОННЫЕ СИСТЕМЫ ЛЕТАТЕЛЬНЫХ АППАРАТОВ Ульяновск 2012 УДК 629.7.05 (076) ББК 32я7 Ш 55 Рецензент доцент кафедры Электроснабжение энергетического факультета Ульяновского государственного технического университета кандидат технических наук А. Е. Усачев Одобрено секцией методических пособий научно-методического совета университета Шивринский, В. Н. Ш 55 Навигационные системы летательных аппаратов : конспект лекций / В. Н. Шивринский. – Ульяновск : УлГТУ, 2012. – 148 с. Данное...»

«Пересказ и его рецептивные возможности в Лекциях по литературе Владимира Набокова Андрей Павлов КЕМЕРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Лекции В. Набокова по русской и зарубежной литературе неоднократно становились предметом научного анализа1. Однако среди множества исследований по эстетике писателя очень мало работ, посвященных слову самого Набокова. При этом рассматривается, как правило, одна лекция, а не весь цикл, а в исследовательском обороте в целом находятся практически одни и те же...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ФИЗИЧЕСКОЙ КУЛЬТУРЕ, СПОРТУ И ТУРИЗМУ Филиал российского государственного университета физической культуры, спорта и туризма в г. Иркутске КАФЕДРА ЦИКЛИЧЕСКИХ ВИДОВ СПОРТА И ТУРИЗМА О.Ю. Палкин КУРС ЛЕКЦИЙ по дисциплине Рекреалогия УТВЕРЖДЕНО: На заседании кафедры ЦВСиТ Протокол № _4_ от 25.11. 2010 г Зав. каф. О.В. Дулова ИРКУТСК - 2010 РЕКРЕАЛОГИЯ - КАК НАУЧНОЕ НАПРАВЛЕНИЕ Процесс формирования нового научного направления в центре внимания которого стояла деятельность...»

«Министерство образования и науки Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Челябинский государственный университет ПСИХОЛОГИЯ ТРУДА Конспект лекций Для студентов направления подготовки 030300.62 – Психология Троицк 2013 1 Оглавление Возникновение и развитие психологии труда Общее представление о психологии труда Методы психологии труда Неэкспериментальные методы Труд как фактор исторического развития человека Стадии цикла...»

«КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ ЭКСКУРСОВЕДЕНИЕ Доцент кафедры Циклических видов спорта и туризма Журавлева М.М. I. ИСТОРИЧЕСКИЙ ЭКСКУРС ПО ОСНОВНЫМ ДОСТОПРИМЕЧАТЕЛЬНОСТЯМ История города. Улицы г. Иркутска. Старые и новые названия. Город Иркутск был основан на месте слияния рек Иркута и Ангары в 1661 г. Сначала это был деревянный острог, довольно быстро разраставшийся, уже через 25 лет ему был придан статус города. Основание острога связано с территорией, прилегающей к центральной площади города...»

«05.12.2011 любимцы - начальный курс научных открытий 06:00 Line-up 10:00 Отдел защиты животных 12:15 Из истории великих 10:00 Новости Rap Info 2009 - спецвыпуск научных открытий 2x2 10:05 Line-up 10:55 Ветеринар Бондай Бич 12:30 Лекции Марка Стила 11:00 A-One Hip-Hop Top 10 11:20 SOS дикой природы 13:00 Зачем и почему 06:00 Химэн 11:45 Line-up 11:50 Последний шанс 13:30 Искатели во времени 06:30 Вольтрон 13:00 Все свои 12:45 Полиция Феникса: Отдел 14:00 Исследовательский 06:55 Оазис 13:45...»

«Б.В. Бровар, З.В. Рубцова, Т.А. Тутова, А.Б. Щербакова О жизни и деятельности М.И. Юркиной и В.Ф. Еремеева Премия имени Ф.Н. Красовского присуждена за Цикл работ по развитию теоретических обоснований решений фундаментальных задач геодезии, выполненный доктором технических наук М.И. Юркиной в период с 1955 года по 2003 год совместно с кандидатом технических наук В.Ф. Еремеевым, работавшим в ЦНИИГАиК с 1937 г. по 1972 г. В цикле содержится теоретическое обоснование возможности достижения высокой...»

«Библиотека Выпуск 24 А. И. Дьяченко МАГНИТНЫЕ ПОЛЮСА ЗЕМЛИ Издательство Московского центра непрерывного математического образования Москва • 2003 УДК 550.38 ББК 26.21 Д93 Аннотация Географические полюса нашей планеты располагаются в Арктике и Антарктиде. А куда мы в конце концов придём, если будем идти по компасу точно на север? На северный географический полюс? Нет, магнитный северный полюс не совпадает с географическим. И в разные годы стрелка компаса может привести нас в разные места:...»

«МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ КУЛЬТУРЫ ЦЕНТРАЛИЗОВАННАЯ СИСТЕМА ОБЩЕДОСТУПНЫХ БИБЛИОТЕК г. БРЯНСКА ЦЕНТРАЛЬНАЯ ГОРОДСКАЯ БИБЛИОТЕКА им. П.Л. ПРОСКУРИНА Мы не приёмыши, края но законные дети этого края.От отца к сыну, внуку и правнуку. ЛЕКЦИЯ В ПОМОЩЬ ИЗУЧЕНИЮ ИСТОРИИ РОДНОГО КРАЯ (БЕЖИЦЫ) НОВАЯ РЕДАКЦИЯ БРЯНСК—2012 г. 1 Мы не приёмыши, но законные дети этого края.От отца к сыну, внуку и правнуку : лекция в помощь изучению истории родного края (Бежицы) / сост. Г.Г.Моцар. – Брянск,...»

«Тема 1. КРАТКАЯ ИСТОРИЯ РАЗВИТИЯ ЭКОЛОГИЧЕСКОЙ НАУКИ Лекция 1.1. Зарождение экологических взглядов в науке Лекция 1.2. Обобщение материалов экологии в трудах ученых Лекция 1.3. Обособление науки экологии в отдельную область знаний Лекция 1.4. Современное состояние науки экологии Лекция 1.1. Зарождение экологических взглядов в науке Экология как наука о взаимоотношениях организма и среды могла возникнуть лишь на определенном этапе развития биологических знаний. Ее становление, как никакой...»

«Н. В. Беляева О. И. Григорьева Т.А. Ищук ЛЕСНОЕ ХОЗЯЙСТВО Лабораторный практикум Санкт-Петербург 2012 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Санкт-Петербургский государственный лесотехнический университет имени С.М. Кирова (СПбГЛТУ) Кафедра лесоводства Н. В. Беляева, кандидат сельскохозяйственных наук, доцент О. И. Григорьева, кандидат сельскохозяйственных наук, доцент Т.А. Ищук, аспирант кафедры...»

«Кафедра физики полупроводников А.В. Бурмистров Аудит качества КРАТКИЙ КОНСПЕКТ МАТЕРИАЛОВ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ АУДИТ КАЧЕСТВА Саратов 2012 Задача аудита – сбор данных, необходимых для стратегического и оперативного управления! Финансовый Экологический Технологический аудит аудит аудит Аудит качества • установить, что система менеджмента качества • соответствует запланированным целям; • соответствует требованиям; Цель: • эффективно внедрена и поддерживается в рабочем состоянии; • оценить сильные...»

«А.Б.Данилин, Е.Н.Евсеева, С.В.Карпенко ГРАЖДАНСКАЯ ВОЙНА В РОССИИ (1917 – 1922) В отличие от традиционого изложения в учебниках и учебных пособиях истории Гражданской войны, когда отдельно рассматриваются причины и начало войны, политика военного коммунизма, международные отношения, военные действия и т.д., в предлагаемой лекции все события и процессы излагаются во взаимосвязях друг с другом внутри хрононологических периодов. Это позволяет лучше понять закономерности хода войны и факторы,...»

«ПРИКЛАДНІ ПИТАННЯ ПЕДАГОГІКИ 40 УДК 378.147:94/477/ Т.К. Кухникова, канд. ист. наук, доцент Севастопольский национальный технический университет ул.Университетская 33, г. Севастополь, Украина, 99053 E-mail: root@sevgtu.sebastopol.ua ИСТОРИЧЕСКОЕ КРАЕВЕДЕНИЕ НА ЛЕКЦИЯХ И СЕМИНАРАХ ПО ИСТОРИИ УКРАИНЫ: МЕТОДИЧЕСКИЙ АСПЕКТ Анализируются конкретные методики изучения истории Крыма и Севастополя на занятиях по истории Украины в Севастопольском национальном техническом университете. Ключевые слова:...»

«РАСПИСАНИЕ НА ОСЕННИЙ СЕМЕСТР 2012/2013 УЧЕБНЫЙ ГОД ГРУППА БЖД-12-1 ДНИ НЕДЕЛИ № Часы занятий ПН ВТ СР ЧТ ПТ СБ Русский язык Математика практика 1 - 504 практика 1 - 312 преп. Азимбаева Ж.А. доц. Шаихова Г.С. Экология и УР практика 2- 406 9:00-9: асс. Ауельбекова А.Ж. 1 9:55-10: Иностранный язык Физика Иностранный язык Физкультура Физика практика 1- 605 лекция1-209 практика 1 - 523 лаб. раб.1 - преп. Несипбаева Н.Е. ст. преп. Хуанбай Е.К. преп. Несипбаева Н.Е. асс. Салькеева Ж.К. 10:55-11:...»

«Структура дисциплины Практический курс перевода (второй иностранный язык) Семестр Кол-во Кол-во Объем учебного курса и виды учебных мероприятий Форма Наименование изучения ЗЕТ недель, в курса контроля Всего Аудиторные занятия Самостоятельная работа течение часов которых (Курс. работы) по уч. Курс. проекты Лабораторные Лабораторные Консультации реализуется Практические Контрольные курс плану Лекции работы Всего Всего Иное РГР ЦТ Практический зачет 5 855 68 курс перевода (второй ино- экзамен 6...»









 
2014 www.konferenciya.seluk.ru - «Бесплатная электронная библиотека - Конференции, лекции»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.