Матроиды (доп. семинар для первого курса по языку C и алгоритмам)

Специальные выпуски о комбинаторике. Дополнительный семинар, когда сессия уже (почти) сдана, а семестр ещё далеко -- самое время поговорить об отвлеченных вещах. Например о матроидах. Мы рассмотрим жадные алгоритмы, разные задачи, которые решаются жадными алгоритмами и введём специальную структуру матроида как систему множеств с ограничениями. В процессе мы столкнёмся с разменом монет, графами, матрицами, криптоморфизмами и многим другим. Будет весело и страшно. Лектор: Константин Владимиров Дата лекции: 22 января 2022 года Съёмка: Марк Гончаров. Звук: Дмитрий Рябцев. Предыдущие попытки: 1. Первая черновая запись: • Матроиды и гридоиды 2. Вторая черновая запись: • Дополнительный семинар по матроидам Следующая лекция: TBD Timeline: 00:00 Идея жадного алгоритма 09:53 Загадка размена монет 17:56 Примеры задач с жадным решением 31:12 Графы и остовные деревья 43:52 Алгоритм Краскала и структура этой задачи 51:42 Определение матроида и алгоритм Радо-Эдмондса 58:15 Матроидная структура ряда задач 1:07:39 Разгадка размена монет 1:10:20 Жадные алгоритмы на матрицах 1:19:10 Матроиды без грима 1:34:36 Алгоритм Прима и гридоиды 1:41:16 Обзор литературы Errata: * Тут пока пусто