Асимптотика (1-я пара, 2024/25 учебный год)

1. [5 минут] Разбор вступительного теста
   1. Задача a² + b² + c² + d² = N : N⁴, N², N^3/2, N
   
   
2. [15 минут] Информация о курсе
   1. Отчётность: по теории экзамен, по практике каждую неделю +1 контест, +1 порция теорзадач
   2. Как сдавать ДЗ: дедлайны жёсткие, контест в систему на c++, теорию в tex на почту
   3. Ссылки: Wiki, Telegram, материалы курса
   4. Обратите внимание на: не нужно списывать, вообще. Если у вас есть вопросы, сложности − обратитесь к преподавателям, к одногруппникам.
   5. Полезные ссылки: wiki , материалы курса алгоритмов , контакты препов (на wiki)
   
   
3. [2 минут] Учимся задавать вопросы на примерах (лектор произносит утверждение, студенты не понимают, проявляют не понимание голосом)
   1. Алгоритм Карацубы работает за 1.58ⁿ
   2. Алгоритм Карацубы умножает многочлены: делаем 3 рекурсивных запуска от кусочков длины n/2
   3. Многочлены над вещественными числам умножаются за квадрат.

1. [5 минут] Общие слова
   1. Что такое хороший алгоритм? Всегда работает, время, память, простота.
   2. Время работы, пример 1: зависит от размера входных данных; пример − поиск минимума в массиве; 4n: асимптотика, константа.
   3. 3GHz − 3 000 000 000 операций в секунду (на самом деле меньше, т.к. сложные операции). Питон ~= 10⁶, C++ ~= 10⁹.
   
   
2. [15 минут] Асимптотика: базовые обозначения, определения, свойства
   1. Время работы, пример 2: for i, for j ≤ i .
   2. Определения (O, o, Ω, ω, Θ), уже здесь нужно сказать, что n = O(2n), 2n = O(n), n ≠ o(n), n = o(n²).
   3. Примеры: n и 2n+1, 2n и n²; O(Θ(O(f))), Θ(o(Θ(O(f)))), ...
   4. Свойства (транзитивность, связь определений друг с другом)
   5. Следствия: f ± o(f), n^k от n^k+1, многочлен от старшего члена.
   
   
3. [10 минут] Примеры
   1. 5 циклов for, n⁵ / 5! (константа таки важна)
   2. Длинные числа, числа Фибоначчи на самом деле считаются за квадрат (договорённость, какие операции сколько работают)
   3. Найти все a² + b² = N двумя циклами (показываем два указателя)
   4. Для всех чисел от 1 до n сгенерить список делителей (nlogn, 2 цикла for, оцениваем сумму гармонического ряда).

1. [15 минут] Умножение многочленов и чисел
   1. Умножение в столбик за O(nm), хранение чисел
   2. Многочлены ↔ числа, переносы
   3. Алгоритм Карацубы за O(n^1.58)
   
   
2. [25 минут] Главные теоремы
   1. [5 минут] Рекуррентность: примеры, T(n) = 2T(n/2) + n ; T(n) = T(n/2) + n ; T(n) = 3T(n/2) + n
   2. [15 минут] Рекуррентность: мастер теорема T(n) = aT(n/b) + n^c. Доказательство времени работы Карацубы.
   3. [2 минут] Примеры на экспоненциальные соотношения: числа Фибоначчи, оценки 2ⁿ и 2^n/2
   4. [15 минут] Теорема об экспоненциальных рекуррентных соотношениях T(n) = ∑_i b_i T(n-a_i). Применение к числам Фибоначчи.
   
   
3. [10 минут] Примеры асимптотик
   1. T(n) = 2T(n/2) + n, T(n) = 2T(n/2) + Cn, T(n) = 2T(n/2) + O(n)
   2. T(n) = T(n-1) + n
   3. T(n) = T(n-3) + T(n-3)
   4. T(n) = T(n-1) + T(n-2) + T(n-2)
   
   
4. [2 минут] Формулировки: log^an = O(n^b), n^b = O(cⁿ)