4.2. Содержание разделов и результаты изучения дисциплины

Указывается название каждого раздела дисциплины (в соответствии с разделом 4.1 РПД) и формулируется его содержание, раскрывающее сущность учебного материала. Рекомендуется в разделах дисциплины указывать знания, умения и навыки, формируемые при их изучении.

Разделы дисциплины и их содержание	Результаты обучения^10
1. Элементы теории множеств и математической логики.
1.1. Основные понятия теории множеств, логики высказываний и предикатов. Высказывания. Булевы функции, арность, существенные и фиктивные переменные, суперпозиция. Логические связки (операции): соответствие в русском/английском языках, таблицы истинности. Логические законы. Тавтологии и противоречия. Принцип двойственности. Предикаты. Множество, элемент, подмножество. Задание множеств перечислением, описание с помощью характеристических предикатов. Булевы операции над множествами. Диаграммы Венна. Кортежи. Декартово произведение. Прямое (дизъюнктное) объединение. Мощность множества, кардинальные числа.	Знания на уровне понятий, определений, описаний, формулировок. Пропозициональные переменные. Логические связки (операции): Таблицы истинности. Предикаты. Логические законы. Множество, элемент, подмножество. Кортежи. Декартово произведение. Умения в решении задач. Применять диаграммы Венна. Вычислять значение истинности составных высказываний. Выполнять преобразования логических формул с применением логических законов. Описывать подмножества с помощью характеристических предикатов. Строить объединение, пересечение, разность, декартово произведение множеств.
1.2. Булевы функции и алгебры. Совершенные нормальные формы. Булеан и алгебра подмножеств. Булевы функции. Булевы алгебры. Алгебра полиномов Жегалкина. Теорема Стоуна. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Карты Карно. Существенные и фиктивные переменные. Минимизация СДНФ алгоритмом Квайна-Мак-Клоски. Предикаты, предваренные кванторами. Свободные и связанные переменные. Предложения. Интерпретации переменных и истинность. Диаграммы Эйлера. Правило отрицания универсально/экзистенциально квантифицированного предиката.	Знания на уровне понятий, определений, описаний, формулировок. Булевы функции и алгебры. Совершенные нормальные формы. Алгебра полиномов Жегалкина. Алгебра подмножеств. Теорема Стоуна. Знания на уровне доказательств и выводов. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Умения в решении задач. Строить булеан конечного множества. Вычислять совершенную дизъюнктивную / конъюнктивную нормальную форму, многочлен Жегалкина булевой функции, заданной таблицей. Минимизировать СДНФ алгоритмом Квайна-Мак-Клоски. Преобразовывать негативное предложение в позитивное.
1.3. Теорема Поста о функциональной полноте. Исчисление высказываний. Линейность, монотонность, самодвойственность, сохранение 0/1. Функциональная полнота. Теорема Поста. Формальная система (исчисление): алфавит, формулы (выражения), аксиомы, правила вывода, теоремы. Алгебраические системы. Модели формальных теорий. Порождение множеств исчислениями. Исчисление высказываний, непротиворечивость, полнота, разрешимость.	Знания на уровне понятий, определений, описаний, формулировок. Линейность, монотонность, самодвойственность, сохранение 0/1. Функциональная полнота. Теорема Поста. Алгебраическая система. Формальная система (исчисление). Исчисление высказываний: аксиомы, правила вывода, непротиворечивость, полнота, разрешимость. Знания на уровне доказательств и выводов. Свойства логических связок. Умения в решении задач. Проверять свойства булевых функций и применять теорему Поста. Описывать порождение множества выражений продуктивным исчислением.
1.3. Исчисление предикатов. Исчисление предикатов чистое (ИПЧ): алфавит, формулы, аксиомы, правила вывода. Непротиворечивость, полнота, неразрешимость ИПЧ (Чёрч). Логические и нелогические (содержательные) аксиомы теорий. Прикладные теории 1-го порядка. Формализация N арифметики (без схемы аксиом индукции Пеано). Теорема Гёделя о неполноте рекурсивно-аксиоматизируемых расширений арифметики N, в частности, - арифметики Пеано.	Знания на уровне понятий, определений, описаний, формулировок. Исчисление предикатов чистое: алфавит, формулы, аксиомы, правила вывода. Непротиворечивость, полнота, неразрешимость ИПЧ (Чёрч). Логические и нелогические (содержательные) аксиомы теорий. Теорема Гёделя о неполноте рекурсивно-аксиоматизируемых расширений арифметики N. Умения в решении задач. Доказывать теоремы с помощью аксиом и правил вывода исчисления предикатов.
2.  Основы теории алгебраических систем и чисел.
2.1.  Алгебраические отношения между множествами. Алгебраические системы. Отношения, арность, график. Соответствия: проекции, композиция, транспонирование. Алгебраические системы, модели и алгебры. Представление бинарного отношения матрицей инцидентности, [ор]графы. Возможные свойства: [анти]рефлексивность, [анти]симметричность, транзитивность, ди/трихотомичность, функциональность. Отображения, сюръективность, инъективность, биективность. Отношение эквивалентности на множестве, классы эквивалентных элементов. Фактор-множество по отношению эквивалентности. Разбиения и эквивалентности. Отношения предпорядка, частичного и линейного порядков, доминирования на множестве. Диаграммы Хассе. Факторизация предупорядоченного множества до частичного упорядочения. Наибольший и наименьший, максимальный и минимальный, [не]сравнимые элементы. [Точная] верхняя/нижняя грань, верхний/нижний конус подмножества. Вполне упорядоченное множество. Примеры в т. графов, групп, колец. Структура булеана P(S), частичное упорядоченого включением подмножеств X в S. Дистрибутивность U, ∩; ноль Ø, единица S, дополнение X*=S\X. Связь булевых алгебр и булевых колец. Лексикографический порядок на декартовом произведении линейно упорядоченных множеств. Вполне упорядоченное множество. Аксиома выбора и теорема Цермело. [Транс]финитная индукция.	Знание понятий, определений, описаний, формулировок. Алгебраические отношения между множествами, [ор]графы, отображения, свойства. Алгебраические системы, одно / многосортные, модели и алгебры. Знания на уровне доказательств и выводов. Теорема о факторизации множества. Умения в решении задач. Проверять характеристические свойства бинарных отношений и распознавать их тип. Строить диаграмму Хассе конечного частично упорядоченного множества (ЧУМ). Вычислять минимумы, максимумы, грани подмножества в ЧУМ. Выполнять лексикографическую сортировку словаря. Проводить индуктивные доказательства.
2.2.  Полугруппы, моноиды, группы. Свободные моноиды и конечные автоматы. Односортные алгебраические системы с одной бинарной операцией: группоид, полугруппа, моноид, группа (аддитивные / мультипликативные; абелевы / некоммутативные). Конечный инициальный автомат как фактор свободного моноида над конечным алфавитом по отношению эквивалентности, определяющему автоматные состояния (события). Примеры	Знание понятий, определений, описаний, формулировок. Алгебраические системы, одно / многосортные, модели и алгебры. Морфизм. Фактор. Знания на уровне доказательств и выводов. Умения в решении задач. Применять алгоритм быстрого возведения в натуральную степень элемента моноида.
2.3.  Основы теории групп. Теорема о единственности нейтрального элемента и обратного элемента. Классы смежности по подгруппе, односторонние факторы. Теорема Лагранжа. Подгруппы, порожденные подмножеством группы. Циклическая подгруппа Cn =  g  g^n = e  < G группы G. Теорема о порядке элемента конечной группы. Группы подстановок An  Sn. Композиция подстановок (в левой или правой экспоненциальной записи операторов), обращение, чётность, цикловое разложение подстановки. Нормальная подгруппа. Теорема о трансформации. Нормальная подгруппа = подгруппа, стабильная относительно всех трансформаций. Факторгруппа G/H группы G по нормальной подгруппе H  G. Примеры нормальных подгрупп и факторгрупп по ним. Теорема (1-я) о ядре и образе гомоморфизма групп. 2-ая теорема о гомоморфизмах групп: о факторе подгруппы по пересечению с нормальным делителем (формулировка): 3-ая теорема: о сокращении на нормальный делитель (формулировка). Центр C(G) группы G. Группа внутренних автоморфизмов Int(G)  G/C(G) группы. Коммутант [G,G] =  {[g, h] = g^-1h^-1 gh | g, h  G}   G группы G – её нормальная подгруппа. Фактор G/[G,G] по коммутанту – максимальная коммутативная факторгруппа группы G. Группа G абелева <=> [G,G] = {e}.	Знание понятий, определений, описаний, формулировок. Подгруппы [нормальные], фактор. Теоремы: Лагранжа, 1, 2, 3-я о гомоморфизмах. Знания на уровне доказательств и выводов. Теоремы: Лагранжа, 1-я о гомоморфизмах. Умения в решении задач. Вычислять композицию и обращение подстановок, сумму и произведение классов вычетов, индекс подгруппы и её классы смежности. Решать уравнение a*x = b в группе.
2.4.  Применения теории групп в кодировании с контролем ошибок и криптографии. Шифр как параметризованное ключами подмножество группы подстановок кодового пространства. Итерационный шифр – НЕ полугруппа! Реализация перестановки с помощью подстановки индексов символа Кронекера, задающего единицы мономиальной матрицы перестановки. F2-линейность оператора перестановки, P-блоков Data Encryption Standard, F2^8-линейность операции MixColumns в Advanced Encryption Standard. Передача сообщений с коррекцией малых ошибок: Информационный и кодовый векторы. Классы ошибок как классы смежности по группе линейного кода в (Fq)^n. Расстояние Хемминга. Лидеры классов. Минимальное расстояние d^* и корректирующая способность t = (d^*-1)/2 кода. Дуальный код, порождающая G и проверочная H матрицы кода, GH^T = . Линейная независимость любых d^*-1 строк транспонированной проверочной матрицы H^T. Синдром и коррекция малой ошибки с помощью таблицы синдромов t-разрядных ошибок.	Знание понятий, определений, описаний, формулировок. Знания на уровне доказательств и выводов. Умения в решении задач. Вычислять синдром ошибки и корректировать её в линейном циклическом коде на основе поля Галуа.
2.5.  Основы теории полу/колец, полей. Классификация полуколец: Идемпотентные полукольца; регулярные (полу)кольца без/с 1, не/коммутативные, с (нетривиальными) делителями нуля/целостные, факториальные/дедекиндовы, целостные кольца главных идеалов (ц.к.г.и.), евклидовы кольца, поля. Множество простых элементов коммутативного кольца. Классы ассоциированных элементов, фактор кольца по отношению ассоциированности – фактор его мультипликативного моноида по мультипликативной группе. Основная теорема арифметики коммутативного факториального кольца: Теорема о связи отношений делимости элементов и «делимости» (включения) идеалов в целостных кольцах главных идеалов (ц.к.г.и. факториальны).	Знание понятий, определений, описаний, формулировок. Полукольца, кольца, тела, поля. Идеалы и факторкольца. Классификация полуколец. Теоремы о разложении. Знания на уровне доказательств и выводов. Умения в решении задач.
2.6.  Начало теории колец классов вычетов. Подкольца. R-модуль над кольцом R. Идеал - аддитивный R-модуль. Факторкольцо. Кольцо Zn классов вычетов – факторкольцо Zn = Z/nZ целых чисел Z по идеалу nZ кратных модуля редукции n. Мультипликативная группа U(Zn)= Zn^* кольца Zn = Z/nZ классов вычетов. Функция Эйлера . Расширенный алгоритм Евклида. Обращение классов вычетов. Простые поля Fp =. Zp . Теорема Эйлера. Сложность факторизации n и вычисления (n). Идея криптосистемы RSA с открытым ключом. Структурная теорема о кольце классов вычетов Zn и его мультипликативной группе U(Zn). Криптосистема RSA. Мультипликативность функции Эйлера . Функция Кармайкла . Цикличность мультипликативной группы U(Zp^d). Первообразный корень g. Мультипликативный модуль U(Zp^d) над Z/(p^d)Z. Экспонента g^(), дискретный logg(). Быстрое MSDF|LSDF-вычисление экспоненты. Сложность дискретного логарифмирования.	Знание понятий, определений, описаний, формулировок. Кольца классов вычетов, их мультипликативные группы. Теорема Эйлера. Алгоритмы обращения вычетов, возведения в степень. Дискретный логарифм, сложность. Знания на уровне доказательств и выводов. Теорема Эйлера. Расширенный алгоритм Евклида. Быстрая экспонента в моноиде. Умения в решении задач.
2.7.  Структурная теорема о кольцах классов вычетов. Извлечение квадратного корня. Извлечение квадратного корня в конечном поле (случай мультипликативной группы порядка 4m+3). Извлечение квадратного корня в кольце классов вычетов Zn при известном разложении модуля на простые множители (без квадратов). Квадратичная подпись Rabin’а.	Знание понятий, определений, описаний, формулировок. Структурная теорема о кольцах классов вычетов, извлечение квадратного корня в них. Знания на уровне доказательств и выводов. Умения в решении задач.
2.8.  Кольца многочленов. Поля Галуа. Тривиальность идеалов ({0}, F) поля F. Теорема о характеристике поля. Теорема о факторе по max идеалу. Поле Галуа GF(p^d) как фактор евклидова кольца многочленов Fp[z] по идеалу простого многочлена P(z) степени d. Цикличность групп U(GF(p^d)) = <g|g^q^-1=1>, q=p^d. Первообразный корень g. Вычисление P(z), аннулирующего первообразный корень g: разложение z^q^-1-1 над Q в произведение циклических многочленов ; разложение q – 1(z) над Fp на простые P(z), аннулирующие первообразные корни поля GF(p^d). Группа автоморфизмов алгебраической системы. Автоморфизм Фробениуса. Группа Галуа G(FpFq). Теорема Галуа (формулировка).	Знание понятий, определений, описаний, формулировок. Кольца многочленов. Поля Галуа и вычисления в них. Знания на уровне доказательств и выводов. Умения в решении задач.
2.9.  Применения колец и полей в криптографии и кодировании с контролем ошибок. Криптосистема RSA. Криптосхема Diffie-Hellman & El Gamal. Квадратичная подпись Rabin’а. Конечные поле F2^8 и факторкольцо F2^8[x]/(x^4-1) в Advanced Encryption Standard. Линейные циклические коды на основе полей Галуа. Теорема о циклическом подмножестве (n,k)-кодов Хемминга. Построение их систематического или циклического представлений с помощью степеней первообразного корня ж  U(GF(q^m)) = <g|g^Q^-1=1>, Q=q^m, или корня =g^q^-1 порядка n=(Q-1)/(q-1). Циклические многочлены Q – 1(z) или n(z), вычисление порождающего код минимального аннулятора P(z) корня g или . Единственность расширения Галуа Fp = GF(p)  GF(p^d) = Fq, q=p^d как поля разложения многочлена z^q^-1 - 1(или z^q – z) в алгебраическом замыкании поля Fp. Алгебра FpFq.	Знание понятий, определений, описаний, формулировок. Знания на уровне доказательств и выводов. Умения в решении задач.
3.  Основы теории графов.
3.1.  Основные понятия теории графов. Пути, циклы, связность, [остовные] деревья. Алгоритмы обхода дерева (сначала) в глубину / в ширину. Реализация на основе очереди / стека.	Знание понятий, определений, описаний, формулировок. Пути, циклы, связность, [остовные] деревья. Знания на уровне доказательств и выводов. Умения в решении задач. Алгоритмы обхода дерева (сначала) в глубину / в ширину. Реализация на основе очереди / стека.
3.2.  Симметричное рефлексивно-транзитивное, замыкания бинарного отношения. Компоненты связности. Рефлексивное, симметричное, транзитивное замыкания бинарных отношений. Алгоритм Уоршалла. Вычисление компонент связности [ор]графа.	Знание понятий, определений, описаний, формулировок. Рефлексивное, симметричное, транзитивное замыкания бинарных отношений. Алгоритм Уоршалла. Знания на уровне доказательств и выводов. Умения в решении задач. Вычисление компонент связности графа.
3.3.  Выделение (минимального) остовного дерева и поиск кратчайшего пути. [Ор][мульти]графы со взвешенными дугами / ребрами. Алгоритмы Краскала, Прима выделения минимального остовного дерева. Алгоритм Дийкстры вычисления кратчайшего пути / дерева кратчайших путей. Реализация на основе очереди с приоритетами. Применения в связи и схемотехнике (топологический анализ электрической цепи в методе контурных токов, маршрутизация в сетях связи).	Знание понятий, определений, описаний, формулировок. [Ор][мульти]графы со взвешенными дугами / ребрами. Алгоритмы Краскала, Прима выделения минимального остовного дерева. Алгоритм Дийкстры вычисления кратчайшего пути / дерева кратчайших путей. Знания на уровне доказательств и выводов. Реализация на основе очереди с приоритетами. Умения в решении задач. Применения в связи и схемотехнике (топологический анализ электрической цепи в методе контурных токов, маршрутизация в сетях связи).
4.  Элементы комбинаторики.
4.1.  Комбинаторные схемы. Мультимножества. Разбиения. Полиномиальные коэффициенты, числа Белла, Стирлинга. Комбинаторные конфигурации, Размещения, перестановки, сочетания. Полиномиальные коэффициенты. Схемы урн. Латинские квадраты. Мультимножества: базис и кратности, первичная и вторичная спецификации, операции. [Не]упорядоченные разбиения. Беллиан. Числа Белла, Стирлинга. Факториальные многочлены и конечные разности.	Знание понятий, определений, описаний, формулировок. Знания на уровне доказательств и выводов. Умения в решении задач.
4.2.  Разбиения чисел. Вложимость, ранговые критерии. [Не]упорядоченные суммы и разбиения/композиции натуральных чисел. Диаграммы Ферре. Ранг. Понятие и ранговые критерии волжимости разбиений. Алгоритм “first-fit” «упаковки в ящики» (случай вложимых разбиений) при распределении задач в памяти ЭВМ.	Знание понятий, определений, описаний, формулировок. Знания на уровне доказательств и выводов. Умения в решении задач.
5.  Основы теории алгоритмов и автоматов.
5.1.  Конечные автоматы и регулярные языки. Алфавит, слово,язык. Порождающие грамматики. Классификация грамматик и языков. Регулярные языки и регулярные выражения. Конечные автоматы. Теорема Клини. Детерминизация и минимизация конечных автоматов. Конечные автоматы с выходом. Структурный синтез. Морфизмы и конечные подстановки. Машины Тьюринга.	Знание понятий, определений, описаний, формулировок. Алфавит, слово,язык. Порождающие грамматики. Классификация грамматик и языков. Регулярные языки и регулярные выражения. Конечные автоматы. Теорема Клини. Знания на уровне доказательств и выводов. Умения в решении задач. Детерминизация и минимизация конечных автоматов, структурный синтез.
5.2.  Контекстно-свободные языки и МП-автоматы (Магазинные с Памятью). КС-грамматики. Деревья вывода. Однозначность. Приведённая форма. Магазинные автоматы. Лемма о разрастании и алгебраические свойства КС-языков. Методы синтаксического и семантического анализа КС-языков. Нисходящий синтаксический анализ (сильной) LL(k)-грамматики. Восходящий анализ LR(k)-грамматики. Детерминированные Магазинные автоматы с Памятью. КС-языки и решения систем алгебраических уравнений над полукольцом L(A) всех языков над алфавитом A.	Знание понятий, определений, описаний, формулировок. КС-грамматики. Деревья вывода. Однозначность. Приведённая форма. Магазинные автоматы. Лемма о разрастании и алгебраические свойства КС-языков. Методы синтаксического и семантического анализа КС-языков. Знания на уровне доказательств и выводов. Умения в решении задач. Нисходящий синтаксический анализ (сильной) LL(k)-грамматики. Восходящий анализ LR(k)-грамматики. Решения систем алгебраических уравнений над полукольцом.
5.3.  Основные понятия теории алгоритмов и вычислительной сложности. Детерминированная и вероятностная машины Тьюринга. Временная и объёмная вычислительная сложность. Полиномиальная и экспоненциальная временная сложность. Классы сложности P, NP. Сложность алгоритмов Краскала, Прима. Дийкстры. Сложность факторизации n и вычисления (n). Сложность дискретного логарифмирования.	Знание понятий, определений, описаний, формулировок. Детерминированная и вероятностная машины Тьюринга. Временная и объёмная вычислительная сложность. Полиномиальная и экспоненциальная временная сложность. Классы сложности P, NP. Умения в решении задач. Учитывать сложность алгоритмов Краскала, Прима, Дийкстры, факторизации n и вычисления (n), дискретного логарифмирования.