Занятие 1. Анализ алгоритмов. Числовые алгоритмы. Рекурсия
- Введение в анализ сложности алгоритмов.
- Алгоритм вычисление факториала и его анализ.
- Понятие рекурсии. Анализ рекурсивных функций.
- Практика
Занятие 2. Элементарные структуры данных
- Массив, стек, очередь
- Динамические структуры данных (списки, деревья)
- Умножение матриц
- Сравнение строк
- Анализ сложности вычислений
- Практика
Занятие 3. Сортировки и алгоритмы поиска
- Бинарный поиск.
- Сортировка вставками
- Сортировка выбором
- Сортировка слиянием
- Быстрая сортировка (возможные случаи)
- Алгоритмы поиска в деревьях
- Поиск подстрок
- Анализ сложности вычислений
- Практика
Занятие 4. Динамическое программирование
- Кэширование вычислений.
- Замена рекурсивных функций и увеличение производительности.
- Анализ сложности вычислений
- Практика
Занятие 5. Порядковые статистики. Кучи
- Вычисление k-порядковой статистики. Рэндомизированный случай.
- Очереди с приоритетами (кучи). Двоичная куча.
- Сортировка кучей (heap sort).
- Анализ сложности вычислений
- Практика
Занятие 6. Хэширование. Система непересекающихся множеств
- Хэширование. Типы хэш-таблиц. Хэш-функция.
- Система непересекающихся множеств. Разновидности.
- Анализ сложности вычислений
- Практика
Занятие 7. Элементарная теория графов
- Представление графов. Анализ каждого представления.
- Обход графа. Поиск в глубину. Поиск в ширину.
- Поиск кратчайших путей на графе. Алгоритм Дейкстры. Алгоритм Флойда-Уоршелла
- Практика
Занятие 8. Применение численных методов в решении практических задач
- Подход к вычислению бесконечных сумм на примере математической библиотеки.
- Реализация алгоритмов вычисления интегралов.
- Интерполяционные многочлена на примере построения графиков
- Практика