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

1. Асимптотический анализ

  1. $O, \Omega, \Theta, o, \omega$: определения и базовые свойства.
  2. Сравнение скорости роста полилогарифмических, полиномиальных и экспоненциальных функций.
  3. Основная теорема о рекуррентных соотношениях. Доказательство оценки $O$ в общем случае, оценки $\Theta$ в случае $n = b^{k}$.

2. Элементарная арифметика

  1. Алгоритм сложения за $O(n)$. Алгоритмы умножения за $O\!\left(n^{2}\right)$.
  2. Алгоритмы деления за $O\!\left(n^{2}\right)$.
  3. Алгоритм Карацубы.

3. Базовые структуры данных и поиск

  1. Массив, динамический массив, связный список, стек, очередь, дек.
  2. Двоичный поиск, поиск левого (правого) вхождения.
  3. Двоичный поиск по функции, двоичный поиск по функции с вещественным аргументом.
  4. Метод двух указателей на примере задачи о поиске в массиве неотрицательных чисел максимального по длине подотрезка, сумма на котором не превосходит $M$.

4. Сортировки

  1. Сортировка выбором, сортировка вставками. Оценка времени работы сортировки вставками через число инверсий в массиве. Стабильность.
  2. Сортировка слиянием.
  3. Быстрая сортировка. Корректность работы функции partition.
  4. Быстрая сортировка. Оценка времени работы.
  5. Поиск $k$-й порядковой статистики. Оценка времени работы.
  6. Оценка снизу на время работы сортировки сравнениями.
  7. Сортировка подсчётом. Стабильная версия.
  8. Поразрядная сортировка.

5. Двоичная куча

  1. Двоичная куча. Операции getMin, siftUp, siftDown, insert и extractMin.
  2. Двоичная куча. Построение за линейное время.
  3. Двоичная куча. Heapsort, очередь с приоритетами, удаление или изменение произвольного элемента.

6. Хеш-таблицы

  1. Хеш-таблица. Метод цепочек.
  2. Хеш-таблица. Открытая адресация, способы выбора последовательности проб, удаление элементов.
  3. Сортировка Киркпатрика–Рейша.
  4. Универсальное хеширование. Оценка времени работы операций на хеш-таблице при использовании техники универсального хеширования.
  5. Универсальное хеширование. Построение универсального семейства хеш-функций.
  6. Совершенное хеширование. Оценка вероятности отсутствия коллизий при хранении $n$ ключей в хеш-таблице размера $n^{2}$ с использованием техники универсального хеширования.
  7. Совершенное хеширование. Оценка суммарного размера внутренних хеш-таблиц.

7. Теоретико-числовые алгоритмы и криптография

  1. Сложение, умножение и возведение в степень по модулю $N$.
  2. Алгоритм Евклида. Оценки времени работы $O(n \cdot M(n))$ и $O\!\left(n^{2}\right)$.
  3. Расширенный алгоритм Евклида. Доказательство корректности. Нахождение обратного по модулю $N$.
  4. Расширенный алгоритм Евклида. Оценки времени работы $O(n \cdot M(n))$ и $O\!\left(n^{2}\right)$.
  5. Решето Эратосфена.
  6. Решето с линейным временем работы.
  7. Тест Ферма. Оценка вероятности ошибки для $n$, не являющихся числами Кармайкла.
  8. Тест Миллера–Рабина. Оценка вероятности ошибки.
  9. $\rho$-алгоритм Полларда. Описание, эвристическая оценка времени работы.
  10. $\rho$-алгоритм Полларда. Оценка вероятности того, что для случайных $f\colon \mathbb{Z}_{p} \to \mathbb{Z}_{p}$, $x_{0} \in \mathbb{Z}_{p}$ элементы последовательности $x_{i} = f\!\left(x_{i-1}\right)$ с номерами не более $\sqrt{2\lambda p}$ попарно различны.
  11. Схема RSA.
  12. Цифровая подпись. Цифровой сертификат.
  13. Протокол Диффи–Хеллмана.
  14. Схема Эль-Гамаля.

