Практика языка C (МФТИ, 2023-2024). Семинар 3.2. Стратегия "разделяй и властвуй".
Вставка
- Опубліковано 13 чер 2024
- Практические занятия по языку 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:
* Пока пусто
У Вас хорошие лекции по С и С++, думал что знаю базу, а оказывается многое не знал. Будет интересно Вас послушать на конференции.
Очень круто, и ревью в конце семинара помогает. Спасибо большое за материалы
Спасибо за бесплатные лекции, безмерно уважаю вас за это. 🆒🙏☺
Надеюсь бесплатность не является их главным преимуществом ))
@@tilir конечно же нет, качественный матеиал. Всем друзьям рекомендую.
@@tilirспасибо
Спасибо за очередной ролик
На 1:24:00 в assert(arr[low] > arr[high]) нужно поставить >=
low и high могут индексировать в массиве два одинаковых элемента
А еще лучше выше заменить проверки
arr[low]=key
Извините за мои пять копеек
СУПЕР!!!!!!!
На 30 слайде, алгоритм будет работать только если длина массива не превышает INT_MAX + 1.
Благодарю за лекцию. Прочитал книгу "Грокаем алгоритмы" - там все поверхностно, а у вас развернуто
Если честно я не читал. Но попробуйте прочитать Кормена: там всё ещё более развёрнуто. Я как раз вынужден быть несколько поверхностным.
ua-cam.com/video/pcJHkWwjNl4/v-deo.html
необычный графический взгляд на insertion и selection sort'ы . При визуализации выглядят одинаково