теория кодирования дискретная математика

Основы дискретной математики

Привет, хабр. В преддверии старта базового курса «Математика для Data Science» делимся с вами переводом еще одного полезного материала.

Об этой статье

Эта статья содержит лишь малую часть информации по заявленной теме. Рассматривайте ее как вводный курс перед началом всестороннего изучения предмета. Надеюсь, вы найдете в ней полезную информацию. Знание дискретной математики помогает описывать объекты и задачи в информатике, особенно когда дело касается алгоритмов, языков программирования, баз данных и криптографии. В дальнейшем я планирую подробнее раскрыть темы, затронутые в этой статье. Приятного чтения!

ЧТО ТАКОЕ ДИСКРЕТНАЯ МАТЕМАТИКА?

Это область математики, изучающая объекты, которые могут принимать только уникальные отдельные значения.

Мы рассмотрим пять основных разделов в следующем порядке.

ЛОГИКА

Что такое логика?

Это наука о корректных рассуждениях. Мы будем использовать приемы идеализации и формализации. Неформальная логика изучает использование аргументов в естественном языке.

Формальная логика анализирует выводы с чисто формальным содержанием. Примерами формальной логики являются символическая логика и силлогистическая логика (о которой писал Аристотель).

Начнем с азов. Рассмотрим следующее высказывание на естественном языке:

«Если я голоден, я ем».

Пусть «голоден» будет посылкой A, а «ем» — следствием B. Попробуем формализовать:

A => B (то есть из A следует B)

NB. Посылка и следствие являются суждениями.

Логические выражения

Для нас важна форма, а НЕ содержание. Значение будет истинным, если оно соответствует форме.

Например, 10 4 — ИСТИНА.

Логические операции

Суждение P — это утверждение, которое может быть как истинным, так и ложным.

Обозначим истинное значение P единицей (1), а ложное значение P нулем (0).

Существует другое суждение; обозначим истинное значение Q единицей (1), а ложное значение Q нулем (0).

Рассмотрим логические операции с суждениями, значение которых истинно. Они могут сами образовывать истинные значения путем выполнения соответствующих операций над истинными значениями.

Источник

Математические основы кодирования и шифрования

Информационное взаимодействие абонентов в компьютерных и связных сетях подвергается возмущениям, которые приводят к возникновению ошибок и возмущений разного рода. Помимо возникновения ошибок в передаваемых сообщениях возможен несанкционированный доступ к содержанию сообщений нарушителя. Борьба с этими нежелательными явлениями ведется тысячелетиями, но с переменным успехом. Создатели Интернета задумывали его совсем не таким, каким он стал сейчас. О хакерах тогда и не думали.

Основные теоретические проблемы информационного противостояния, задачи по их решению возлагаются на теории кодологии, криптологии и стеганологии, в которых во всем мире интенсивно развиваются направления кодоанализа, криптоанализа и стегоанализа. Практические аспекты также не остаются в стороне, но замечу, что в РФ активность не очень-то высока, сказывается инертность молодых (сам я разменял уже 9-й десяток, но администрация Хабра ограничила возрастной ценз 1950 г). Мое мнение, конечно, ограничено наблюдением потомства (вплоть до правнуков) и общением в интернете, а также с обучаемыми и сотрудниками фирмы, где подрабатываю. СМИ тоже добавляют негатива. Кто из молодежи чуть поумнел, уходят за бугор. Поведение остальных видите сами.

Экскурс по публикациям

Разработка (синтез) технических устройств требует от разработчика определенных знаний, умений ими пользоваться и других навыков подобного рода. Существенная составляющая таких знаний — математическая. Это, как правило, алгебра, дискретная математика, геометрия, физика, математическая логика и др. Здесь в статье будем рассматривать алгебраические структуры не совсем в классическом изложении, но с достаточными уровнем строгости и точностью. Главной моей задачей является обеспечение доступности и понятности изложения вещей, которые я использую в своих текстах и изысканиях.

Например, здесь используется поле расширения GF (2 8 ) и, если обойтись без него, ничего стоящего изложить не удается. Мои критерии оценки просты. Каждый семестр 2, а то и 3 экзамена и зачеты в разных учебных группах. Там слышу и вижу, что я излагал, выносил на практику, и что мне возвращают в ответах по экзаменационным билетам. Очень полезен анализ экзаменационных ответов, вижу, что следовало бы излагать кое-что по-другому, лучше.

А здесь свойства Z_N конечного числового кольца вычетов по составному модулю N =pq используются для поиска решения задачи факторизации больших чисел в рамках нового оригинального подхода. Понятно, что в каждой из последующих публикаций переносить часть стандартных математических средств было бы неразумно, посему принято решение собрать все в одном месте и при необходимости адресовать сюда читателей.

Здесь же рассматривается и используется группа точек эллиптической кривой на плоскости. Операция суммирования в группе очень специального вида, вызывающая недоуменные вопросы, типа как это Вам удается складывать точки кривой, даже от членов ГЭК.

