Тематический план СтОГ
-
Рекурсия
- Подсчет значения арифметического выражения методом рекурсивного спуска
- Задача о Ханойских башнях
-
Графы, поиск в глубину и ширину
- Графы
- Представление графов в памяти компьютера
- Матрица смежности
- Списки смежности
- Поиск в ширину
- Поиск в глубину
- Рекурсивная и нерекурсивная реализация
- Проверка графа на ацикличность и нахождение цикла
- Топологическая сортировка
-
Нахождение кратчайших путей в взвешенном графе
- Алгоритм Дейкстры
- Алгоритм Флойда
- Нахождение цикла отрицательного веса алгоритмом Флойда
-
Геометрия.
- Векторы и координаты
- Сложение векторов, умножение вектора на число, нормирование вектора, коллинеарные векторы
- Построение ортогональных векторов
- Скалярное произведение векторов
- Свойства скалярного произведения
- Векторное произведение векторов
- Ориентированная площадь треугольника
- Свойства векторного произведения
- Принадлежность точки прямой, лучу, отрезку
- Расстояние от точки до прямой, луча, отрезка
- Определение взаимного расположения двух отрезков
- Нахождение точки пересечения двух прямых
- Уравнение прямой, проходящей через две различные точки, заданные своими координатами
- Связь координат точек с коэффициентами A, B и C. Нормаль к прямой
- Уравнение прямой, заданной одной из ее точек и вектором нормали к ней
- Уравнение прямой, перпендикулярной данной и проходящей через заданную точку
- Уравнение биссектрисы угла
- Уравнение прямой, параллельной данной и находящейся на заданном расстоянии от нее
- Уравнение окружности
- Алгоритм построения касательной к окружности (нахождение точек касания)
- Нахождение точек пересечения окружности и прямой
-
Динамическое программирование.
- Правильные скобочные последовательности
- Числа Каталана
- Построение наибольшей возрастающей подпоследовательности за время O(n2)
- Задача о рюкзаке
- Сравнение динамического программирования с рекурсией
-
Комбинаторика.
- Перестановки
- Рекурсивный и нерекурсивный алгоритм генерации перестановок в лексикографическом порядке
- Определение перестановки по номеру и номера по перестановке
- Генерация всех слов заданной длины в конечном алфавите
- Рекурсивная и нерекурсивная реализации
- Генерация всех подмножеств мощности k в множестве из n элементов
- Рекурсивная и нерекурсивная реализации