Эффективные алгоритмы анализа джевонс-эквивалентности данных

Кукарцев, Анатолий Михайлович

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 приведены оценки времени
работы тривиальных алгоритмов.

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

    Нажимая на кнопку, я соглашаюсь на обработку персональных данных и с правилами пользования Платформой

    Помогаем с подготовкой сопроводительных документов

    Совместно разработаем индивидуальный план и выберем тему работы Подробнее
    Помощь в подготовке к кандидатскому экзамену и допуске к нему Подробнее
    Поможем в написании научных статей для публикации в журналах ВАК Подробнее
    Структурируем работу и напишем автореферат Подробнее

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Лидия К.
    4.5 (330 отзывов)
    Образование высшее (2009 год) педагог-психолог (УрГПУ). В 2013 году получено образование магистр психологии. Опыт преподавательской деятельности в области психологии ... Читать все
    Образование высшее (2009 год) педагог-психолог (УрГПУ). В 2013 году получено образование магистр психологии. Опыт преподавательской деятельности в области психологии и педагогики. Написание диссертаций, ВКР, курсовых и иных видов работ.
    #Кандидатские #Магистерские
    592 Выполненных работы
    Екатерина С. кандидат наук, доцент
    4.6 (522 отзыва)
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    #Кандидатские #Магистерские
    1077 Выполненных работ
    Яна К. ТюмГУ 2004, ГМУ, выпускник
    5 (8 отзывов)
    Помощь в написании магистерских диссертаций, курсовых, контрольных работ, рефератов, статей, повышение уникальности текста(ручной рерайт), качественно и в срок, в соот... Читать все
    Помощь в написании магистерских диссертаций, курсовых, контрольных работ, рефератов, статей, повышение уникальности текста(ручной рерайт), качественно и в срок, в соответствии с Вашими требованиями.
    #Кандидатские #Магистерские
    12 Выполненных работ
    Анна В. Инжэкон, студент, кандидат наук
    5 (21 отзыв)
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссе... Читать все
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссертаций. Работала в маркетинге. Практикующий бизнес-консультант.
    #Кандидатские #Магистерские
    31 Выполненная работа
    Екатерина Б. кандидат наук, доцент
    5 (174 отзыва)
    После окончания института работала экономистом в системе государственных финансов. С 1988 года на преподавательской работе. Защитила кандидатскую диссертацию. Преподав... Читать все
    После окончания института работала экономистом в системе государственных финансов. С 1988 года на преподавательской работе. Защитила кандидатскую диссертацию. Преподавала учебные дисциплины: Бюджетная система Украины, Статистика.
    #Кандидатские #Магистерские
    300 Выполненных работ
    Евгения Р.
    5 (188 отзывов)
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и со... Читать все
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и создаю красивые презентации. Сопровождаю работы до сдачи, на связи 24/7 ?
    #Кандидатские #Магистерские
    359 Выполненных работ
    Андрей С. Тверской государственный университет 2011, математический...
    4.7 (82 отзыва)
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на... Читать все
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на продолжение диссертационной работы... Всегда готов помочь! ;)
    #Кандидатские #Магистерские
    164 Выполненных работы
    Ольга Б. кандидат наук, доцент
    4.8 (373 отзыва)
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских... Читать все
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских диссертаций, дипломных и курсовых работ. Слежу за новинками в медицине.
    #Кандидатские #Магистерские
    566 Выполненных работ
    Глеб С. преподаватель, кандидат наук, доцент
    5 (158 отзывов)
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной с... Читать все
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной специальности 12.00.14 административное право, административный процесс.
    #Кандидатские #Магистерские
    216 Выполненных работ

    Последние выполненные заказы

    Другие учебные работы по предмету

    Расширенное суперпиксельное представление изображений для их обработки и анализа
    📅 2022год
    🏢 ФГАОУ ВО «Самарский национальный исследовательский университет имени академика С.П. Королева»
    Метод восстановления динамических изображений на основе оптимальной интерполяции
    📅 2022год
    🏢 ФГАОУ ВО «Самарский национальный исследовательский университет имени академика С.П. Королева»
    Метод конверсационного анализа неструктурированных текстов социальных сетей
    📅 2021год
    🏢 ФГАОУ ВО «Самарский национальный исследовательский университет имени академика С.П. Королева»