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

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

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 экспертов уже готовы начать работу над твоим проектом!

    Евгения Р.
    5 (188 отзывов)
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и со... Читать все
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и создаю красивые презентации. Сопровождаю работы до сдачи, на связи 24/7 ?
    #Кандидатские #Магистерские
    359 Выполненных работ
    Родион М. БГУ, выпускник
    4.6 (71 отзыв)
    Высшее экономическое образование. Мои клиенты успешно защищают дипломы и диссертации в МГУ, ВШЭ, РАНХиГС, а также других топовых университетах России.
    Высшее экономическое образование. Мои клиенты успешно защищают дипломы и диссертации в МГУ, ВШЭ, РАНХиГС, а также других топовых университетах России.
    #Кандидатские #Магистерские
    108 Выполненных работ
    Елена Л. РЭУ им. Г. В. Плеханова 2009, Управления и коммерции, пре...
    4.8 (211 отзывов)
    Работа пишется на основе учебников и научных статей, диссертаций, данных официальной статистики. Все источники актуальные за последние 3-5 лет.Активно и уместно исполь... Читать все
    Работа пишется на основе учебников и научных статей, диссертаций, данных официальной статистики. Все источники актуальные за последние 3-5 лет.Активно и уместно использую в работе графический материал (графики рисунки, диаграммы) и таблицы.
    #Кандидатские #Магистерские
    362 Выполненных работы
    Екатерина Б. кандидат наук, доцент
    5 (174 отзыва)
    После окончания института работала экономистом в системе государственных финансов. С 1988 года на преподавательской работе. Защитила кандидатскую диссертацию. Преподав... Читать все
    После окончания института работала экономистом в системе государственных финансов. С 1988 года на преподавательской работе. Защитила кандидатскую диссертацию. Преподавала учебные дисциплины: Бюджетная система Украины, Статистика.
    #Кандидатские #Магистерские
    300 Выполненных работ
    Татьяна М. кандидат наук
    5 (285 отзывов)
    Специализируюсь на правовых дипломных работах, магистерских и кандидатских диссертациях
    Специализируюсь на правовых дипломных работах, магистерских и кандидатских диссертациях
    #Кандидатские #Магистерские
    495 Выполненных работ
    Дарья Б. МГУ 2017, Журналистики, выпускник
    4.9 (35 отзывов)
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных ко... Читать все
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных компаниях, сейчас работаю редактором. Готова помогать вам с учёбой!
    #Кандидатские #Магистерские
    50 Выполненных работ
    Оксана М. Восточноукраинский национальный университет, студент 4 - ...
    4.9 (37 отзывов)
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политоло... Читать все
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политологии.
    #Кандидатские #Магистерские
    68 Выполненных работ
    Кирилл Ч. ИНЖЭКОН 2010, экономика и управление на предприятии транс...
    4.9 (343 отзыва)
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). С... Читать все
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). Сейчас пишу диссертацию на соискание степени кандидата экономических наук.
    #Кандидатские #Магистерские
    692 Выполненных работы
    Сергей Е. МГУ 2012, физический, выпускник, кандидат наук
    4.9 (5 отзывов)
    Имеется большой опыт написания творческих работ на различных порталах от эссе до кандидатских диссертаций, решения задач и выполнения лабораторных работ по любым напра... Читать все
    Имеется большой опыт написания творческих работ на различных порталах от эссе до кандидатских диссертаций, решения задач и выполнения лабораторных работ по любым направлениям физики, математики, химии и других естественных наук.
    #Кандидатские #Магистерские
    5 Выполненных работ

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

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