Просмотр исходного текста страницы Жадный алгоритм в задачах о покрытии/Задачи/internal-cover

<latex>
Дано множество $n$ точек $X = \{x_1,..., x_n\}$, принадлежащих одной прямой. \\
\begin{enumerate}
      	\item 
    Разработать «жадный» алгоритм, который находит наименьшее множество закрытых интервалов длины 1, которое содержит все точки. 
        \item 
    Доказать оптимальность алгоритма и оценить его сложность.
        \item 
    Применима ли теория матроидов \footnote  {Матроид -- классификация подмножеств некоторого множества, представляющая собой обобщение идеи независимости элементов, аналогично независимости элементов линейного пространства, на произвольное множество.} для доказательства оптимальности алгоритма?
\end{enumerate}
</latex>

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]