Введение к работе
Актуальность темы
Последовательности, построенные из букв конечного ллфапи-а, являются ваяіик объектом в математике it ее приложениях. 7an, напри vep, задача исследования закономерностей блузкдаїшя гастицїл на прямой сводятся и изучению последовательностей, 5разс:;аші:>і>с явуі.їя буквами.: —1 и 1. 3 задачах социальной пси-"олигнл, социологии, биологии, медицины иногда удобно предств-лять "ретніщу" в поведении двух объектов в виде последователь-сстк из нулей и единиц.
Іізвестио, что бедыггал часть вычислительных устройств от-оентся к. цифровому типу; в таких машинах используется пред-гавленне информации в виде последовательностей символов коечного алфавита, чаще всего, двоичных последовательностей.
В силу этой; и ряда других причин особое Еіінмаїпге уделяет-я изучению конечных двоичных последовательностей. Так в терші кодирования основной объект изучение — двоичные коды, овольно часто математические модели тех или иных реальных родессов, использующие двоичные последовательности:, огранк-::г"&ются случаем "независимого" появления нуля или единицы, а гковігой характеристикой поведения объекта является доля едите (или нулей) в наборе некоторой фиксированной длины. Од-ixo в целок ряде задач возникают множества двоичных после-ж&телыюстей более сложной структуры, несущих в себе опре-іленную зависимость iiezmy разрдцами. Так, например, при со-[ании моделей физики микромира следует учитывать, что име-
2 ется взаимодействие мезкду частинами, сильное при их бдизкс расположении и резко ослабеваюшее с ростом расстояния меха ними; в социологических обследованиях при анкетном спросе ч сто характер ответов зависит от порядка следования задаваомь вопросов.
Цель работы
Целью дашюй работы является решение ряда задач, связа ных со свойствами /-уравновешенной метркзш*), а иыеюа, нал зкдение числа пар наборов, отстоящих друг от друга в этой ь трике не более чем на I, нахождение "шара" ыаксиыалыюго об ема, вычисление среднего н максимального "объема шара". Др гой целью работы является классификация булевых функций в < ответствии с их "степенью уравновешенности", решение ЕОЩ сов, касающихся описания, нахождения мощности миолхества уравновешенных функций и оценки слоасности реализации фуі ций из этого множества схемами из функциональных элемента а такзке получение оценок для числа наборов, на которых ї-урі новешгкные функции принимают единичные значения. Научная ковкзва
В работе на основе разработанных методов получены еле. юпгие результаты, являющиеся новыми:
*) '-уравновешенная метрика на множестве двоичных набо} длины п была, введена в работе:
Липатов Е. П. Об одной мере близости между объектами Сборник докладов III международного рабочего семинара "Мв матические вопросы кибернетики", Братислава, 1987. — Бра слава: Университет им. Я. А. Корейского, 198Т, с. 30-54.
.) получены формулы для мощностей множества всех упорядо-енных пар /-уравновешенных наборов длины п и многхества всех аборов, /-уравновешенных с набором -J-* = (1, 0,1, 0,...); для поучения этих формул построены специальные разложения ухазан-
t ых і5К02з:еств на подмножества, для мощностей которых сїіравед-
квы некоторые рекуррентные соотношения;
) решена экстремальная комбинаторная задача нахозхдення явочного яебсра, являющегося /-уравновешенным с наибольшим чистій двоичных наборов длины п, а именно, доказано, что ігабор -'.'зляется таким набором; для решения этой задачи построены реобразовашм и отображения некоторых комбинаторных сбъек-ов (целое специального пида и содержащихся в них ломаных); ) иайяено хинс-е описание миозхестза всех І-уравтювепзєяньїх бу-евых функций н разработал индуктивный метод, позволивший оказать полноту этего описания.
Прахтггчесзаз: ценность
Работа носит теоретический характер. Разработанные в ра-эте методы мигут быть использованы для решения яеречисли-злыпдх и экстремальных комбинаторных задач в различных Зластях дискретной математики (в теории кодирования, тео-пн їптфср*»глі:к, распознавании образов, дискретной геометрии других), а также в исследованиях в области строения и сдогс-эстн булевых функций.
Полученные в работе результаты могут найти применение эк разработке математических моделей в статистической физи-ї, при кластеризации множеств объектов з социологии, при дис-
4 кретном кодировании объектов, обладающих некоторыми сво ствами непрерывности (например, функций).
. Методика исследования В работе используются методы дискретной математики, и тематической кибернетики — главным образом, комбинаторно анализа, теории сложности управляющих систем, и линейной а гебры.
Апробация результатов
Результаты настоящей работы докладывались и обсуау лись на школах-семинарах по синтезу и сложности управляют систем (Нижний Новгород, 1992 и Минск, 1993), шеолє-сєминб по дискретным моделям в теории управляющих систем (Моек: 1993), конференции молодых ученых механико-математнческс факультета МГУ (1993), научных семинарах кафедр дискрет» математики н математической кибернетики Московского униві ситета.
Публикации
Основные результаты диссертации содержатся в работах тора, список которых помещен в конце автореферата [1—4].
Об-ь-ем н структура работы
Диссертация состоит из введения, двух глав, разбитых н параграфов, и списка литературы, включающего 20 наимено ний. Общий объем работы составляет 133 страницы. Изломе: материала проиллюстрировано 26 рисунками и 5 таблицами.