Читать онлайн «Дискретная математика: учебное пособие. Ч.1. Основные алгебраические структуры»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ЯДЕРНЫЙ УНИВЕРСИТЕТ «МИФИ» А. Н. ИВАНОВ ДИСКРЕТНАЯ МАТЕМАТИКА ЧАСТЬ 1. ОСНОВНЫЕ АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ УЧЕБНОЕ ПОСОБИЕ Москва 2010 УДК 512. 62 ББК 22. 144 И 17 Иванов А. Н. Дискретная математика. Часть 1. Основные алгеб- раические структуры. Учебное пособие. В 4-х частях. М. : НИЯУ МИФИ. 2010. 188 с. Даны основные алгебраические структуры, используемые в дис- кретной математике и ее приложениях. Приведены примеры, ил- люстрирующие рассматриваемые понятия, определения и теоремы. Все разделы снабжены упражнениями для самостоятельной рабо- ты, а пособие дополнено набором вариантов домашних заданий. Главная задача учебного пособия заключается в оказании по- мощи студентам при первоначальном изучении алгебраических понятий дискретной математики и подготовке к изучению соответ- ствующих разделов специальной литературы. Во 2-й части пособия изложены основы комбинаторики, теории графов и сетевых моделей. 3-я часть посвящена математической логике, теории автоматов и сложности вычислений. 4-я часть со- держит практические примеры использования дискретных матема- тических моделей в криптографии, помехоустойчивом кодирова- нии, цифровой обработке сигналов и сжатии данных Пособие предназначено студентам специальности «Прикладная математика» факультета «К» НИЯУ МИФИ при изучении курса «Дискретная математика», а также может быть рекомендовано к использованию в учебном процессе факультета «Б». Рецензент доцент каф. 42 И. А. Юров Рекомендовано редсоветом НИЯУ МИФИ в качестве учебного пособия ISBN 978-5-7262-1197-8 © Национальный исследовательский ядерный университет «МИФИ», 2010  ОГЛАВЛЕНИЕ Предисловие……………………………………………………………4 1. Множества…………………………………………………………... 6 1. 1. Операции, отображения и преобразования……………………6 1. 2 Бинарные отношения . ………………………………………. . 17 Упражнения…………………………………………………... . 30 Список литературы…………………………………………... . 31 2. Группы……………………………………………………………. . 32 2. 1. Способы задания групп………………………………………. 32 2. 2. Подгруппы……………………………………………………. . 49 2. 3. Нормальные подгруппы………………………………………. 61 2. 4. Факторгруппы………………………………………………… 66 Упражнения……………………………………………………70 Список литературы……………………………………………71 3. Кольца…………………………………………………………… 72 3. 1. Кольцо многочленов…………………………………………. . 83 3. 2. Кольцо целых чисел…………………………………………... 97 Упражнения…………………………………………………. . 108 Список литературы…………………………………………. . 109 4. Конечные поля……………………………………………………110 4. 1. Характеризация конечных полей……………………………110 4. 2. Первообразные корни и индексы……………………………119 4. 3. Многочлены над конечными полями………………………. 131 4. 4. Алгоритм Берлекэмпа разложения многочленов…………. . 144 4. 5. Коды Боуза-Чоудхури-Хоккенгема…………………………149 Упражнения…………………………………………………. . 153 Список литературы…………………………………………. . 154 Приложение 1. Варианты домашних заданий……………………. 155 Приложение 2.