Основные подходы к проектированию программных алгоритмов

Структурное программирование

Структурное программирование основано на модульной структуре программного продукта и типовых управляющих структурах алгоритмов обработки данных различных программных модулей.

В любой типовой структуре блок, кроме условного, имеет только один вход и выход, безусловный переход на блок с нарушением иерархии запрещен.

Различают три основных типа управляющих структур ( три класса алгоритмов): линейные, ветвящиеся и циклические.

Линейный алгоритм при каждом исполнении предписывает однократное выполнение всех действий алгоритма в определенной последовательности.

Ветвящийся алгоритм описывает несколько возможных последовательностей действий и при каждом исполнении предписывает выполнение одной из последовательностей действий в зависимости от определенных условий.

Циклический алгоритм при каждом исполнении предписывает многократное выполнение одной и той же последовательности действий.

Таблица Классы алгоритмов

Процесс последовательного построения алгоритма может выглядеть следующим образом: алгоритм сначала формулируется в самых «крупных» командах, при этом в записи алгоритма могут использоваться команды, выходящие за рамки возможностей исполнителя. Затем на каждом последующем этапе отдельные детали алгоритма уточняются, при этом недоступные исполнителю команды записываются как вызов вспомогательных алгоритмов. После этого строятся вспомогательные алгоритмы. Процесс продолжается до тех пор, пока все алгоритмы не будут состоять из команд, понятных исполнителю. Такой способ построения алгоритма называется методом последовательного уточнения алгоритма (пошаговой детализацией, нисходящей разработкой). Данный подход к проектированию алгоритмов позволяет повысить качество и надежность разрабатываемых программ. Кроме того, появляется возможность использовать отдельные модули программы при решении других задач.

На практике «чистую» нисходящую разработку осуществить практически невозможно, так как выбор более конкретизированных элементов на каждой стадии должен производиться на основе представления и понимания возможностей языка реализации. Однако даже в данном случае на более поздней стадии часто обнаруживается, что некоторый выбор, сделанный ранее, был неверным. Это приводит к необходимости разработки новых и корректировки уже имеющихся модулей.

Другой подход к созданию программ называется восходящей разработкой. При этом осуществляется последовательное построение программы из уже имеющихся элементов, начиная с примитивов, предоставляемых выбранным языком программирования. Этот процесс заканчивается получением требуемой готовой программы. На каждом этапе из имеющихся элементов строятся новые более мощные (в контексте разрабатываемой программы) элементы. Они в свою очередь используются на следующем этапе для построения еще более сложных элементов и так далее до тех пор, пока не будут получены элементы, из которых можно непосредственно составить требуемую программу. На практике восходящая разработка в чистом виде невозможна; построение каждого нового элемента должно сопровождаться «просмотром вперед» с целью проверки, выполняются ли все требования, предъ­являемые к разрабатываемой программе. Но даже при таком подходе на более позднем этапе часто обнаруживается, что использованная ранее последовательность построения была выбрана неправильно и требует корректировки.

Таким образом, на практике при разработке алгоритмов обычно используется сочетание методов нисходящего и восходящего проектирования.

Использование вышеназванных подходов позволило создать огромное количество разнообразных алгоритмов, и пришлось обратить серьезное внимание на вопросы их эффективности. В значительной степени эффективность алгоритма зависит от его сложности — количественной характеристики, указывающей, сколько времени работает алгоритм (временная сложность) либо какой объем памяти необходим для его выполнения (емкостная сложность). Сложность рассматривается в основном для алгоритмических моделей, поскольку в них время и память присутствуют в явном виде.

Физическое время выполнения алгоритма – это величина, равная произведению n и t, где n число действий (элементарных шагов, команд); t –среднее время выполнения одного действия. Число шагов и определяется описанием алгоритма в данной алгоритмической модели и не зависит от физической реализации модели; t— величина физическая и зависит от скорости сигналов в элементах и узлах ЭВМ, Поэтому объективной математической характеристикой трудоемкости алгоритма (его временной сложности) в данной модели является число действий.

Емкостная сложность (трудоемкость) алгоритма определяется числом ячеек памяти, используемых в процессе его исполнения. Эта величина не может превосходить числа действий n, умноженного на определенную константу (число ячеек, используемых в данной модели на одном шаге). В свою очередь число шагов может сколь угодно сильно превосходить объем памяти (за счет циклов по одним и тем же ячейкам). Следует отметить, что проблемы памяти технически преодолеваются легче, чем проблемы быстродействия, которое имеет физический предел — скорость распространения физических сигналов (300 тыс. км/с). Поэтому трудоемкость (временная сложность) считается более существенной характеристикой алгоритма.

Трудоемкость алгоритма, как и другие виды сложности, не является постоянной величиной, а зависит от размерности задачи. Под размерностью задачи понимается либо объем памяти, необходимой для записи данных, либо характеристики задачи, от которых зависит этот объем. В задачах обработки графов размерностью может считаться число вершин или дуг графа, в задачах преобразования логических выражений — число букв в выражении и т. д.

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

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

Метод (подъем) ветвей и границ также предназначен для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.

Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

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

В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.

Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.

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

Проще говоря, эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.

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

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

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