-
Предназначено обучающимся ОП "Информационная безопасность"
-
Экзаменационные вопросы
- Множества и их задания. Операции с множествами. Диаграммы Эйлера. Порождающая процедура. Примеры.
- Эквивалентные формулы в алгебре множеств. Создание различных соответствий между множествами. Определение мощности множеств. Булеан. Универсум. Покрытие и разбиение множества. Примеры.
- Соответствие и его свойства. Функции и отображения. Отношения. Бинарные отношения. Способы задания бинарных отношений. Эквивалентные отношения и отношения порядка. Транзитивные отношения. Транзитивное замыкание. Примеры.
- Элементы комбинаторики. Размещение и сочетания. Разбиение множеств. Правила сложения и умножения. Примеры.
- Булевы функции. Все логические функции двух переменных. Булева алгебра.
- Эквивалентные формулы алгебры логики.
- Разложение функций трех переменных по первой переменной. Примеры.
- Составление таблицы истинности для заданной функции, написание форм МДКФ и МККФ.
- Универсальные формы логических функций. Полином Жегалкина.
- Полные системы булевых функций. Классы Поста. Теорема Поста. Полнота функций Штрих Шеффера и стрелка Пирса.
- Составление схем функциональных элементов, состоящих из элементарного сумматора, дизъюнкций, отрицания и конъюнкций.
- Предикаты. Операции, применяемые к предикатам. Исчисление предикатов. Эквивалентные формулы логики предикатов. Сколемовская форма предикатной формулы.
- Графы. Основные понятия теории графов. Ориентированные и неориентированные графы. Важные типы графов.
- Способы задания графов. Матрица инцидентности. Матрица соседства вершин.
- Операции над графами.
- Цепи. Циклы. Связь. Пространство подграфов.
- Цикломатическое число v = p-b + k. Построение каркаса графа и базиса циклов заданного графа.
- Задача о Кенингсбергских мостах. Эйлеровы (четные) графы.
- Метрические характеристики графа. Диаметр. Радиус. Эксцентриситет. Центр графа.
- Двухполюсные сети. Потоки в сетях. Сечение. Задача о максимальном потоке.
- Алгоритмы в графах. Кратчайшие пути и цепи. Алгоритм Форда.
- Элементы теории кодирования. Алфавитное кодирование. Оптимальное кодирование. Код Фано. Равномерные коды.
- Кодовое дерево. Расчет кодового расстояния. Коды с обнаружением и исправлением ошибок. Код Хемминга.
- Логические сети. Схемы функциональных элементов для системы булевых функций.
- Конечные автоматы. Граф переходов. Таблица переходов. Примеры.
- Алгоритмы и вычислимость. Требования к алгоритмическим процедурам. Рекурсивные функции. Исходные функции. Суперпозиция. Операторы минимизации. Тезис Черча.
- Машины Тьюринга. Основные понятия. Примеры.
