Базовые канонические структуры алгоритмов

Для реализации алгоритмов на ПЭВМ используется алгоритмический язык — набор символов и правил образования и истолкования конструкций из этих символов для записи алгоритмов.

Любую программу можно написать, используя комбинации трех базовых структур:

  • — следование, или последовательность операторов;
  • — ветвление, или условный оператор;
  • — повторение, или оператор цикла.

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

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

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

Согласно положениям структурного программирования можно выделить всего три различных варианта организации потока управления действиями алгоритма. Поток управления может обладать следующими свойствами: каждый блок выполняется не более одного раза; выполняется каждый блок. Поток управления, в котором имеются оба эти свойства, называется линейным — в нем несколько функциональных блоков выполняются последовательно. Линейному потоку на языке блок-схем соответствует структура, показанная на рис. 2.8.

Линейный поток управления

Рис. 2.8. Линейный поток управления

Очевидно, несколько блоков, связанных линейным потоком управления, могут быть объединены в один функциональный блок (рис. 2.9).

Функциональный блок

Рис. 2.9. Функциональный блок

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

а б

Рис. 2.10. Полное (а) и неполное (б) ветвление

Если структура содержит два функциональных блока (Sj и S2), ветвление называется полным (рис. 2.10, а); возможно существование неполного ветвления — при этом один из блоков пуст (рис. 2.10, б).

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

Схема переключателя

Рис. 2.11. Схема переключателя

Повторение представляет собой многократное выполнение фрагментов алгоритма (программы). Такой тип потока управления называется циклическим. Он организует многократное повторение функционального блока, пока логическое условие его выполнения является истинным. Например (рис. 2.12), действие А будет повторяться до тех пор, пока значение предиката Сбудет оставаться истинным. Поэтому в действии А должны изменяться значения переменных, от которых зависит Р, в противном случае произойдет зацикливание.

Схема цикла с предусловием

Рис. 2.12. Схема цикла с предусловием

Вычисление предиката Р возможно после выполнения действия А, в этом случае действие А будет выполняться хотя бы один раз (рис. 2.13).

Алгоритм называется структурным, если он представляет собой комбинацию трех уже рассмотренных выше структур (они называ-

Схема цикла с постусловием

Рис. 2.13. Схема цикла с постусловием

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

  • понятность и простота восприятия алгоритма (поскольку невелико число исходных структур, которыми он образован);
  • проверяемость (для проверки любой из основных структур достаточно убедиться в правильности входящих в нее функциональных блоков);
  • модифицируемость (она состоит в простоте изменения структуры алгоритма, поскольку входящие в нее блоки относительно независимы).

После введенных определений можно сформулировать структурную теорему Бома — Джакопини: любой алгоритм может быть сведен к структурному. Иными словами, для любого неструктурного алгоритма может быть построен эквивалентный ему структурный алгоритм.

2.8. Полное построение алгоритма

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

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

  • 1) постановка задачи;
  • 2) построение модели;
  • 3) разработка алгоритма;
  • 4) проверка правильности алгоритма;
  • 5) реализация (программирование) алгоритма;
  • 6) анализ алгоритма и его сложности;
  • 7) проверка (отладка) программы;
  • 8) составление документации.

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

Этапы решения задач на ЭВМ

Рис. 2.14. Этапы решения задач на ЭВМ

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

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

Постановка задачи. Прежде чем уяснить задачу, ее нужно точно сформулировать. Это условие само по себе не является достаточным для понимания задачи, но оно абсолютно необходимо.

Обычно процесс точной формулировки задачи сводится к постановке правильных вопросов. Перечислим некоторые полезные вопросы для плохо сформулированных задач:

  • — Понятна ли терминология, используемая в предварительной формулировке?
  • — Что дано? Что нужно найти?
  • — Как определить решение?
  • — Какие данные недостаточны или, наоборот, все ли перечисленные в формулировке задачи данные используются?
  • — Какие сделаны допущения?

Возможны и другие вопросы, возникающие в зависимости от конкретной задачи.

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

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

  • 1. Какие математические структуры больше всего подходят для задачи?
  • 2. Известны ли решенные аналогичные задачи?

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

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

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

Сделав пробный выбор математической структуры, задачу следует переформулировать в терминах соответствующих математических объектов. Это будет одна из возможных моделей, если можно утвердительно ответить на такие вопросы, как:

  • — Вся ли важная информация задачи хорошо описана математическими объектами?
  • — Существует ли математическая величина, ассоциируемая с искомым результатом?
  • — Выявлены ли какие-нибудь полезные отношения между объектами модели?
  • — Можно ли работать с моделью? Удобно ли с ней работать?

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

Правильность алгоритма. Доказательство правильности алгоритма — это один из наиболее трудных, а иногда и особенно утомительных этапов создания алгоритма. Вероятно, наиболее распространенный прием доказательства правильности программы — это прогон ее на разных тестах. Если выданные программой ответы могут быть подтверждены известными или вычисленными вручную данными, возникает искушение сделать вывод, что программа «работает» правильно. Однако этот метод редко исключает все сомнения; может существовать случай, в котором программа не работает.

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

Другой метод доказательства правильности алгоритма, который не имеет специального названия, состоит в следующем. Для каждого цикла, который имеется в программе (алгоритме), вручную (например, на калькуляторе) подсчитывают две контрольные точки. Если контрольные точки совпадают со значениями, выданными программой, можно быть уверенным, что все циклы в программе работают правильно. Почему речь идет о двух контрольных точках? Дело в том, что первое контрольное значение в программе может быть вычислено правильно, а затем в этом цикле будут выполнены некоторые некорректные действия, которые приведут к искажению всех последующих результатов. Совпадение второго контрольного значения как раз и подтверждает, что в данном цикле некорректности нет. Таким образом — два контрольных вычисления должны быть сделаны для каждого цикла программы.

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

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

При этом возникает ряд проблем.

  • 1. Очень часто отдельно взятый шаг алгоритма может быть выражен в форме, которую трудно перевести непосредственно в конструкции языка программирования. Например, один из шагов алгоритма может быть записан в виде, требующем специальной подпрограммы для своей реализации.
  • 2. Реализация может оказаться трудным процессом, потому что перед тем как написать программу, необходимо построить систему структур данных для представления важных аспектов используемой модели. Чтобы сделать это, необходимо ответить, например, на такие вопросы:
    • — Каковы основные переменные?
    • — Каких они типов?
    • — Сколько нужно массивов и какой размерности?
    • — Целесообразно ли пользоваться связными списками?
    • — Какие нужны подпрограммы (возможно, уже записанные в памяти)?
    • — Каким языком программирования пользоваться?

Конкретная реализация может существенно влиять на требования к памяти и на скорость алгоритма.

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

 
Посмотреть оригинал