Алгоритмы и способы их разработки
Дискретная математика – это область науки, в которой рассматриваются разнообразные задачи с дискретными (не являющимися непрерывными) данными, исследуются методы решения таких задач и изучаются наиболее оптимальные алгоритмы поиска этих решений.
В связи с современными условиями, связанными с развитием вычислительной техники, появились возможности по программированию разнообразных алгоритмов, которые используются при решении огромного количества прикладных задач.
Несмотря на то, что не существует универсального подхода к составлению алгоритмов, полезно знать некоторые общие принципы и способы, которые используются при разработке любых алгоритмов, применяемых для эффективного решения различных задач.
Наиболее распространённым методом является системный подход, основанный на принципах декомпозиции (нисходящего проектирования) и синтеза (восходящего проектирования).
При нисходящем проектировании происходит процесс пошагового разделения исходной задачи на целый ряд более мелких подзадач, для которых достаточно применять более простые технологии решения. В итоге, в результате повторения данного процесса нужное количество раз, будут получены подзадачи, решаемые с помощью элементарных команд.
При восходящем проектировании, наоборот, сначала разрабатываются элементарные конструкции, на основе которых формируются подзадачи более общего назначения, представляющие собой функционально завершённые элементы. Далее, опираясь на них, аналогичным образом создаются ещё более общие подзадачи, и данный процесс продолжается до тех пор, пока не будет получен уровень, на котором решается исходная задача. Такой принцип синтеза используется в модульном программировании, технология которого основывается на максимальном использовании различных стандартных функций, процедур и других специализированных программных продуктов.
Также при проектировании алгоритмов применяются методы дедукции (переход от общего знания к частному) и индукции (переход от известных частных фактов к общему выводу).
Ещё для составления алгоритмов при решении сложных вычислительных задач и задач, связанных с обработкой данных, принято использовать такие способы организации вычислительного процесса, как итерация и рекурсия.
Итерация («выполнить для всех n») – это способ организации процесса обработки данных, при котором некоторые действия многократно повторяются, не вызывая при этом самих себя.
Рекурсия («выполнить то же, что и в последний раз») – это метод вычисления функции, определения объекта или нахождения результата процедуры, который выполняется при помощи той же функции, объекта или процедуры, соответственно.
Особенностью итерации и рекурсии является их взаимозаменяемость. То есть для решения задач, в которых требуется применение рекурсии (например, вычисление факториала), можно составить алгоритм, использующий несколько итераций, и, наоборот, от итерационной задачи вернуться к рекурсивному алгоритму.
Основные методы построения алгоритмов
В дискретной математике существует целый ряд алгоритмов, позволяющих эффективно решать те или иные прикладные задачи, относящиеся к самым разнообразным классам. Причём даже для однотипных задач зачастую есть сразу несколько вариантов алгоритмов, применяемых для поиска их решения.
Рассмотрим наиболее важные методы, на основе которых создавались многие распространённые алгоритмы дискретной математики.
Метод декомпозиции (частных целей).
Несмотря на то, что не существует каких-либо чётких правил для определения класса задач, которые можно было бы решить с помощью этого метода, именно такой подход в алгоритмизации является наиболее распространённым, составляя основу всего программирования. Данный принцип позволяет применять уже полученные в некоторой задаче решения для дальнейшего поиска ответа в какой-то другой, схожей с ней, задаче.
Метод подъёма (от начального предположения).
Этот метод не всегда является эффективным, так как при его использовании невозможно быть уверенным, что найденное в задаче решение будет оптимальным.
Метод отрабатывания назад.
Здесь предполагается, что решение задачи уже известно, и весь метод заключается в том, что последовательно определяются условия, при которых такое решение может быть получено.
Метод динамического программирования.
С помощью этого метода можно решать достаточно сложные задачи, комбинируя решения различных вспомогательных подзадач. И в отличие от метода декомпозиции, где исходная задача разделяется на независимые подзадачи, здесь подзадачи могут перекрываться. При этом каждая подзадача решается только один раз, после чего её ответ сохраняется и может быть использован в последующем решении.
«Жадные» методы.
Для них характерно то, что на каждом отдельном шаге решения задачи выбирается тот вариант, который в данный момент является локально оптимальным, соответствуя всем предъявляемым к нему по условию задачи требованиям. Такие алгоритмы позволяют получать эффективные решения, но не подходят для любого класса задач.
Метод поиска с возвратом (отбрасывания назад).
Данный метод предполагает максимально возможное углубление по ветви исследуемого решения, а затем обратный возврат и попытку сделать какой-то другой выбор на ближайшем шаге алгоритма, где это допустимо. Такой подход позволяет решать задачи, в которых просматриваются все возможные варианты в поиске среди них оптимального решения.
Детерминированные и недетерминированные алгоритмы
Все алгоритмы можно разделить на две большие группы:
- детерминированные (определённые) алгоритмы;
- недетерминированные (неопределённые) алгоритмы.
Говорят, что задача имеет детерминированный метод решения, если она решается прямым способом. Любой детерминированный алгоритм всегда позволяет найти регулярное решение и характеризуется очень чёткой определённостью на каждом своём шаге, а также недопустимостью применения методов проб и ошибок.
Если же решение задачи не может быть получено прямым методом и его приходится выбирать из множества различных вариантов, то в этом случае говорят о недетерминированном методе решения. Такой недетерминированный алгоритм предполагает систематический подход в поиске нужного решения среди всех возможных и основывается на методе проб и ошибок, допуская в своей реализации многократные повторы и случайный выбор. И, несмотря на то, что обычно поиск решения задачи таким способом оказывается достаточно сложным, проверку полученного в ходе выполнения алгоритма решения будет легко выполнить.
Теперь приведём примеры различных задач, для которых применяется тот или иной метод решения. Так, детерминированные алгоритмы применяются при решении математических уравнений, в задачах о проверке данных и во многих других задачах. Недетерминированные алгоритмы позволяют, например, определить все делители заданного числа, найти нужное слово (или строку) в некотором тексте, а также используются при решении известной задачи коммивояжера.
При поиске алгоритма для решения какой-либо задачи обычно рекомендуется выбирать детерминированные алгоритмы (если они вообще возможны и применимы в данной ситуации), так как именно они являются наиболее эффективными.
