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