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

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

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 (158 отзывов)
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной с... Читать все
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной специальности 12.00.14 административное право, административный процесс.
    #Кандидатские #Магистерские
    216 Выполненных работ
    Елена С. Таганрогский институт управления и экономики Таганрогский...
    4.4 (93 отзыва)
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на напис... Читать все
    Высшее юридическое образование, красный диплом. Более 5 лет стажа работы в суде общей юрисдикции, большой стаж в написании студенческих работ. Специализируюсь на написании курсовых и дипломных работ, а также диссертационных исследований.
    #Кандидатские #Магистерские
    158 Выполненных работ
    Елена Л. РЭУ им. Г. В. Плеханова 2009, Управления и коммерции, пре...
    4.8 (211 отзывов)
    Работа пишется на основе учебников и научных статей, диссертаций, данных официальной статистики. Все источники актуальные за последние 3-5 лет.Активно и уместно исполь... Читать все
    Работа пишется на основе учебников и научных статей, диссертаций, данных официальной статистики. Все источники актуальные за последние 3-5 лет.Активно и уместно использую в работе графический материал (графики рисунки, диаграммы) и таблицы.
    #Кандидатские #Магистерские
    362 Выполненных работы
    Екатерина Д.
    4.8 (37 отзывов)
    Более 5 лет помогаю в написании работ от простых учебных заданий и магистерских диссертаций до реальных бизнес-планов и проектов для открытия своего дела. Имею два об... Читать все
    Более 5 лет помогаю в написании работ от простых учебных заданий и магистерских диссертаций до реальных бизнес-планов и проектов для открытия своего дела. Имею два образования: экономист-менеджер и маркетолог. Буду рада помочь и Вам.
    #Кандидатские #Магистерские
    55 Выполненных работ
    Катерина В. преподаватель, кандидат наук
    4.6 (30 отзывов)
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации... Читать все
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации. Опыт работы 7 лет. Всегда на связи и готова прийти на помощь. Вместе удовлетворим самого требовательного научного руководителя. Возможно полное сопровождение: от статуса студента до получения научной степени.
    #Кандидатские #Магистерские
    47 Выполненных работ
    Ольга Р. доктор, профессор
    4.2 (13 отзывов)
    Преподаватель ВУЗа, опыт выполнения студенческих работ на заказ (от рефератов до диссертаций): 20 лет. Образование высшее . Все заказы выполняются в заранее согласован... Читать все
    Преподаватель ВУЗа, опыт выполнения студенческих работ на заказ (от рефератов до диссертаций): 20 лет. Образование высшее . Все заказы выполняются в заранее согласованные сроки и при необходимости дорабатываются по рекомендациям научного руководителя (преподавателя). Буду рада плодотворному и взаимовыгодному сотрудничеству!!! К каждой работе подхожу индивидуально! Всегда готова по любому вопросу договориться с заказчиком! Все работы проверяю на антиплагиат.ру по умолчанию, если в заказе не стоит иное и если это заранее не обговорено!!!
    #Кандидатские #Магистерские
    21 Выполненная работа
    AleksandrAvdiev Южный федеральный университет, 2010, преподаватель, канд...
    4.1 (20 отзывов)
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    Пишу качественные выпускные квалификационные работы и магистерские диссертации. Опыт написания работ - более восьми лет. Всегда на связи.
    #Кандидатские #Магистерские
    28 Выполненных работ
    Егор В. кандидат наук, доцент
    5 (428 отзывов)
    Здравствуйте. Занимаюсь выполнением работ более 14 лет. Очень большой опыт. Более 400 успешно защищенных дипломов и диссертаций. Берусь только со 100% уверенностью. Ск... Читать все
    Здравствуйте. Занимаюсь выполнением работ более 14 лет. Очень большой опыт. Более 400 успешно защищенных дипломов и диссертаций. Берусь только со 100% уверенностью. Скорее всего Ваш заказ будет выполнен раньше срока.
    #Кандидатские #Магистерские
    694 Выполненных работы
    Татьяна П.
    4.2 (6 отзывов)
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки ... Читать все
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки в одном из крупнейших университетов Германии.
    #Кандидатские #Магистерские
    9 Выполненных работ

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

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

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