Дизайн и анализ алгоритмов
Описание
Темы включают сортировку; деревья поиска, кучи и хеширование; метод “разделяй и властвуй”; динамическое программирование; жадные алгоритмы; амортизированный анализ; алгоритмы на графах и поиск кратчайших путей.
Дополнительные темы могут охватывать потоки в сетях; вычислительную геометрию; алгоритмы теории чисел; вычисления с многочленами и матрицами; кэширование и параллельные вычисления.
Программа:
- Обход в ширину. Обход в глубину.
- 2-разрезы.
- Поиск кратчайших путей.
- Минимальные остовные деревья.
- Поиск подстрок.
- Суффиксные деревья.
- Суффиксные массивы.
- Длиннейшие общие подстроки. Приближённый поиск подстрок.
Предварительные требования:
- Алгоритмы и структуры данных: Базовый курс по алгоритмам