Практические занятия по языку C на первом курсе МФТИ. Кафедра информатики.
На этом занятии мы плотно займёмся анализом алгоритмов. Начнём мы с бинарного поиска и сортировок, использующих стратегию разбиения пополам. А дальше погрузимся в доказательство основной теоремы (master theorem) которую далее будем использовать в анализе асимптотической сложности. Я попробую не только доказать эту теорему но и объяснить как она работает. Ну а закончим поучительным перемножением полиномов.
Семинарист: Константин Владимиров.
Дата: 3 ноября 2023 года.
Съёмка: Марк Гончаров.
Звук: Юлий Тарасов.
Предыдущий семинар: • Практика языка C (МФТИ...
Следующий семинар: • Практика языка C (МФТИ...
Слайды к занятиям: cs.mipt.ru/wp/?page_id=7775
Примеры кода: github.com/tilir/c-graduate
Задачник: olymp1.vdi.mipt.ru/
Timeline
00:00 Вступление
02:45 Линейный и бинарный поиск
10:35 Быстрая сортировка
17:45 Разбиение по элементу
24:20 Сортировка слиянием
28:40 Основная теорема
50:40 Время решать задачи
52:10 Перемножение полиномов
01:06:10 Ревью кода
01:16:38 Пишем partition
01:26:38 Завершение
Errata:
* Пока пусто
13 июл 2024
