Лекция 1: Жадный алгоритм

Подробности

Категория: Алгоритмы: построение и анализ

Лекция посвящена задачам, решаемым жадным алгоритмом. Приводится задача выбора подмножества из множества точек трехмерного пространства, задача нахождения максимальной системы линейно-независимых строк матрицы, задача из теории графов. Рассказывается об алгоритме Крускала, о структуре непересекающихся множеств, о системе представителей, о матроидах.