Эффективные алгоритмы анализа джевонс-эквивалентности данных
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Глава 1. Представление группы Джевонса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
§ 1.1. Основные обозначения, объекты и операции. . . . . . . . . . . . . . . . . . . . . .15
§ 1.2. Действие группы подстановок на множестве БВ . . . . . . . . . . . . . . . . . 18
§ 1.3. Контрольные примеры действия подстановок над БВ . . . . . . . . . . . . 21
§ 1.4. Выбор представления группы Джевонса . . . . . . . . . . . . . . . . . . . . . . . . . . 25
§ 1.5. Контрольные примеры операций в группе Джевонса . . . . . . . . . . . . . 34
§ 1.6. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Глава 2. Действие группы Джевонса на множествах . . . . . . . . . . . . . . . . . . . . . . . . . 38
§ 2.1. Действие группы Джевонса на множестве БВ . . . . . . . . . . . . . . . . . . . . 38
§ 2.2. Действие группы Джевонса на множестве БФ . . . . . . . . . . . . . . . . . . . . 42
§ 2.3. Эквиморфизм группы Джевонса и группы βn . . . . . . . . . . . . . . . . . . . . 44
§ 2.4. Частотные свойства БВ и БФ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48
§ 2.5. Частотные свойства действия группы Джевонса . . . . . . . . . . . . . . . . . 50
§ 2.6. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Глава 3. Исследование джевонс-эквивалентности данных . . . . . . . . . . . . . . . . . . . . 55
§ 3.1. Формальная постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
§ 3.2. Каноническое представление элемента группы Джевонса . . . . . . . . 57
§ 3.3. Основной алгоритм решения уравнения . . . . . . . . . . . . . . . . . . . . . . . . . . 61
§ 3.4. Эквиморфный вычислитель. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67
§ 3.5. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Глава 4. Оценки сложности предложенных решений . . . . . . . . . . . . . . . . . . . . . . . . . 78
§ 4.1. Теоретические оценки сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
§ 4.2. Анализ тривиальности подгрупп инерции булевых функций . . . . . 80
§ 4.3. Спектральный анализ булевых функций . . . . . . . . . . . . . . . . . . . . . . . . . 84
§ 4.4. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Список сокращений и условных обозначений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Приложение А. Подробная статистика классов БФ . . . . . . . . . . . . . . . . . . . . . . . . . 107
Приложение Б. Каталоги классов БФ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Приложение В. Результаты спектрального анализа . . . . . . . . . . . . . . . . . . . . . . . . . 114
Приложение Г. Результаты вычислительных экспериментов . . . . . . . . . . . . . . . . 117
Актуальность темы и степень её разработанности. Цифровая ин-
формация представляется преимущественно двумя способами: комбинацион-
ным и функциональным. Первый рассматривает её в виде комбинации симво-
лов некоторого алфавита, а второй – в виде множества значений некоторой
дискретной функции. Комбинационные способы представления информации
и соответствующие им алгоритмы её обработки начали развиваться с начала
ХХ века. Эти способы представления обычно связывают с работами К. Шенно-
на [1], Р. В. Хэмминга [2] и многих других исследователей. В конце XX века в
связи с развитием информационных технологий и естественной потребностью
в качественно новых методах обработки информации начали появляться функ-
циональные способы её представления. Одним из примеров обработки инфор-
мации в таком представлении является серия алгоритмов сжатия графических
данных JPEG [3]. Цифровая информация отображается на некоторую функцию
двух аргументов. Далее функция преобразуется и определяющие её парамет-
ры (коэффициенты Фурье) округляются, кодируются, и их коды сжимаются
комбинационными методами. Такой способ сжатия, как правило, приводит к
потерям информации во время преобразования.
Для функционального представления цифровой двоичной информации
естественно подходят булевы функции (далее – БФ) [4]. Любому бинарному
вектору (далее – БВ), состоящему из нулей и/или единиц, можно инъектив-
но поставить в соответствие БВ длины, кратной степени двойки. Последнему
можно взаимно однозначно поставить некоторую БФ. Для этого важно одно-
значно упорядочить область определения БФ. Это можно выполнить, зафик-
сировав порядок её аргументов, и в соответствии с ним упорядочить область
её определения, например, лексикографически. Сама БФ может быть описана
реализующими её функциональными элементами или формулой [5]. Множе-
ства отрицаний и перестановок аргументов БФ образуют группу Джевонса [6]
и определяют действие над БФ. Указанное действие замечательно тем, что оно
нейтрально, т.к. не затрагивает связей между функциональными элементами
и не меняет формулы. Джевонс-эквивалентные БФ будут иметь одинаковые
КНФ и ДНФ [7]. Такое действие задаёт естественную эквивалентность БФ и,
как следствие, джевонс-эквивалентность соответственных им данным.
Группа Джевонса была определена в конце XIX века С. Джевонсом для
описания действия над системой связанных понятий, представленных в виде
БФ [6]. Более формальное представление этой группы и другое её название
(гипероктаэдральная группа) были предложены А. Янгом [8] в 1930 г. Работы,
связанные с группой Джевонса и её приложениями, ведутся с начала XX века, –
как за рубежом, так и в России. К ним можно отнести, прежде всего, работы о
представлении группы и изучении её свойств исследователей Л. Гейссингера и
Д. Кинча [9], М. Баака [10], В. Н. Иванова [11], С. Билли и Т. К. Ламма [12],
М. Парвафи, Б. Сивакумара и А. Тамилселви [13], Б. Бьянок [14], Дж. Кон-
да [15], Б. В. Олийныка и В. И. Сущанского [16, 17] и др.; труды, связанные с
теорией перечислений исследователей Д. Слепиана [18], П. Константинески [19],
Н. Дж. Де Брёйна [20] и др.; практические работы, связанные с кодированием
и обработкой информации исследователей О. В. Денисова [21], Д. Г. Видеман-
на [22] и др.; теоретические и прикладные работы в области криптографии и
криптологии исследователей А. В. Тарасова [23], В. Г. Никонова и А. В. Саран-
цева [24], М. Л. Бурякова и О. А. Логачева [25], Б. А. Погорелова и М. А. Пу-
довкиной [26, 27], С. П. Горшкова [28], Е. К. Алексеева и Е. К. Карелиной [29]
и др.; труды в области генетики исследователей С. Ханненнфлли и П. А. Пе-
взнера [30] и др.; работы в области кристаллографии исследователей Э. Заппа,
Э. Дюкмана, и Р. Тварока [31]. К известным нерешенным проблемам, связан-
ным с группой Джевонса, относится также Burnt Pancake problem о сортировке
префикс-реверсалами, сформулированная Б. Гейтсом и К. Пападимитроу [32].
Перечислим некоторые важные проблемы в этой предметной области:
– анализ джевонс-эквивалентности данных;
– поиск элементов группы, связывающих джевонс-эквивалентные данные.
Поэтому необходимы эффективные алгоритмы, т.е. такие, которые могут
находить решение указанных проблем за разумное время. Как известно, по-
рядок группы Джевонса для БФ n переменных равен 2n · n!. Исходя из этого,
оценим возможность применения тривиальных алгоритмов, перечисляющих все
элементы группы. Время проверки одного элемента составляет τ(n) = 10−9 · 2n ,
где 2n – число значений БФ и 10−9 с – примерное время вычисления одно-
го значения на ЭВМ (1 ГГц). Тогда полное время работы алгоритма составит
T ime(n) = τ(n) · dtrivial = τ(n) · 2n · n!, где dtrivial – число действий над БФ три-
виальным алгоритмом (порядок группы). В табл. 1 приведены оценки времени
работы тривиальных алгоритмов.
Помогаем с подготовкой сопроводительных документов
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!