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

Специальные выпуски о комбинаторике. Дополнительный семинар, когда сессия уже (почти) сдана, а семестр ещё далеко -- самое время поговорить об отвлеченных вещах. Например о матроидах. Мы рассмотрим жадные алгоритмы, разные задачи, которые решаются жадными алгоритмами и введём специальную структуру матроида как систему множеств с ограничениями. В процессе мы столкнёмся с разменом монет, графами, матрицами, криптоморфизмами и многим другим. Будет весело и страшно. Лектор: Константин Владимиров Дата лекции: 22 января 2022 года Съёмка: Марк Гончаров. Звук: Дмитрий Рябцев. Предыдущие попытки: 1. Первая черновая запись: • Матроиды и гридоиды https://rutube.ru/video/a69e29dd1968f728f6cf2df78fb6111b/ 2. Вторая черновая запись: • Дополнительный семинар по матроидам https://rutube.ru/video/6357942b370380bc2c12eb4f1673c57e/ Следующая лекция: TBD Слайды ко всем лекциям по комбинаторике: https://sourceforge.net/projects/cpp-lects-rus/files/combinatorics/ Задачник для первого курса: http://olymp1.vdi.mipt.ru 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: * Тут пока пусто

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