Занятие №5 Класс алгоритмических методов «разделяй и властвуй»

ЛАБОРАТОРНОЕ ЗАНЯТИЕ № 5
Класс алгоритмических методов «разделяй и властвуй»


Цель работы: изучить принципы метода «разделяй и властвуй; научиться проводить анализ эффективности алгоритма.

Одним из самых важных и наиболее широко применимых методов проектирования эффективных алгоритмов является метод, называемый методом декомпозиции (или метод разделяй и властвуй, или метод разбиения). Этот метод предполагает такую декомпозицию (разбиение) задачи размера п на более мелкие задачи, что на основе решений этих более мелких задач можно легко получить решение исходной задачи.

Разделяй и властвуй (англ. divide and conquer) в информатике — парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Алгоритм «разделяй и властвуй» пытается разбить проблему на как можно большее количество маленьких кусков, поскольку ее легче решить с помощью маленьких кусочков. Обычно это делается с помощью рекурсии.
Формально техника, определена в известной книге «Introduction to Algorithms» Кормена, Лизерсона, Ривеста и Штейна:
1. Разделяй
Если проблема небольшая, то решайте ее напрямую. В противном случае разделите задачу на меньшие подмножества той же проблемы.
2. Властвуй
Решайте меньшие проблемы, решая их рекурсивно. Если подзадачи достаточно малы, рекурсия не нужна, и вы можете решить их напрямую.
3. Комбинируй
Возьмите решения для подзадач и объедините это с решением исходной проблемы.
Разделяй и Властвуй — стратегия, подразумевающая, что задача разделяется на независимые подзадачи и затем каждая из них решается. Примеры этой стратегии — быстрая сортировка, сортировка слиянием и пирамидальная сортировка, а также бинарный поиск.