Введение к работе
Актуальное ть^геш:; Одной из-основных'задач дискретной математики
и математической .кибернетики является задача изучения сложности порождения различных комбінаторних объектов: булевых функций, чисел, последовательностей целых чисол и т.д., исходя ' из некоторого начального запаса элементарных объектов в соответствии с определенными правилами. Под сложностью порождения,, как правило, понимается число шагов, за которое исследуемый объект может быть порожден. Е диссертации исследуется именно такая задача: задача о сложности порождения булевых матриц схемами из функциональных элементов. Матрицы при этом порождаются схемами, исходя из множества начальных объектов,' называемых з дальнейшем генераторами. В качестве генераторов использованы либо булевы векторы, либо булевы матрицы. 'Схемы, порождающие матрицы, исходя из генераторов-векторов, состоят из функциональных элементов, выполняющих- покомпонентные булевы операции над булевыми векторами, а схемы, пореждаксие матрицы, исходя из-.генераторов-матриц,, состоят из- функциональных элементов, еыполняших покомпонентные булевы операции над булевыми аатрицами. В первом случае будем говорить о У-порокдении матриц, а во втором - о м-порождении матриц схемами из функциональных элементов..
Исследование сложности матриц представляет интерес по ряду причин. Одна из них заключается в том, что матрицы интенсивно используются в различных разделах как .чистой, так и прикладной математики. Кроме этого, практически всё результаты о сложности М~порождения матриц могут быть интерпретированы как
результаты о сложности порождения графов, так как любая матрица
является матрицей смежности некоторого графа (двудольного графа). А
графи"'-' объекты "не- 'менее- распространенные ?. математике чем
матрицы. Наконец матрицы можно рассматривать как частичные булевы
функции-(при И-порождении) и системы частичных булевых функций' (при
v-порождении). ' \ *
Цель работы. I)Исследование сложности у- и и-поровдения матриц, исходя из некоторых специальных множеств генераторов, и сравнение этих сложностей со сложностью вычисления ' соответствующих булевых функций схемами в полных .базисах. Соответствие между булевыми функциями и булевыми матрицами устанавливается естественным образом, так как любая булева функция может быть задана двумерной таблицей своих значений, т.е. матрицей,, а любая булева матрица может рассматриваться как двумерная таблица значений некоторой булевой функции/ 2) Изучение поведения функций Шеннона порождения булевых матриц.
^етоды^и«^дрвэний. В работе используются методы дискретной математики и математической кибернетики.'
Научная новизна. Все основные результаты диссертации являются новыми. В диссертации найдены асимптотически точные формулы для функций Шеннона ы-порождения булевых матриц размера шш схемами в базисе, состояаем из не' более -чем г-местных операций дизъюнкции и конъюнкции, при достаточно слабых ограничениях,. накладываемых на величины n,m н г (аналогичные результаты для v-порокдения могут быть легко' получены при помощи конструкций, использованных в случае' м-порокдения). В случае г=2 и nsloggm найдены точные значения этой
функции. Для у-порозвдения матриц схемами в нескольких различных 5аэисах при nsiog^m также найдены точные значения фуисции Шеннона.
В- диссорташв: получен ряд- результатов, связывающих сложность-торождения булевых матриц со сложностью вычисления соответствующих этим матрицам булевых функций. Приведено несколько последовательностей булевых матриц, для сложности порождения которых найдеш точные формулы. Показано, что доказательство нижних оценок сложности порождения матриц,-асимптотически больших чем полученные.в диссертации, равносильно .доказательству .экспоненциальных нижних оценок сложности булевых функций схемами в полных базисах.
Пеактотеская^_теотетическая_ценность. Диссертация носит
теоретический характер. Результаты, полученные в диссертации,- могут
найти применение в теории сложности алгоритмов и вычислений, а также
при создании программного и аппаратного обеспечения вычислительной
техники. ' "'
Апробация работа. Основные результаты диссертации докладывались на научных семинарах в МГУ им. М.В. Ломоносова.
Публикации. Основные результаты диссертации опубликованы.
Структура и объем работы. Диссертация состоит из введения, двух глав и списка литературы, включающего 17 названий. Объем работы 67 страниц.