В 2022 году Computer Science Center приостановил набор и обучение
Направления
Курсы
Онлайн-образование
Поступление
О центре
Войти
Направления
Курсы
Онлайн-образование
Онлайн-курсы
Онлайн-программы
Видеозаписи лекций
Поступление
Подать заявку
Памятка
Программа для поступления
Вопросы и ответы
О центре
Преподаватели
Выпускники
Отзывы
Команда
История
Курсы
/
Алгоритмы и структуры данных, часть 2
/
весна 2015
/
Паросочетания
Понедельник, 06 апреля 2015
Таймс, ауд. 404
Описание
Кодим паросочетание и контролирующее множество
Stable Marriage
Рандомизированный алгоритм для паросочетания в произвольном графе
Задачи
Максимальная двудольная клика (matching)
Покрыть клетчатое поле с дырками доминошками (matching)
Нарисовать чёрно-белый шедевр минимальным числом мазков (cover)
Удаление орграфа, за ход можно удалить или входящие в v, или исходящие из v рёбра (cover)
Максимальное мультипаросочетание (выбрать рёбра так, чтобы у любой вершины степень $\le 2$).
Покрытие графа минимальным числом путей (раздвоили вершины, matching)
Есть самолёты (время вылета, вместимость). Есть пассажиры (отрезок допустимых времён вылета). Сделать так, чтобы все пассажиры улетели.
Есть прямые. Выбрать максимальное подмножество так, чтобы не было параллельных и имеющих одинаковый y пересечения c x=0.