ТЕМА 3. ТЕХНОЛОГИЯ РАЗРАБОТКИ АЛГОРИТМОВ И ПРОГРАММ.



3.1. Основные этапы разработки программного обеспечения.


Программное обеспечение (ПО) в процессе своего создания и эксплуа-

тации проходит последовательно следующие этапы:


- постановка и анализ задачи; составление спецификаций будущего ПО

(т. е. описание технических требований к решению этой задачи).

- построение и анализ формальной модели задачи. В ходе анализа мо-

дели выявляются главные факторы, влияющие на ее работу; связь между эти-

ми факторами. Определяется последовательность работы и взаимодействие

частей модели. Проводится поиск и запись математических и логических

соотношений между элементами модели.

- проектирование алгоритма решения задачи.

- проектирование структуры исходной, промежуточной и выходной ин-

формации для данной задачи. Этот и предыдущий этапы позволяют обоснован-

но выбрать язык программмирования для записи (кодирования) исходной

программы.

- запись программы в соответствии с синтаксическими правилами соот-

ветствующего языка программирования.

- автоматическая трансляция (перевод) исходной программы на машин-

ный язык. С этого момента начинается процесс отладки и тестирования

(испытания) программы.

- подготовка технической документации по программе в соответствии с

требованиями государственного стандарта.

- эксплуатация и сопровождение программы. С этого момента начина-

ется "жизненный цикл" программы, в процессе которого возможна ее модер-

низация.



3.2. Проектирование алгоритмов.


Если требуется решить задачу на ЭВМ, то необходимо разработать ал-

горитм - способ действий, ясно и недвусмысленно объясняющий этапы вы-

числений, которые должны быть выполнены над исходными данными задачи,

чтобы получить корректное решение (когда оно существует) за конечное

время. Составление алгоритма - важнейший шаг для получения эффективной и

правильной программы. При этом предполагается правильный выбор языка и

полнота спецификаций программы.


Возникает вопрос как выбрать хороший алгоритм? Первое правило - не

начинайте программировать первый пришедший в голову алгоритм, просмотри-

те по крайней мере несколько вариантов. Имеется немало литературных

источников, где рассматриваются вычислительные алгоритмы, например,

трехтомник Д. Кнута "Искусство программирования для ЭВМ". Все профессио-

нальные программисты должны быть знакомы с этимии полезными изданиями.



3.2.1. Требования к алгоритмам.


Разработанный алгоритм должен удовлетворять ряду требования, среди

которых следует выделить:


- определенность; результаты работы алгоритма должны однозначно

соответствовать исходными данными задачи.

- массовость; алгоритм должен быть работоспособным не для одного, а

для целого множества исходных данных.

- информативность (результативность); результатом работы алгоритма

должно быть или решение задачи или сообщение о невозможности такого ре-

шения при предложенном наборе исходных данных.

- эффективность; работа алгоритма должна заканчиваться за конечное,

определенное условием задачи, время и за конечное количество шагов.



3.2.2. Временная и емкостная сложность алгоритмов.


Если дана задача, как найти для ее решения эффективный алгоритм? А

если алгоритм найден, как сравнить его с другими алгоритмами, решающими

ту же задачу? Как оценить его качество? Вопросы такого рода интересуют и

программистов-практиков и программистов-теоретиков.


Для оценки алгоритмов существует много критериев. Наибольший инте-

рес представляет порядок роста необходимых для решения задачи времени и

емкости памяти при увеличении входных данных. Обычно с каждой конкретной

задачей связывается некоторое число, называемое ее размером, которое вы-

ражает меру количества входных данных. Например, размером задачи умноже-

ния матриц может быть наибольший размер матриц-сомножителей. Размером

задачи о графах может быть число ребер данного графа.


Время, затрачиваемое алгоритмом, как функция размера задачи, назы-

вается временной емкостью этого алгоритма. Поведение этой сложности в

пределе при увеличении размера задачи называется асимптотической времен-

ной сложностью. Аналогично можно определить емкостную сложность и асимп-

тотическую емкостную сложность.


Именно асимптотическая сложность алгоритмов определяет в итоге раз-

мер задач, которые можно решить этим алгоритмом. Если алгоритм обрабаты-

вает входы размера n за время c*n^2, где c - некоторая постоянная, то

говорят, что временной сложность этого алгоритма есть O(n^2) (читается

"порядка n^2").


Следующий пример придаст предшествующим рассуждениям более конкрет-

ный характер. Допустим, имеется пять алгоритмов A1, A2, A3, A4, A5 со

следующими временными сложностями соответственно O(n), O(n*log(n)),

O(n^2), O(n^3), O(2^n). Здесь временная сложность - это число единиц

времени, требуемого для обработки входа размера n. Предположим, что вре-

менные сложности алгоритмов A1, A2, A3, A4, A5, в действительности равны

соответственно 1000*n, 100*n*log(n), 10*n^2, n^3 и 2^n. Тогда A5 будет

