Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://sp.cs.msu.ru/courses/alg/task3/index.html
Дата изменения: Fri Oct 31 19:59:00 2008
Дата индексирования: Mon Oct 1 22:10:02 2012
Кодировка: koi8-r
Домашнее задание 3.
Срок сдачи: 06/03/2000.
1.
Предложите алгоритм динамического программирования для
решения задачи о планировании работ, основанный на последовательном вычислении
mi для
,
где mi является размером наибольшего
подмножества
совместных работ из множества
.
Входные данные отсортированы
в порядке возрастания времен окончания работ. Сравните время работы
вашего алгоритма со временем работы
.
2.
Дано множество занятий, которое нужно распределить по большому
количеству аудиторий. Каждое занятие проходит в интервале времени
[si, fi) (как и в задаче, рассмотренной на лекции). Необходимо для
каждого занятия назначить аудиторию таким образом, чтобы было использовано
минимальное количество аудиторий. Предложите <<жадный>> алгоритм и
обоснуйте его корректность.
3.
В задаче о планировании работ, рассмотренной на лекции,
не всякая <<жадная>> стратегия дает множество взаимно совместных работ
максимальной мощности. Приведите пример, что стратегия, основанная
на выборе работы наименьшей продолжительности, совместимой с уже
выбранными работами, не работает. Приведите пример, что стратегия,
основанная на выборе работы, накладывающейся на наименьшее количество
оставшихся работ, не работает.
4.
Докажите, что дробная задача о рюкзаке имеет свойство
<<жадного>> выбора.
5.
Предложите эффективный алгоритм, который для множества точек
на вещественной прямой определит минимальное
количество закрытых интервалов единичной длины, которые содержат все
данные точки. Обоснуйте корректность алгоритма.