Введение к работе
Актуальность темы. В связи с широким развитием цифровой техники проблема изучения дискретных функций становится все более актуальной. В нашей стране активное изучение дискретных функций было начато во второй половине 50-х годов прошлого века в работах С. В. Яблонского, О. Б. Лупанова, Ю. И. Журавлева и других авторов. За прошедшие годы широко развились такие разделы теории дискретных функций как функциональные системы, проблемы подсчета числа функций, сложность реализации функций, распознавание свойств функций, изучение специальных классов функций. В диссертации изучаются три типа задач теории дискретных функций: проблема подсчета количества функций, проблема тестирования бесповторных функций и проблема распознавания свойств функций по вектор-столбцу. Основное внимание уделяется построению методов, позволяющих решить большое количество задач.
Задачи подсчета числа дискретных функций интенсивно изучались в течение длительного времени. Наиболее известной такой задачей является проблема Дедекинда [19] о количестве монотонных булевых функций. Эта задача активно исследуется последние сорок лет. Важнейший вклад в ее решение внесли В. К. Коробков [9], Ж. Ансель [20], Д. Клейт-мен [21], А. Д. Коршунов [10] и А. А. Сапоженко [12]. С. В. Яблонский [18] исследовал задачу о количестве функций в инвариантных классах. В. Б. Алексеев [2,3] решил задачу нахождения асимптотики логарифма для числа fc-значных монотонных функций и числа функций в предполных классах в Р&. Отметим задачу об оценке числа пороговых функций (асимптотика логарифма была установлена Ю. А. Зуевым [5]). Задача оценки количества дискретных функций решалась и для большого количества других классов. В диссертации изучаются задачи нахождения асимптотики логарифма количества дискретных функций для широкого класса семейств, задаваемых простыми естественными условиями.
Задача тестирования функций и схем впервые подробно описана в работе СВ. Яблонского и И. А. Чегис [16]. Различные задачи тестирования ставились для класса монотонных функций. Проблема расшифровки была решена Ж. Анселем [20]. И. И. Катериноч-кина [7,8], И. А. Соколов [14,15] и А. А. Сапоженко [13] решали различные постановки задачи поиска верхнего нула монотонной функции. Большой интерес представляют функ-
ции, которые можно реализовать формулами без повторения переменных (бесповторные функции). Одним из первых утверждений теории бесповторных функций была теорема А. В. Кузнецова [11] о конечной полной системе тождеств для бесповторных формул. Задача тестирования бесповторных функций отличается тем, что в ней вырождается целый ряд постановок. В работе рассматривается задача построения проверяющего теста для бесповторной в заданном базисе функции на множестве всех бесповторных в этом базисе функций, не имеющих других существенных переменных, кроме существенных переменных тестируемой функции. Естественным образом ставится задача об оценке функции Шеннона и минимальной длины теста для отдельных функций и последовательностей функций.
Важной задачей для различных приложений (в частности, криптографических) является задача распознавания свойств дискретных функций при различных их заданиях. Задача распознавания свойств функций, заданных вектор-столбцом, рассматривалась ранее в работах В. Б. Алексеева [1,4]. Им разработан метод логических полуколец, основанный на использовании алгебраических характеристик распознаваемых свойств. Рассматриваемая задача является частным случаем другой проблемы: существует ли для задачи алгоритм проще (лучше) "естественного". Первый результат в этом направлении был получен А. А. Карацубой [6] для умножения чисел. Целое направление связано с результатом В. Штрассена [22] об умножении матриц. В работе делается строится рекурсивный алгоритм, строящий код функции в предположении, что она обладает исследуемым свойством, для распознавания наличия этого свойства у функции. Данный метод позволяет понизить сложность алгоритмов во многих задачах. Среди рассматриваемых задач выделим задачу распознавания монотонности, в которой получен результат лучше, чем достижимый методом логических полуколец, а также задачу распознавания бесповторно-сти функции в произвольном базисе, связанную с гипотезой О. Б. Лупанова (доказанной недавно Д. Ю. Черухиным [17]) о том, что взаимная бесповторная выразимость является критерием сложностной формульной эквивалентности.
Цели исследований. Изучение свойств дискретных функций из ряда важных классов. Построение представлений функций для решения задач подсчета, тестирования и
распознавания свойств.
Научная новизна. Все основные результаты работы являются новыми. Укажем наиболее важные из них.
В диссертации установлена асимптотика логарифма количества отображений вершин булева куба в вершины произвольного графа, переводящих смежные вершины в смежные или совпадающие. Для отображений декартовых степеней частичных порядков в себя, удовлетворяющих части аксиом замыкания, также найдена асимптотика логарифма количества. Для получения оценок количества дискретных функций предложен метод жирных точек, при помощи которого получена асимптотика логарифма количества дискретных функций в нескольких семействах классов функций, сохраняющих двуместные предикаты.
Исследована проблема тестирования бесповторных функций. Поставлена задача построения теста относительно бесповторной альтернативы. Для ее решения разработан метод квадратов существенности (для случая базиса всех функций двух переменных), который был обобщен на случай базисов, содержащих функции большего количества переменных. Получен порядок роста функций Шеннона длины теста в ряде базисов. Для элементарного базиса установлен линейный рост функции Шеннона. В базисе функций двух переменных построены последовательности функций с длиной проверяющего теста от линейной до квадратичной.
Разработан метод разложения для схемного распознавания принадлежности дискретных функций, задаваемых столбцом значений, наследственным классам. При помощи этого метода получены верхние оценки 0(N^/log iVloglogiV) для сложности распознавания монотонности, частичной монотонности и поляризуемости булевых функций (N — длина вектор-столбца). Доказана линейность сложности задач распознавания свойств доопре-делимости до линейной функции и бесповторности в произвольном конечном базисе. Исследована задача построения схем, распознающих наличие у булевой функции растущего количества фиктивных переменных.
Методика исследований. В работе используются методы теории булевых и fc-значных функций и комбинаторики.
Практическая и теоретическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в различных разделах теории дискретных функций, в том числе при решении задач оценки количества дискретных функций, при исследовании бесповторных функций в различных базисах и при оценке сложности распознавания свойств дискретных функций, задаваемых вектор-столбцом. Вместе с тем полученные результаты по тестированию бесповторных функций могут быть использованы при тестировании реальных схем, изготовленных по технологии FPGA.
Апробация. Результаты работы докладывались на VII Международной конференции "Дискретные модели в теории управляющих систем"(2006, Москва), на российской школе-семирнаре "Синтаксис и семантика логических систем"(2006, Иркутск) — пленарные доклады, на шестой молодежной научной школе по дискретной математике и ее приложениям (лекция, 2007, Москва), на 15 конференции IEEE Computational Complexity (2000, Флоренция), на Ломоносовских чтениях в МГУ, на II, IV, VI Международных конференциях "Дискретные модели в теории управляющих систем"(1997, 2000, 2004, Москва), на XI, XII, XIV Международных конференциях "Проблемы теоретической кибернетики"(1996, Ульяновск, 1999, Нижний Новгород, 2005, Пенза), на VI, VII Международном семинаре "Дискретная математика и ее приложения (1998, 2001, Москва), на конференции "Интеллектуализация обработки информации"(2000, Симферополь), на четвертой молодежной научной школе по дискретной математике и ее приложениям (2000, Москва), на Международной школе-семинаре "Дискретная математика и математическая кибернетика" (2001, Москва), на XIII Международной школе-семинаре "Синтез и сложность управляющих си-стем"(2002, Пенза), на семинаре С.В.Яблонского (с осени 1998 г. О.Б.Лупанова) "Математические вопросы кибернетики "и на научных и учебных семинарах факультета ВМиК МГУ.
Публикации. Основные результаты диссертации изложены в рецензируемых работах, список которых приведен в конце автореферата. Там же приводится список остальных работ по теме диссертации.
Структура диссертации. Диссертация состоит из введения, трех глав, состоящих в совокупности из 15 параграфов, и списка литературы. Полный объем диссертации — 154
страницы.
Похожие диссертации на Методы представления дискретных функций в задачах подсчёта, тестирования и распознавания свойств
