Глава 1

Список вопросов к экзамену по курсу основы программирования СПбГУ, весенний семестр, 2024/25 учебный год

  1. $O, \Omega, \Theta, o, \omega$ : определения и базовые свойства.
  2. Сравнение скорости роста полилогарифмических, полиномиальных и экспоненциальных функций.
  3. Алгоритм сложения за $O(n)$. Алгоритмы умножения за $O\left(n^{2}\right)$.
  4. Алгоритмы деления за $O\left(n^{2}\right)$.
  5. Алгоритм Карацубы.
  6. Основная теорема о рекуррентных соотношениях. Доказательство оценки $O$ в общем случае, оценки $\Theta$ в случае $n=b^{k}$.
  7. Массив, динамический массив, cвязный список, стек, очередь, дек.
  8. Двоичный поиск, поиск левого (правого) вхождения.
  9. Двоичный поиск по функции, двоичный поиск по функции с вещественным аргументом.
  10. Метод двух указателей на примере задачи о поиске в массиве неотрицательных чисел максимального по длине подотрезка, сумма на котором не превосходит $M$.
  11. Сортировка выбором, сортировка вставками. Оценка времени работы сортировки вставками через число инверсий в массиве. Стабильность.
  12. Сортировка слиянием.
  13. Быстрая сортировка. Корректность работы функции partition.
  14. Быстрая сортировка. Оценка времени работы.
  15. Поиск $k$-й порядковой статистики. Оценка времени работы.
  16. Оценка снизу на время работы сортировки сравнениями.
  17. Сортировка подсчётом. Стабильная версия.
  18. Поразрядная сортировка.
  19. Двоичная куча. Операции getMin, siftUp, siftDown, insert и extractMin.
  20. Двоичная куча. Построение за линейное время.
  21. Двоичная куча. Heapsort, очередь с приоритетами, удаление или изменение произвольного элемента.
  22. Хеш-таблица. Метод цепочек.
  23. Хеш-таблица. Открытая адресация, способы выбора последовательности проб, удаление элементов.
  24. Сортировка Киркпатрика-Рейша.
  25. Универсальное хеширование. Оценка времени работы операций на хеш-таблице при использовании техники универального хеширования.
  26. Универсальное хеширование. Построение универсального семейства хеш-функций.
  27. Совершенное хеширование. Оценка вероятности отсутствия коллизий при хранении $n$ ключей в хеш-таблице размера $n^{2}$ с использованием техники универсального хеширования.
  28. Совершенное хеширование. Оценка суммарного размера внутренних хеш-таблиц.
  29. Сложение, умножение и возведение в степень по модулю $N$.
  30. Алгоритм Евклида. Оценки времени работы $O(n \cdot M(n))$ и $O\left(n^{2}\right)$.
  31. Расширенный алгоритм Евклида. Доказательство корректности. Нахождение обратного по модулю $N$.
  32. Расширенный алгоритм Евклида. Оценки времени работы $O(n \cdot M(n))$ и $O\left(n^{2}\right)$.
  33. Решето Эратосфена.
  34. Решето с линейным временем работы.
  35. Тест Ферма. Оценка вероятности ошибки для $n$, не являющихся числами Кармайкла.
  36. Тест Миллера-Рабина. Оценка вероятности ошибки.
  37. $\rho$-алгоритм Полларда. Описание, эвристическая оценка времени работы.
  38. $\rho$-алгоритм Полларда. Оценка вероятности того, что для случайных $f: \mathbb{Z}_{p} \rightarrow \mathbb{Z}_{p}, x_{0} \in \mathbb{Z}_{p}$ элементы последовательности $x_{i}=f\left(x_{i-1}\right)$ с номерами не более $\sqrt{2 \lambda p}$ попарно различны.
  39. Схема RSA.
  40. Цифровая подпись. Цифровой сертификат.
  41. Протокол Диффи-Хеллмана.
  42. Схема Эль-Гамаля.
  43. DFS. Обход вершин, достижимых из данной. Поиск компонент связности.
  44. DFS. Дерево поиска в глубину в неориентированном/ориентированном графе. Времена входа и выхода. Типы рёбер.
  45. DFS. Поиск цикла в неориентированном/ориентированном графе.
  46. DFS. Топологическая сортировка.
  47. DFS. Поиск компонент сильной связности.
  48. DFS. Поиск мостов и компонент рёберной двусвязности.
  49. DFS. Поиск точек сочленения и компонент вершинной двусвязности.
  50. DFS. Решение задачи 2-SAT.
  51. BFS. Дерево кратчайших путей.
  52. $0-1 \mathrm{BFS}$.
  53. $1-k$ BFS (две реализации).
  54. Алгоритм Дейкстры.
  55. Алгоритм А*. Доказательство корректности работы для функции, удовлетворяющей неравенству треугольника. Сравнение с алгоритмом Дейкстры с break.
  56. Алгоритм Форда-Беллмана.
  57. Алгоритм Форда-Беллмана. Поиск отрицательного цикла.
  58. Алгоритм Форда-Беллмана с очередью.
  59. Алгоритм Флойда.
  60. Поиск отрицательного цикла и проверка существования кратчайшего пути между вершинами с помощью алгоритма Флойда.
  61. Префиксные коды, связь с двоичными деревьями. Алгоритм Хаффмана.
  62. Алгоритм Белади.
  63. Лемма о разрезе. Алгоритм Прима.
  64. Лемма о разрезе. Алгоритм Краскала.
  65. DSU. Реализация связными списками.
  66. DSU. Реализация деревьями. Ранговая эвристика.
  67. DSU. Реализация деревьями. Эвристика сжатия путей.
  68. DSU. Совместное использование эвристик.
  69. ДП. Наибольшая общая подпоследовательность.
  70. ДП. Расстояние Левенштейна.
  71. ДП. Алгоритм Хиршберга.
  72. ДП. Наибольшая возрастающая подпоследовательность. Решение за $O(n \log n)$.
  73. ДП. Задача о рюкзаке. Версии “с повторениями” и “без повторений”.
  74. ДП. Произведение матриц.
  75. ДП. Независимое множество максимального веса в дереве.
  76. ДП. Задача коммивояжёра.
  77. ДП. Размер подмножеств, сумма элементов в подмножестве, сумма по подмножествам.
  78. ДП. Генерация перестановки по номеру и номера по перестановке.
  79. ДП. Генерация ПСП по номеру и номера по ПСП.