Курс АиСД МФТИ

Конспекты по курсу «Алгоритмы и структуры данных» на Физтехе, осенний семестр 2026/27. Общее вступление и как читать сайт — на главной, Конспекты МФТИ.

Лекции

№	Лекция	Дата
01	АиСД L01 - Время работы и асимптотика	19.09.2026
02	АиСД L02 - Простейшие алгоритмы	26.09.2026
03	АиСД L03 - Решето Эратосфена и квадратичные сортировки	03.10.2026
04	АиСД L04 - Рекурсия и сортировка слиянием	10.10.2026
05	АиСД L05 - Быстрая сортировка и сортировка подсчётом	17.10.2026
06	АиСД L06 - Динамическое программирование	24.10.2026

Термины

Сложность алгоритмов

Время работы алгоритма — такты вместо секунд, RAM-модель, длина входа
Асимптотические оценки — O, Ω, Θ, шкала асимптотик, отбрасывание констант

Числа

Алгоритм Евклида — НОД вычитанием и остатком, доказательства и оценки
Решето Эратосфена — все простые до N за $O (N lo g lo g N)$

Поиск

Бинарный поиск — поиск в отсортированном массиве за $O (lo g N)$ и поиск по ответу

Сортировки

Сортировка — определение, виды порядка, время, память, устойчивость, нижняя оценка $Ω (N lo g N)$
Квадратичные сортировки — выбором, вставками, пузырьком: инварианты, сравнения, инверсии
Сортировка слиянием — Merge, деление пополам, $O (N lo g N)$ , буфер на $O (N)$
Быстрая сортировка — Partition Ломуто и Хоара, выбор опорного, $O (N lo g N)$ в среднем и $O (N^{2})$ в худшем
Сортировка подсчётом — без сравнений за $O (N + K)$ , устойчивая версия

Приёмы

Рекурсия — граничное условие, восходящая и нисходящая, глубина стека
Динамическое программирование — подзадачи считаются один раз: Фибоначчи, кузнечик, сочетания, разбиения
Жадный алгоритм — лучший выбор на каждом шаге и почему он ошибается на монетах

Общие с курсом C++

Циклы — сколько стоит цикл в тактах и почему break не всегда ускоряет
Типы с плавающей точкой — почему бинарный поиск по дробным числам останавливают числом итераций, а не eps