Вопросы к экзамену по курсу проф. И. В. Романовского

"ДИСКРЕТНЫЙ АНАЛИЗ" для специальностей 080801 и 080802

  1. Разбиения множества. Произведение разбиений
  2. Трактовки набора из нулей и единиц.
  3. Простейшее соединение вершин многомерного единичного куба
  4. Способы перебора 0-1 векторов
  5. Кодировки ASCII, Unicode, UTF-8
  6. Перевод информации в видимый формат
  7. Перестановки, размещения, сочетания
  8. Бином Ньютона и треугольник Паскаля
  9. Использование формулы Муавра для получения комбинаторных тождеств
  10. Задача перебора разбиений
  11. Вероятность и ее свойства
  12. Условные вероятности
  13. Формула полной вероятности и формула Байеса
  14. Случайная величина и ее функция распределения
  15. Математическое ожидание и дисперсия случайной величины
  16. Способы моделирования непрерывных распределений
  17. Моделирование дискретных распределений (метод Уолкера)
  18. Аксиоматическое определение энтропии
  19. Неравенство Крафта
  20. Алгоритм Хаффмена для построения оптимального префиксного кода
  21. Алгоритм MTF (Move To Front)
  22. Алгоритм сжатия Зива-Лемпеля
  23. Алгоритм сжатия Зива-Лемпеля-Уэлча
  24. Алгоритм сжатия Барроуза-Уилера
  25. Защита информации от сбоев. Контрольные суммы. Код Хэмминга
  26. Защита информации от несанкционированного доступа
  27. Операции над строками
  28. Лексикографическое сравнение
  29. Поиск образца в строке. Дактилоскопический метод Карпа-Рабина
  30. Поиск образца в строке. Другие методы
  31. Задача о максимальном совпадении двух строк
  32. Классификация функций от строк
  33. Сортировка вставкой
  34. Сортировка слиянием (фон Неймана)
  35. Сортировка Шелла
  36. Быстрая сортировка (два варианта)
  37. Иерархическая сортировка
  38. Поразрядная сортировка
  39. Построение суффиксного массива
  40. АВЛ-дерево
  41. В-дерево
  42. Хеширование и его использование
  43. Приоритетные очереди. Биномиальное дерево
  44. Классификация предикатов
  45. Транзитивное замыкание отношения
  46. Классы эквивалентности
  47. Основные определения теории графов
  48. Существование остовного дерева в связном графе
  49. Различные определения дерева
  50. Матрица инциденций и ее свойства
  51. Нахождение частного решения неоднородной лин. системы с матрицей инциденций
  52. Структура общего решения однородной линейной системы с матрицей инциденций
  53. Метод Прима-Ярника для поиска кратчайшего остовного дерева
  54. Метод Краскала для поиска кратчайшего остовного дерева
  55. Вычисление матрицы кратчайших расстояний
  56. Метод Дейкстры для поиска кратчайшего пути в графе
  57. Построение сетевого графика
  58. Критические пути в сетевом графике
  59. Теорема двойственности для задачи о паросочетаниях
  60. Построение максимального паросочетания
  61. Теорема Биркгофа-фон Неймана
  62. Венгерский метод для задачи о назначениях
  63. Метод ветвей и границ
  64. Приближенные методы решения экстремальных задач
  65. Конечные автоматы
  66. Марковские цепи. Матрица переходных вероятностей
  67. Марковские цепи. Эргодические классы
  68. Процессы принятия решений (динамическое программирование)

 

 

ЛИТЕРАТУРА

  1. Романовский И.В. Дискретный анализ. СПб, 2008.
  2. Берж К. Теория графов и ее применения. М., 1962.
  3. Яглом А.М. и Яглом И.М. Вероятность и информация. М., 1973.
  4. Гасфилд Д. Строки, деревья и последовательности в алгоритмах. СПб. 2003.
  5. Липский В. Комбинаторика для программистов. М., 1988.