наилучшим для задач размера 2<=n<=9, A3 - для задач размера 10<=n<=58,

A2 - при 59<=n<=1024, а A1 - при n>1024. -



3.2.3. Алгоритмы полиномиальной сложности и NP-полные алгоритмы.


Сколько времени должна требовать задача, чтобы ее сочли действи-

тельно трудной? Общепринято, что если задачу нельзя решить быстрее, чем

за экспоненциальное время, то ее следует рассматривать как безусловно

трудно разрешимую. В этой "схеме классификации" задачи, решаемые алго-

ритмами полиномиальной сложности, будут легко разрешимыми. Но нужно

иметь в виду, что хотя экспоненциальная функция (такая, как 2^n) растет

быстрее любой полиномиальной функции от n, для небольших значений n, ал-

горитм, требующий O(2^n) времени, может оказаться эффективнее многих ал-

горитмов с полиномиально ограниченным временем работы. Например, сама

функция 2^n не превосходит n^10 до значения n, равного 59. Тем не менее

скорость роста экспоненциальной функции столь стремительна, что задачу

нызывают трудно разрешимой, если у всех алгоритмов, решающих ее, слож-

ность по меньшей мере экспоненциальна.


В теории алгоритмов приводятся соображения, показывающие, что неко-

торый класс задач, а именно задач полных для недетерминированного поли-

номиального времени (называемых NP-полными), вероятно, содержит только

трудно разрешимые задачи. Этот класс включает в себя многие "класси-

ческие" задачи из комбинаторики (такие, как задачу о коммивояжере, о га-

мильтоновом цикле, задачу целочисленного линейного программирования).


Замечание. Ключевое понятие в теории NP-полных задач - недетермини-

рованная машина Тьюринга - рассматривается в курсе "Дискретная математи-

ка".



3.2.4. Эвристические алгоритмы.


Если известно, что задача трудно разрешима, можно довольствоваться

эвристическими способами нахождения приближенных решений. Эвристические

алгоритмы решения задач обычно противопоставляются формальным методам

решения, опирающимся на точные математические модели. Использование эв-

ристических алгоритмов сокращает время решения задачи по сравнению с ме-

тодом полного ненаправленного перебора возможных вариантов, тем более

что в ряде задач полный перебор вообще невозможен (например, при созда-

нии алгоритма игры в шахматы). Решения, получаемые при использовании эв-

ристических методов, не являются, как правило, наилучшими, а относятся

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


Эвристический метод состоит в том, что по заданному правилу шаг за

шагом генерируются возможные решения (кандидаты), каждое из которых за-

тем подвергается проверке на соответствие критериям, характеризующим ре-

шение. Если предролагаемое решение оказывается неприемлемым, то генери-

руется другой кандидат; причем в этом случае возможно несколько предыду-

щих шагов придется анулировать.


Пример задачи, для которой требуется сконструировать эвристический

алгоритм ее решения:


Построить последовательность из N литер в алфавите, состоящем из

трех элементов (например, 1, 2, 3), такую, что никакие две соседние под-

последовательности не совпадают друг с другом.


Например, последовательность длины N=5 с литерами "12321" приемле-

ма, но последовательности "12323" и "12123" неприемлемы.


Алгоритм. Упражнение. -



3.2.5. Итеративные и рекурсивные алгоритмы.


Решение подавляющего числа задач, представляющих практический инте-

рес, сводится к организации многошагового вычислительного процесса. Для

организации такого процесса используются два фундаментальных метода: ме-

тод итераций и метод рекурсий.


Метод итераций широко применяется в вычислительной математике. Суть

этого метода будет рассмотрена на примере.


Пусть имеется некоторая функция F(x). Необходимо найти такие значе-

ния аргумента x, для которых F(x)=0. Функция F(x) может быть алгебраи-

ческой или трансцендентной; обычно предполагается, что она дифференциру-

ема.


В общем случае функция F(x) не имеет аналитических формул для своих

корней, в противоположность, например, квадратному уравнению. Поэтому

приходится пользоваться приближенными методами нахождения корней, кото-

рые в основном состоят из двух этапов:


- отыскание приближенного значения корня;

- уточнение приближенного значения до некоторой заданной степени

точности.


Очень часто приближенное значение корня бывает известно из физи-

ческих соображений, а в других случаях можно использовать графические

методы.


Численный метод, в котором производится, шаг за шагом, уточнение

первоначального грубого приближения, называется методом итераций. Каждый

шаг в таком методе называется итерацией. Если при последовательных ите-

рациях получаются значения, которые все ближе и ближе приближаются к

истинному значению корня, то говорят, что метод итераций сходится.


Одним из методов уточнение приближенного значения корня уравнения

F(x) является "знаменитый" метод Ньютона-Рафсона, который записывается в

форме


F'(x )

n

x = x - --------- ,

n+1 n F''(x )

n


где условия сходимости принимают вид:


- x - выбрано достаточно близко к корню уравнения F(x)=0;

0

- производная F''(x) не становится слишком большой;

