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

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

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

 

 

ЛИТЕРАТУРА

  1. Романовский И.В. Дискретный анализ. СПб. 2003.
  2. Новиков Ф.А. Дискретная математика для программистов. - СПб.2001.
  3. Оре О. Теория графов. - М. 1980.
  4. Кнут Д. Искусство программирования, тт 1-3. М. 2000..
  5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир. 1979. 534 с.