Группы

Предварительно введем ряд необходимых определений.

Определение. Конечное множество А-набор, совокупность любых n объектов , перечисляемых в любом порядке, но среди которых нет повторяющихся. Множества бывают структурированные, над элементами которых задана одна (или более) операция и отношений и неструктурированные, когда операции не заданы.

Ниже, как напоминание, приводится таблица действий (операций) с конечными дискретными множествами, а на диаграммах для наглядности показаны и непрерывные множества А и В.

Таблица операций с множествами

Определение. Группа — это множество G элементов (любой природы), над которыми задана единственная операция, но она может быть сложением (+) и группа называется аддитивной, ее нейтральный элемент (0) или умножением (◦) — называется мультипликативной, ее нейтральный элемент (1), но как правило, операции эти не обычные арифметические, а специальные. Обозначается группа часто символом (G,◦), среди всех групп важное место отводится симметрическим группам перестановок степени n.

Определение.Части элементов группы, сохраняющие свойства и операцию группы называются подгруппами. В сущности это такие же группы, только меньше исходной. Это неформальное определение группы, формальное будет приведено чуть позже.

Примером аддитивной группы является набор слов кода Хемминга (см.здесь). Операция в этой группе 16 порядка — суммирование слов по (mod2). С этой группой выполнялась операция разложения в смежные классы группы из 128 слов по подгруппе кода, а также строилась таблица Кели, элементы группы используются в кодере (базис пространства размерности 4) и декодере. Одним словом этот пример наглядно демонстрирует как может использоваться даже маленькая группа для решения очень важной практической задачи (связь).

Очень важными в теории групп являются симметрические группы подстановок (перестановок). Эта важность определяется теоремой, в которой говорится, что для любой группы, возникающей в произвольной предметной области, существует изоморфная ей симметрическая группа (подгруппа) на перестановках. Тогда исследователю новой открытой группы задача ее изучения упрощается. Почти все свойства изоморфной группы перестановок имеют место и в новой группе.

Начнем с простого примера. Заданы n элементов (обозначим их цифрами 1,2,3. n) и образуем из них перестановки, число которых n! = 1·2·3·. ·n. Ограничимся значением n=3, тогда 3! = 6.

Определение. Порядок группы — число элементов в группе называется ее порядком. В примере число 6 — это порядок группы.

В группе каждый элемент также имеет порядок, который является делителем порядка группы.
Определение. Порядок элемента группы — это наименьший показатель степени элемента в мультипликативной группе (кратности в аддитивной b+b+b+b+. b =nb = 0, порядок =n), при котором он обращается в нейтральный элемент, например () 3 =1, порядок ord() = 3.

В симметрической группе операцией является умножение перестановок. Это умножение аналогично матричному умножению, так как каждой перестановке степени n ставится в соответствие квадратная перестановочная матрица размерности n×n, в которой каждая строка и столбец содержат единственную единицу. Ниже это показано для симметрической группы.

Для удобства работы с группой и ее элементами математиком Кели предложена таблица операций группы (ограниченного размера). В клетке на пересечении строки и столбца ставится результат операции с элементами, которые их обозначают. Результат (как и обозначение строк/столбцов) в таблице представляется десятичными номерами элементов, что экономит место.

Таблица умножения элементов (перестановок) группы

Заполнение 36 клеток таблицы умножения упрощается, если воспользоваться свойствами таблицы Кели.
— Все строки и столбцы содержат элементы всей группы.
— Крайние столбцы лексикографически упорядочены и встречно направлены (1-й сверху/вниз — последний наоборот)
— На главной диагонали таблицы стоят квадраты элементов, если там стоит 1, то элемент ей соответствующий — инволюция; инволюциями в являются
— Относительно диагоналей матрицы выполняется симметрия положений элементов.
Свойства таблицы позволяют при ее заполнении ограничиться вычислениями только 13 пар элементов (выше они показаны).

Симметрическая группа

Группа имеет маленький порядок (6) и для иллюстрации свойств не очень удобна. Далее будут приводится примеры с симметрической группой 24 порядка. Все четные перестановки степени n образуют знакопеременную подгруппу в симметрической группе, обозначаемую символом А_n.

Таблица 2 может использоваться для нахождения произведений любой пары элементов или для их целой цепочки, но находятся последовательным умножением результата на следующий элемент. Переставлять местами элементы в произведении нельзя. Операция умножения перестановок не коммутативна, как и умножение матриц. Один элемент при многократном умножении на себя, пока не получится 1, образует циклическую группу из всех промежуточных результатов. Порядок такой циклической подгруппы является порядком порождающего элемента, он должен делить порядок исходной большой группы.

