Экзаменационные вопросы по курсу «Дискретная математика»
Направление «Программная инженерия»
Программа к экзамену
Множества и основные операции над ними. Диаграммы Эйлера-Венна. Свойства теоретико-множественных операций. Декартово произведение множеств. Примеры. Бинарные отношения и их свойства. Отношение эквивалентности. Отображения, виды отображений. Мощность множества. Примеры. Упорядоченные и неупорядоченные множества. Пузырьковая сортировка и сортировка вставками. Алгоритм Флойда. Принципы суммы и произведения. Перестановки. Размещения без повторений и с повторениями. Сочетания без повторений и с повторениями. Бином Ньютона и треугольник Паскаля. Полиномиальные коэффициенты. Покрытия множества. Формула включений и исключений. Разбиения множества. Числа Стирлинга и Белла. Графы. Смежность и инцидентность. Способы представления графа. Маршруты в графах. Связность, достижимость и расстояния. Деревья. Остовные деревья. Алгоритмы Прима и Крускала. Эйлеровы и гамильтоновы графы. Поиск в глубину. Модификация алгоритма для поиска компонент связности. Поиск в ширину. Модификация алгоритма для поиска компонент связности. Транспортные сети. Алгоритм Дейкстры. Задача о максимальном потоке в сети. Алгоритм Форда-Фалкерсона. Понятие группы и подгруппы. Абелева и циклическая группы. Примеры. Кольца и поля. Примеры. Сравнения в кольце целых чисел. Кольца и поля вычетов. Теорема Безу. Схема Горнера. НОД. Алгоритм Евклида (на примере чисел и многочленов). Разложение многочлена на множители. Схема Горнера. Виды кодирования. Разделимые коды. Алгоритм Маркова. Свойство префикса. Неравенство Крафта-Макмиллана. Построение кода с заданными длинами кодовых слов Постановка задачи об оптимальном кодировании. Метод Шеннона-Фано. Метод Хаффмена построения оптимального кода. Ошибки при передаче информации. Помехоустойчивые коды. Расстояние и код Хемминга. Шифры. Понятие о шифровании с открытым ключом. Понятие о кодировании с целью архивирования.