Курсовая работа по теме Задача о наименьшем покрытии решение, алгоритмы, применение (обзор с примерами программных реализаций)
Введение
алгоритм жадный вычислительный быстродействие
Задача о наименьшем покрытии множества, рассматриваемая в данной работе, заключается в поиске минимального набора подмножеств, полностью покрывающих исходное множество. Она является классической задачей комбинаторики, информатики и теории вычислений, входит в список 21 NP-полной задачи Р. Карпа.
К задаче о покрытии сводятся многие известные задачи дискретной оптимизации: задачи стандартизации, упаковки и разбиения множества, задачао наибольшей клике, задача минимизации полинома от булевых переменных и др. Известна также и обратная сводимость задачи о покрытии к этим задачам.
На практике задачи о покрытии возникают при размещении пунктов обслуживания, в системах информационного поиска, при назначении экипажей на транспорте, проектировании интегральных схем и конвейерных линий и т. д. Задача о вершинном покрытии может использоваться при разработке систем контроля и наблюдения, в построении помехоустойчивых алгоритмов передачи информации, при диагностике оборудования и в других областях.
