Вопросы к экзамену по курсу доц. Н. С. Григорьевой

"Основы дискретной математики"

  1. Определения теории множеств. Прямое произведение, разбиение множеств.
  2. Логические операции. Их свойства.
  3. Вектора из нулей и единиц.
  4. Алгоритм перебора 0-1 векторов. Коды Грея.
  5. Перебор элементов прямого произведения множеств.
  6. Размещения, сочетания, перестановки без повторений.
  7. Размещения, сочетания, перестановки с повторениями.
  8. Алгоритм перебора перестановок. Нумерация перестановок.
  9. Задача о минимуме скалярного произведения.
  10. Задача о максимальной возрастающей подпоследовательности.
  11. Перебор сочетаний. Нумерация сочетаний.
  12. Бином Ньютона и его комбинаторное использование.
  13. Основные определения элементарной теории вероятностей.
  14. Условные вероятности и формула Байеса.
  15. Случайные величины. Математическое ожидание и дисперсия.
  16. Случайные числа.
  17. Двоичный поиск и неравенство Крафта.
  18. Операции над строками переменной длины.
  19. Поиск образца в строке.
  20. Задача о максимальном совпадении двух строк.
  21. Код Шеннона-Фано.
  22. Алгоритм Хаффмена.
  23. Сжатие информации по методу Зива-Лемпеля.
  24. Избыточное кодирование. Помехоустойчивость.
  25. Шифрование с открытым ключом.
  26. Сортировки. (5 методов)
  27. Информационный поиск и организация информации.
  28. АВЛ деревья.
  29. Предикаты и отношения.
  30. Отношения в базах данных.
  31. Основные определения теории графов.
  32. Построение транзитивного замыкания.
  33. Связность. Компоненты связности и сильной связности.
  34. Алгоритм поиска контура и построение диаграммы порядка.
  35. Деревья.
  36. Теорема о шести эквивалентных определениях дерева.
  37. Задача о кратчайшем остовном дереве. Алгоритм Прима. Алгоритм Краскала.
  38. Задача о кратчайшем пути. Алгоритм Дейкстры. Алгоритм Левита.
  39. Задача о кратчайшем дереве путей.
  40. Сетевой график и критические пути. Нахождение резервов работ.
  41. Задача о максимальном паросочетании в графе.
  42. Теорема Кенига.
  43. Задача о назначениях. Венгерский метод.
  44. Задача коммивояжера. Метод ветвей и границ.
  45. Приближенные методы решения задачи коммивояжера.
  46. Метод динамического программирования.

 

 

ЛИТЕРАТУРА

  1. Романовский И.В. Дискретный анализ. СПб. 2003.
  2. Новиков Ф.А. Дискретная математика для программистов. - СПб.2001.
  3. Оре О. Теория графов. - М. 1980.
  4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир. 1979. 534 с.
  5. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука. 1990. 384 с.
  6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. -М.2002.960с.
  7. Липский В. Комбинаторика для программистов. Мир,1988.
  8. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир.1978.