Добрый день. На первом курсе бакалавриата Академического университета читается годовой курс алгоритмов. Каждая лекция сопровождается семинаром, на котором мы разбираем алгоритмические задачи. Практические семинары проходят в небольших группах. В этом семестре я читаю лекции и веду практику у одной из групп.
Сегодня хочу поделиться с Вами двумя задачами с этих семинаров.
Задача 1. На прямой даны n отрезков, нужно выбрать максимальное по размеру подмножество непересекающихся.
Задача 2. На окружности даны n дуг (отрезков), нужно выбрать максимальное по размеру подмножество непересекающихся.
Читать полностью »