Бесплатная часть
(вводный модуль 7 часов)
Понятие алгоритма. Скользящее среднее. Метод двух указателей.
Введение в алгоритмы
Понятие сложности алгоритма. O-нотация. Оценка времени исполнения программы.
Основные структуры данных
Массив, связный список, стек, очередь. Сложность операций вставки, поиска и удаления. Представление данных в памяти. Пространственная сложность алгоритма.
Рекурсия и сортировки
Рекурсия
Понятие рекурсии. Принцип «разделяй и властвуй». Бинарный поиск.
Сортировки
Квадратичные сортировки. Сортировка слиянием. Быстрая сортировка. Линейная сортировка подсчётом.
Хеш-функции и хеш-таблицы
Абстракция отображения. Понятие и свойства хеш-функции, примеры. Структура данных хеш-таблица. Коллизии и способы их разрешения.
Деревья
Структура данных дерево. Сбалансированные деревья поиска. Структура данных куча. Пирамидальная сортировка.
Графы
Определение графа, способы представления в памяти. Обход графа в глубину и в ширину. Компоненты связности. Алгоритмы поиска кратчайшего пути. Минимальное остовное дерево.
Жадные алгоритмы и динамическое программирование
Динамическое программирование
Определение, одномерные и двумерные задачи. Динамическое программирование по подотрезкам. Динамическое программирование по подмножествам.
Жадные алгоритмы
Понятие жадного алгоритма, область применения. Примеры, доказательство корректности алгоритма.
Пробное алгоритмическое собеседование
Алгоритмическое интервью один-на-один с наставником, максимально приближённое к настоящему. По итогам наставник даст обратную связь.
Алгоритмы на строках
Префикс-функция. Подстроки, префиксы и суффиксы. Поиск шаблона в строке. Наивный алгоритм. Структура данных бор.