2. Технология проектирования алгоритмав

 Процесс решения задачи на ЭВМ можно разбить на ряд этапов:

Существенным шагом на пути снижения трудоемкости процесса программирования стал структурный подход к проектированию алгоритмов. Его основным принципами яв­ляются нисходящее проектирование и модульное програм­мирование. Нисходящее проектирование заключается в по­следовательном разбиении задачи на все более мелкие уча­стки, т.е. процесс программирования идет «сверху вниз». Модульное программирование предполагает создание для ка­ждого такого участка отдельной автономной программы — модуля. Специально созданная программа объединяет все модули в целое и управляет их работой.

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

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

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

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

Использование вышеназванных методов позволило соз­дать огромное количество разнообразных алгоритмов, и пришлось обратить серьезное внимание на вопросы их эф­фективности. В значительной степени эффективность алго-

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

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

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

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

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

Наиболее часто используют два способа определения функции сложности:

1.         ее значением является сложность худшего случая (минимальное число действий, достаточное для обработки алгоритмом любых данных размерности n);

2.         значением является средняя сложность, взятая по всем данным размерности n.

 

Рассмотрим определение сложности на конкретных при­мерах алгоритмов поиска и сортировки.