Вопросы к экзамену по курсу доц. Н. С. Григорьевой
"Основы дискретной математики"
Определения теории множеств. Прямое произведение, разбиение множеств.
Логические операции. Их свойства.
Вектора из нулей и единиц.
Алгоритм перебора 0-1 векторов. Коды Грея.
Перебор элементов прямого произведения множеств.
Размещения, сочетания, перестановки без повторений.
Размещения, сочетания, перестановки с повторениями.
Алгоритм перебора перестановок. Нумерация перестановок.
Задача о минимуме скалярного произведения.
Задача о максимальной возрастающей подпоследовательности.
Перебор сочетаний. Нумерация сочетаний.
Бином Ньютона и его комбинаторное использование.
Основные определения элементарной теории вероятностей.
Условные вероятности и формула Байеса.
Случайные величины. Математическое ожидание и дисперсия.
Случайные числа.
Двоичный поиск и неравенство Крафта.
Операции над строками переменной длины.
Поиск образца в строке.
Задача о максимальном совпадении двух строк.
Код Шеннона-Фано.
Алгоритм Хаффмена.
Сжатие информации по методу Зива-Лемпеля.
Избыточное кодирование. Помехоустойчивость.
Шифрование с открытым ключом.
Сортировки. (5 методов)
Информационный поиск и организация информации.
АВЛ деревья.
Предикаты и отношения.
Отношения в базах данных.
Основные определения теории графов.
Построение транзитивного замыкания.
Связность. Компоненты связности и сильной связности.
Алгоритм поиска контура и построение диаграммы порядка.
Деревья.
Теорема о шести эквивалентных определениях дерева.
Задача о кратчайшем остовном дереве. Алгоритм Прима. Алгоритм Краскала.
Задача о кратчайшем пути. Алгоритм Дейкстры. Алгоритм Левита.
Задача о кратчайшем дереве путей.
Сетевой график и критические пути. Нахождение резервов работ.
Задача о максимальном паросочетании в графе.
Теорема Кенига.
Задача о назначениях. Венгерский метод.
Задача коммивояжера. Метод ветвей и границ.
Приближенные методы решения задачи коммивояжера.
Метод динамического программирования.
ЛИТЕРАТУРА
Романовский И.В. Дискретный анализ. СПб. 2003.
Новиков Ф.А. Дискретная математика для программистов. - СПб.2001.
Оре О. Теория графов. - М. 1980.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир. 1979. 534 с.
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука. 1990. 384 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. -М.2002.960с.
Липский В. Комбинаторика для программистов. Мир,1988.
Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир.1978.