Geum.ru

Вопросы к экзамену «дискретная математика» (пм-91)

Вид материалаВопросы к экзамену
Подобный материал:

Вопросы к экзамену «ДИСКРЕТНАЯ МАТЕМАТИКА» (ПМ-91)




ТЕОРИЯ МНОЖЕСТВ

  1. Понятие множества. Способы задания множеств. Пустое множество. Подмножество. Равные множества. Булеан. Число элементов булеана конечного множества.
  2. Универсальное множество. Операции над множествами. Теорема о взаимном расположении двух множеств.
  3. Свойства операций над множествами.
  4. Кортеж, его длина. Декартово произведение двух множеств. Бинарное отношение. Область определения и область значений отношения. Матрица отношения. Операции пересечения, объединения и дополнения над отношениями.
  5. Обратное отношение. Тождественное отношение. Произведение отношений. Степень отношения. Свойства рефлексивности, иррефлексивности, симметричности, антисимметричности, транзитивности. Замыкания (рефлексивное, симметричное, транзитивное).
  6. Отношение эквивалентности. Классы эквивалентности, их свойства. Фактор-множество данного множества по отношению эквивалентности. Разбиение, теорема о разбиении.
  7. Частичный порядок. Частично упорядоченное множество и линейно упорядоченное множество. Диаграммы Хассе. Наибольший (наименьший) элемент частично упорядоченного множества. Максимальный (минимальный) элемент частично упорядоченного множества.
  8. Функция. Образ, прообраз. Инъекция, сюръекция, биекция. Сложная функция. Обратная и обратимая функция. Теорема об обратной функции.
  9. Равномощные множества. Мощность. Конечные и бесконечные множества. Счетные множества. Теорема о конечном множестве.



ГРАФЫ

  1. Граф, орграф, нижний граф, инцидентность, смежность, петля, кратные ребра, псевдограф, мультиграф, степень вершины, полустепень захода, полустепень исхода, изолированная вершина, висячая вершина, простой граф, полный граф. Теорема Эйлера о числе ребер.
  2. Помеченный граф, взвешенный граф, однородный граф, двудольный граф, подграф, собственный подграф, остовной граф. Изоморфизм графов.
  3. Дополнение графа, объединение и пересечение графов, удаление вершины и удаление ребра. Представления графов.
  4. Маршрут, замкнутый маршрут, цепь, простая цепь, цикл, простой цикл. Ацикличный граф. Длина маршрута. Расстояние между вершинами. Диаметр графа.
  5. Связность вершин. Отношение связности. Компоненты связности. Связный граф. Слабая связность, сильная связность. Дерево, лес.
  6. Алгоритмы поиска дерева покрытия в глубину и в ширину.
  7. Алгоритм Прима и алгоритм Краскала нахождения дерева покрытия минимального веса.
  8. Эйлеровый и Гамильтоновый графы. Критерий Эйлера. Достаточный признак Гамильтонова графа.
  9. Алгоритм ближайшего соседа.
  10. Алгоритм Дейкстры поиска наикратчайшего пути между двумя заданными вершинами.
  11. Упорядочивание списков: ПС (пузырьковая сортировка), БС (быстрая сортировка), СС (сортировка слиянием).
  12. Алгоритм склеивания дуг.
  13. Сеть. Алгоритм поиска критического пути, его цены.
  14. Поток, цена потока, максимальный поток. Срез, мощность среза, минимальный срез. Теорема Форда – Фалкерсона, алгоритм Форда – Фалкерсона.



КОДИРОВАНИЕ

  1. Задача кодирования. Алфавитное кодирование. Префиксное кодирование. Алгоритм Фано.
  2. Оптимальное кодирование. Теорема Хаффмана. Алгоритм Хаффмана.
  3. Помехоустойчивое кодирование. Кодирование и декодирование Хемминга.



КОМБИНАТОРИКА

  1. Основные формулы комбинаторики.



ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

  1. Задачи линейного программирования (общего вида, стандартного, основного, канонического). Область допустимых решений. Оптимальное решение. Графический метод решения ЗЛП.
  2. Симплексный метод решения ЗЛП. Метод искусственного базиса.
  3. Задачи целочисленного программирования. Графический метод решения ЗЦП.
  4. Метод Гомори.