Разработка алгоритма — специфический метод для создания математического
способа решения проблем.
„Разделяй и властвуй"
Возможно, самым ясным и наиболее
широко применимым методом проектирования эффективных алгоритмов является метод,
называемый методом декомпозиции (или метод "разделяй и властвуй", или
метод разбиения). Этот метод предполагает такую декомпозицию (разбиение) задачи
размера P на более
мелкие задачи, что на основе решений этих более мелких задач можно легко
подучить решение исходной задачи. Мы уже знакомы с рядом применений этого
метода, например в сортировке слиянием или в деревьях двоичного поиска.
Итерация в программировании — организация обработки
данных, при которой действия повторяются многократно, не приводя при этом к
вызовам самих себя (в отличие от рекурсии) Когда какое-то действие
необходимо повторить большое количество раз, в программировании
используются циклы. Например, нужно вывести 200 раз на экран текст «Hello,
World!». Вместо двухсоткратного повторения одной и той же команды вывода текста
часто создается цикл, который прогоняется 200 раз и 200 раз выполняет то, что
написано в теле цикла. Один шаг цикла и называется итерацией.
В программировании рекурсия —
вызов функции (процедуры) из неё же самой, непосредственно (простая
рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает
функцию B, а
функция B —
функцию A. Количество
вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного
определения объекта заключается в том, что такое конечное определение
теоретически способно описывать бесконечно большое число объектов. С помощью
рекурсивной программы же возможно описать бесконечное вычисление, причём без
явных повторений частей программы.
Метод последовательных приближений - метод повторных подстановок,
метод простой итерации,- один из общих методов приближенного решения
операторных уравнений. Во многих случаях хорошая сходимость построенных
этим методом приближений позволяет применять его в практике вычислений.
Полный перебор — метод решения математических задач. Относится
к классу методов поиска решения исчерпыванием всевозможных
вариантов. Сложность полного перебора зависит от количества всех
возможных решений задачи. Если пространство решений очень велико, то полный
перебор может не дать результатов в течение нескольких лет или даже столетий.
Любая задача из класса
NP может быть решена полным перебором. При этом, даже если вычисление
целевой функции от каждого конкретного возможного решения задачи может быть
осуществлено за полиномиальное время, в зависимости от количества всех
возможных решений полный перебор может потребовать экспоненциального
времени работы.
Эвристический алгоритм — это алгоритм решения задачи,
правильность которого для всех возможных случаев не доказана, но про который
известно, что он даёт достаточно хорошее решение в большинстве случаев. В
действительности может быть даже известно (то есть доказано) то, что
эвристический алгоритм формально неверен. Его всё равно можно применять, если
при этом он даёт неверный результат только в отдельных, достаточно редких и
хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый
результат.
Проще говоря, эвристика —
это не полностью математически обоснованный (или даже «не совсем корректный»),
но при этом практически полезный алгоритм.
Важно понимать, что эвристика, в
отличие от корректного алгоритма решения задачи, обладает следующими
особенностями:
Она не гарантирует нахождение
лучшего решения.
Она не гарантирует нахождение
решения, даже если оно заведомо существует (возможен «пропуск цели»).
Она может дать неверное решение в
некоторых случаях.
Построение обратной задачи – учебник Королев-Миков.