8. Бинарные деревья и деревья поиска

  1. Бинарные деревья: определение, высота, связь между числом листьев и числом внутренних вершин в полном бинарном дереве.
  2. Обходы бинарного дерева: прямой, симметричный, обратный порядки. Итеративная реализация через стек.
  3. Обход в ширину бинарного дерева.
  4. Двоичное дерево поиска (BST): поиск, вставка, удаление. Оценка времени работы в худшем и среднем случаях.
  5. Декартово дерево (treap): определение, операции split и merge, вставка и удаление.
  6. АВЛ-деревья: определение, повороты (малый и большой), лемма о высоте. Поддержание инварианта при вставке.
  7. Красно-чёрные деревья: свойства, оценка высоты через чёрную высоту. Операции вставки (разбор случаев).
  8. Б-деревья: определение, поиск, вставка (разбиение вершин). Оценка числа операций с диском.
  9. Дерево отрезков: построение, запрос на отрезке и обновление за $O(\log n)$. Ленивые вычисления.

9. Графы

  1. DFS. Обход вершин, достижимых из данной. Поиск компонент связности.
  2. DFS. Дерево поиска в глубину в неориентированном/ориентированном графе. Времена входа и выхода. Типы рёбер.
  3. DFS. Поиск цикла в неориентированном/ориентированном графе.
  4. DFS. Топологическая сортировка.
  5. DFS. Поиск компонент сильной связности.
  6. DFS. Поиск мостов и компонент рёберной двусвязности.
  7. DFS. Поиск точек сочленения и компонент вершинной двусвязности.
  8. DFS. Решение задачи 2-SAT.
  9. BFS. Дерево кратчайших путей.
  10. $0$-$1$ BFS.
  11. $1$-$k$ BFS (две реализации).
  12. Алгоритм Дейкстры.
  13. Алгоритм A*. Доказательство корректности работы для функции, удовлетворяющей неравенству треугольника. Сравнение с алгоритмом Дейкстры с break.
  14. Алгоритм Форда–Беллмана.
  15. Алгоритм Форда–Беллмана. Поиск отрицательного цикла.
  16. Алгоритм Форда–Беллмана с очередью.
  17. Алгоритм Флойда.
  18. Поиск отрицательного цикла и проверка существования кратчайшего пути между вершинами с помощью алгоритма Флойда.

10. Жадные алгоритмы

  1. Префиксные коды, связь с двоичными деревьями. Алгоритм Хаффмана.
  2. Алгоритм Белади.
  3. Лемма о разрезе. Алгоритм Прима.
  4. Лемма о разрезе. Алгоритм Краскала.
  5. DSU. Реализация связными списками.
  6. DSU. Реализация деревьями. Ранговая эвристика.
  7. DSU. Реализация деревьями. Эвристика сжатия путей.
  8. DSU. Совместное использование эвристик.

11. Динамическое программирование

  1. ДП. Наибольшая общая подпоследовательность.
  2. ДП. Расстояние Левенштейна.
  3. ДП. Алгоритм Хиршберга.
  4. ДП. Наибольшая возрастающая подпоследовательность. Решение за $O(n \log n)$.
  5. ДП. Задача о рюкзаке. Версии «с повторениями» и «без повторений».
  6. ДП. Произведение матриц.
  7. ДП. Независимое множество максимального веса в дереве.
  8. ДП. Задача коммивояжёра.
  9. ДП. Размер подмножества, сумма элементов подмножества, сумма по подмножествам (SOS DP).
  10. ДП. Генерация перестановки по номеру и номера по перестановке.
  11. ДП. Генерация ПСП по номеру и номера по ПСП.
  12. ДП. Решение линейных рекуррентных соотношений методом возведения матрицы в степень.