- производная F'(x) не слишком близка к нулю. -


Рекурсия - это метод определения или выражения функции, процедуры,

языковой конструкции или решения задачи посредством той же функции, про-

цедуры и т. д. Функция (или процедура), которая прямо или косвенно обра-

щается к себе, называется рекурсивной. Применение рекурсии часто позво-

ляет давать более прозрачными и сжатыми описания алгоритмов, чем это бы-

ло бы возможно без рекурсии.


При реализации рекурсивных алгоритмов каждый шаг рекурсии не дает

непосредственного решения задачи, но сводит ее к такой же задаче меньше-

го размера. Этот процесс должен приводить к задаче такого размера, когда

решение получается достаточно легко. Далее "обратный ход" дает последо-

вательные решения для задачи все большего размера, вплоть до первона-

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

"магазинного" типа), где хранятся данные, участвующие во всех вызовах

процедуры, при которых она еще не завершила свою работу.


Несколько примеров придадут этой идее более конкретный характер.


Пример рекурсивного определения факториальной функции:


0! = 1, N! = N*(N-1)!, если N>0. -


Пример дважды рекурсивного определения функции, известной как функ-

ции Аккермана:


A(M, N) = if M=0 then N+1 else if N=0 then A(M-1, N) else

A[M-1, A(M, N-1)]. -


Пример рекурсивного определения идентификатора языка Turbo Pascal в

БНФ:


<идентификатор> ::=

<буква> |

<символ подчеркивания> |

<идентификатор><буква> |

<идентификатор><цифра> |

<идентификатор><символ подчеркивания> -


Полное рассмотрение преимуществ и недостатков рекурсивных и итера-

ционных алгоритмов лежит за пределами данного курса. Также обстоит дело

и с рассмотрением связей между рекурсией и итерацией, представляющих

глубокий теоретический интерес. Необходимо только знать, что любой ре-

курсивный алгоритм можно преобразовать в эквивалентный итеративный алго-

ритм.



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


Практика показывает, что программирование, понимаемое как проекти-

рование и формулирование алгоритмов, процесс сложный, требующий учета

многочисленных деталей и владения специальной техникой. Наиболее общая

тактика программирования состоит в разложении процесса на отдельные

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

таком шаге декомпозиции нужно удостовериться, что


(а) решения частных задач приводит к решению общей задачи,

(б) выбранная последовательность индивидуальных действий разумна и

(в) выбранная декомпозиция позволяет получить инструкции, в ка-

ком-либо смысле более близкие к языку, на котором в конечном счете будет

сформулирована программа.


Если видеть в поэтапной декомпозиции и одновременном развитии и де-

тализации программы постепенное продвижение вглубь, то такой метод при

решении задач можно характеризовать как нисходящий (сверху вниз). И нао-

борот, возможен такой подход к решению задачи, когда программист сначала

изучает имеющуюся в его распоряжении вычислительную машину и/или язык

программирования, а затем собирает некоторые последовательности инструк-

ций в элементарные процедуры или "кластеры действий", типичные для реша-

емой задачи. Элементарные процедуры затем используются на следующем

уровне иерархии процедур. Такой метод (из глубины примитивных машинных

команд к задаче, лежащей "на поверхности") называется восходящим (снизу

вверх). На практике разработку программы никогда не удается провести

строго в одном направлении (сверху вниз или снизу вверх). Однако при

конструировании новых алгоритмов нисходящий метод обычно доминирует!



3.2.7. Базовые управляющие структуры алгоритмов и структурное прог-

раммирование.


Истоки структурного программирования лежат в решении проблемы дока-

зательства правильности программ, т. е. в разработке математически стро-

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

их тестирование. Структурное программирование базируется на строго дока-

занной теореме о структурировании, которая утверждает, что любую пра-

вильную программу (с одним входом и одним выходом, без зацикливаний и

недостижимых команд) можно написать с использованием только следующих

управляющих структур:


- последовательности двух или более операторов;

- выбора одного из двух операторов (конструкция if-then-else);

- повторения оператора, пока выполняется некоторое условие

(конструкция while-do).


Комбинации правильных программ, полученные с использованием трех

основных (базовых) управляющих структур, также являются правильными

программами. При использовании только указанных трех структур отпадает

необходимость в безусловных переходах и метках!!!


Хотя теоретически возможно написать все правильные программы,

используя только три перечисленные базовые структуры, небольшое расшире-

ние этого базиса облегчает программирование. Введенные структуры должны

иметь один вход и один выход. Обычно включают конструкции case-of,

repeat-until и for-do.


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


- нисходящее ("сверху вниз") проектирование алгоритма;

- непосредственное структурное программировани (кодирование) с

использованием базовых управляющих структур;

- сквозной структурный контроль.



3.2.8. Модульный метод разработки алгоритмов.


Неформально модульная программа - это такая программа, в которой


Случайные файлы

Файл
3840-1.rtf
76941-1.rtf
ANNOTA~1.DOC
xar.doc
77858-1.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.