Документация

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

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

Но, в действительности, это только надводная часть айсберга. До­кументация включает в себя всю информацию и помогает объяснить, что делается в программе, т. е., в частности, блок-схемы, описания ступеней в вашем построении сверху-вниз, вспомогательные доказа­тельства правильности, результаты тестирования, детальные описания формата и требований к вводу/выводу и т.д.

В простейшем случае документацию можно разбить на 3 составляющие:

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

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

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

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

Глава 4. Некоторые основные приемы и алгоритмы

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

4.1 Структурное программирование сверху-вниз и правильность программ

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

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

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

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

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

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

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

Идеи структурно программирования в наиболее полной форме были высказаны Э.Дейкстрой, однако они опираются на работы К.Бема, Г.Джекопини, П.Наура и Р.Флойда.

Фундаментом структурного программирования является доказанная Бемом и Джекопини теорема о структурировании. Эта теорема устанавливает: как бы ни была сложна задача, блок-схема соответствующей программы всегда может быть представлена с использованием весьма ограниченного числа элементарных управляющих структур, например:

f THEN g IF p THEN f ELSE g WHILE p DO f

(следования) (ветвления) (цикла)

Эти элементарные структуры могут соединяться между собой, образуя более сложные структуры, по тем же самым элементарным схемам. При этом f и g могут являть собой довольно сложные блок-схемы с одним входом и одним выходом, построенные из таких же элементарных структур.

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

4.2 Основные правила структурного программирования

Наше объяснение структурного программирования мы начнем с определения блок-схемы. Блок-схема — это ориентированная сеть, вершины которой могут быть одного из трех типов, представленных на рис. 4.1

Функциональная вершина используется для представления функции F: X-->Y. Предикатная вершина используется для представления функ­ции (или предиката) р: Х-->{Т, F}, т. е. логического выражения, пере­дающего управление по одной из двух возможных ветвей. Объединяю­щая вершина представляет передачу управления от одной из двух входящих ветвей к одной выходящей ветви.

Структурная блок-схема — это блок-схема, которая может быть выражена как композиция из четырех элементарных блок-схем, изображенных на рис. 4.2. Сравнительно просто доказать, что любая программа для вычислительной машины может быть «представлена» блок-схемой. Как было показано Бомом и Якопини, верно (хотя да­леко не очевидно) и то, что любая блок-схема может, в свою очередь, быть представлена структурной блок-схемой. Из этого результата немедленно следует, что для разработки любого алгоритма достаточно четырех элементарных блок-схем, приведенных на рис. 4.2.

Когда структурная блок-схема служит как представление про­граммы, В интерпретируется как булевское выражение, a S1 и S2интерпретируются как программные операторы (или процедуры).

Блок-схемы на рис. 4.2 а, б, в и г называют структурами уп­равления программы. Схема на рис. 4.2 а называется композицией и записывается в виде S1; S2. Схема на рис. 4.2 б называется выбором (или альтернативой) и записывается в виде if В then SI else S2. Блок-схемы на рис. 4.2 в и г называются итерацией (или по­вторением) и записываются соответственно как while В do S1 и do SI while S.

Следует отметить, что часто употребляемый упрощенный оператор if В then Si, блок-схема которого приведена на рис. 4.3, представ­ляет собой частный случай оператора if - then-else.

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

for...next

while...wend

do...loop

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

If В then do SI; S2

else if С then S3

else S4

If В then if С then SI; S2

else while D; S3 wend

else S4; S5; S6

Обратите внимание на то, что в предыдущих блок-схемах совершенно отсутствует оператор goto.

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

Однако в более широком плане структурное программирование до­пускает большее разнообразие элементарных структур управления, чем те, которые были предложены Бомом и Якопини (т. е. те, которые изображены на рис. 42). Дело в том, что, хотя эта совокупность структур управления достаточна для построения любой программы для вычислительной машины, само построение не обязательно ока­жется простейшим или наиболее естественным. Проиллюстрируем это на некоторых примерах.

Первый пример (рис. 4.5) соответствует ситуации, обрабатывае­мой на Турбо-Бейсике оператором SELECT... END SELECT. Лингвистически эту блок схему можно выразить в виде:

SELECT CASE i

CASE i=1: S1

CASE i=2: S2

CASE i=3: S3

........

CASE i=m: Sm

CASE else: S

END SELECT.

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

Кроме того, может возникнуть ситуация, когда обычный переход является лаконичным, простым и ясным средством, в то время как другие подходы сравнительно неудачны. Хотя более строгие формы структурного программирования исклю­чают применение оператора goto, блок-схемы, в которых оператор goto используется достаточно аккуратно, могут сохранить свойство структурных блок-схем: один вход и один выход.

Еще один пример простой неструктурированной блок-схемы, которая может встречаться в программировании, при­веден на рис. 4.6а. На рис. 4.6 б ука­зан один из способов структурирования этой блок-схемы, хотя получаемый резуль­тат и нельзя считать вполне естественным. Заметим, что лингвистический оператор для неструктурированной блок-схемы на рис. 4.6 а требует применения оператора goto. Например,

k: S1: if then S2: goto k

тогда как лингвистический оператор для структурированной блок-схемы на рис. 4.6 б его не содержит. Например,

S1: while В: S2: S1 wend

Вообще, структурное програм­мирование определяет процесс разработки алгоритмов в терминах «квазиструктурирован-ных» блок-схем, в которых элемен­тарные структуры управления являются, как правило, структурами Бома и Якопини. Впрочем, допускаются и другие структуры «простого типа» при условии, что они обладают свойством «один вход и один выход».

Как отмечалось выше, программирование сверху-вниз—это процесс пошагового разбиения алгоритма на всё более мелкие части с целью получить такие элементы, для которых можно легко написать конкретные команды. На рис. 4.7 этот процесс иллюстрируется для случая блок-схемы на рис. 4.4б.

Теперь попытаемся дать определение структурного программирования

Структурное программирование сверху-вниз — это процесс про­граммирования сверху вниз, ограниченный использованием струк­турных блок-схем. Идея весьма проста. Предположим, что требуется разработать алгоритм для некоторой конкретной функции f. Пусть далее можно доказать, что f есть композиция двух других (надо пола­гать, более простых) функций g и h, т.е. f(x)=h(g(x)), как показано на рис. 4.8. Тогда проблема разработки алгоритма для f сводится к проблемам разработки алгоритмов для g и h. Пусть далее можно доказать, что функция g равна некоторой функции i, когда заданный параметр х неотрицателен, или равна некоторой другой функции j, когда х отрицателен. Тогда алгоритм для вычисле­ния g можно выразить в форме конструкции if-then-else (рис. 4.9).

Поэтому, если алгоритмы для функций i и j построены, то правильный алгоритм для функции g строится автоматически.

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

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

Дата добавления: 2014-12-16