По таблице умножения находятся подгруппы в составе большой группы. Необходимо помнить, что порядок меньшей подгруппы должен делить порядок большей.
Построим циклическую группу с порождающим р₁₄ элементом. Входим в таблицу 2. В строке 14 находим на пересечении с р₁₄ столбцом элемент р₂₄; в строке 24 находим в клетке пересечения с 14 столбцом элемент р₁₁ и наконец в клетке строки 11 на пересечении со столбцом 14 находим элемент р₁, т.е. нейтральный элемент 1. Итак, р₁₄·р₁₄·р₁₄·р₁₄ = р₁, это элементы подгруппы 4-го порядка, значение которого нацело делит порядок 24:4 = 6. Для нее можно построить таблицу Кели и в ней не будут появляться никакие элементы кроме найденных.В этой подгруппе элементы р₁₄ и р₁₁ имеют 4-й порядок, а р₂₄ второй — это инволюция.

Морфизмы групп

Элементы образа с операцией над ними (+), а в прообразе элементы связаны операцией (◦) умножения. Гомоморфный образ группы есть группа (подгруппа), т.е., если f-гомоморфизм G на G’ и G — группа, то и G’ — группа. Гомоморфизм — обобщение изоморфизма групп: если f — взаимно однозначное гомоморфное отображение G на G’, то оно изоморфно, что обозначается так G≈G’.
Две группы G и G’ с операциями (·) и (*) называются изоморфными, если существует отображение f: G → G’ такое, что (отображение f сохраняет групповую операцию) образа;

Теорема. Пусть Н — нормальная подгруппа группы G и G=G/H. Тогда отображение f группы G на G, заданное формулой f(a) =a является гомоморфизмом. Ядро этого гомоморфизма есть Н. Этот гомоморфизм часто называют естественным (каноническим).
Гомоморфизмы группы по существу исчерпываются каноническими гомоморфизмами.

Выполним разложение группы G 24-го порядка по ее подгруппе H = <1,8, 17,24>в смежные классы и построим для этого разложения факторгруппу по подгруппе Н. С этой целью выпишем в столбцы левые и правые произведения элементов подгруппы Н.

В таблице разложения группы G порядка 24 на классы смежности по подгруппе Н обозначены столбцы л1, л2, л3, л4, л5 имена левых и п1, п2, п3, п4, п5 — правых смежных классов, ведущие представители классов по одному на столбец выписаны в следующей строке.

Средний столбец Н — группа 4-го порядка (ядро гомоморфизма). Столбцы заполняются произведениями ведущих представителей классов на элементы группы Н. После заполнения столбцов выполняется сравнение классов. Если составы левых и правых классов совпадают, то говорят просто о классах смежности и обозначают Н = К0, К1, К2, К3, К4, К5. При этом подгруппа Н называется нормальной. Ведущим представителем очередного класса при заполнении таблицы выбирается наименьший элемент G, из не вошедших в уже построенные классы.

Полученные классы смежности далее рассматриваются как элементы новой группы, называемой факторгруппой группы G по подгруппе Н (обозначается факторгруппа G =G/H). Операцией в этой новой группе является умножение классов: для каждой пары классов, например, К3×К5 = К2 строится таблица 4×4, в которой строки помечаются элементами первого сомножителя, а столбцы — второго. Далее выполняют умножение как в группе G. Результат такого умножения дает 16 элементов, но все они принадлежат одному классу, в нашем случае классу К2.

Кроме отображений изоморфизмов гомоморфизмами являются эндоморфизмы и автоморфизмы. Гомоморфизм группы G в себя называется эндоморфизмом, а изоморфизм группы G на себя- автоморфизмом. Эти понятия сопоставимы с понятиями отображений неструктурированных множеств инъекцией, сюръекцией и биекцией.

Коммутант

Группа G называется разрешимой, если цепочка G ⊇ G’ ⊇ G» ⊇… ⊇ G (i) ⊇. где каждая подгруппа G (i) является коммутантом предыдущей, обрывается после конечного числа шагов на единичной подгруппе, например, G (е) = 1.
В таблице 4 знакопеременная подгруппа G’ =А₄ порядка 12 — нормальная, из G = порядка 24, так как левый и правый смежные классы по этой подгруппе совпадают (классы это одно и тоже дополнение до полной группы ). Таблица 4 при этом сворачивается в меньшую 4×4 таблицу (коммутант), содержащую элементы G» = <1,8,17,24>новой подгруппы, коммутант которой равен 1. Таблица 4 иллюстрирует разрешимость группы .

Заключение

В статье рассмотрены некоторые основные положения теории групп, которые часто используются в публикациях технического (не теоретико-математического) характера. Понимание текста таких публикаций во многом определяется владением математическим инструментарием.

Для группы приводится пример и техника гомоморфного отображения её в факторгруппу.
Числовые примеры призваны служить обеспечению доступности излагаемого материала и в большой мере помогают его пониманию и усвоению, при внимательном их разборе или даже повторении с карандашом в руках. Что в классических руководствах просто отсутствует. Часто объясняют это экономией места и времени.
Ожидаю реакции читателей, по которой станет понятно, продолжать ли в этом стиле или нет.

Источник