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

Министерство  образования и науки РФ

 

MКТГТУ

 

 

 

 

 

Реферат

 на тему:

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

 

 

 

 

 

 

Выполнил:

Студент группы КПР 32

Казулин И.В.

 

Проверил:

Данилкин С.В.

 

 

 

 

 

г. Тамбов, 2013

_{Общая характеристика структурного программирования}

 

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

Мы рассматриваем структурное  программирование как равноправный член сообщества альтернативных ему  друзей-соперников¹⁾ .

Начнем с того, что обратимся  к истории.

В теории схем программ было замечено, что некоторые случаи блок-схем легче поддаются анализу  [16] . Поэтому естественно было выделить такой класс блок-схем, что и сделали итальянские ученые С. Бем и К. Джакопини в 1966 г. Они доказали, что любую блок-схему можно привести к структурированному виду, использовав несколько дополнительных булевых переменных. Э. Дейкстра подчеркнул, что программы в таком виде, как правило, являются легче понимаемыми и модифицируемыми, так как каждый блок имеет один вход и один выход.

В качестве методики структурного программирования Э. Дейкстра предложил пользоваться лишь конструкциями цикла и условного оператора, изгоняя go to как концептуально противоречащее этому стилю²⁾ .

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

Средства структурного программирования в первую очередь включаются во все  языки программирования традиционного  типа и во многие нетрадиционные языки. Они занимают основное место в учебных курсах программирования и в теоретических работах (например, [1] ,[4] ,[9]).

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

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

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

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

Для структурного стиля программирования требуется следующее. Задача разбивается на подзадачи, и таким образом выстраивается дерево вложенности подзадач. Информационное пространство структурируется в точном соответствии с деревом вложенности: для каждой подзадачи оно состоит из ее локальных объектов, определяемых вместе с подзадачей и для нее, и так называемых глобальных объектов, определяемых как информационное пространство непосредственно объемлющей подзадачи. Таким образом, информационное пространство всей задачи (подзадачи самого верхнего уровня) расширяется по мере перехода к подзадачам за счет их локальных объектов. Для различных дочерних подзадач одной подзадачи оно имеет общую часть - информационное пространство родительской подзадачи⁴⁾ .

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

К структурным операторам добавляются либо циклы, либо рекурсии.

Внимание!

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

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

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

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

Первым обратил внимание на необходимость введения призраков для логического и концептуального анализа программ Г.С. Цейтин в 1971 г. В Америке это "независимо" открыли заново в 1979 г., хотя упомянутая статья Цейтина была опубликована на английском языке в общедоступном издании. Даже название сущностям было дано то же самое... Этому важнейшему и традиционно игнорируемому понятию посвящена отдельная лекция в курсе "Основания программирования" [21] .

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

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

Для структурного программирования весьма важно требование:

Все структуры подчиняются структуре  информационного пространства.

Это общее требование конкретизируется в следующие.

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

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

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

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

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

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

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

Сети данных.

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

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

Рассмотрим пример. Известному стандартному приему программирования в языках без кратных присваиваний - обмену двух значений через промежуточное.

 

z: = second;

second: = first;

first: = z;

 

соответствует следующая сеть данных:

 

Рис. 1 Обмен значений

 

Здесь first, second, z можно считать комментариями, а сами данные опущены, поскольку их конкретные значения не важны.

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

 

first,second: =second,first;

 

Даже если бы они были, представьте себе, как неудобно станет читать длинное кратное присваивание и понимать, какое же выражение  какой переменной присваивается!

В случае программы вычисления факториала¹⁾ сеть потенциально бесконечна вниз, поскольку аргументом может быть любое число, но по структуре еще проще:

 

Рис. 2

 

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

function fact (n: integer): integer;

var j,res: integer;

begin

res: =1;

for j: =1 to n do res: =res*j;

result: =res;

end;

int fact (int n)

{if (n==0) return (1);

else return (n*fact (n-1)); }

 

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

Для чисел Фибоначчи (та же схема (2)) структура уже несколько сложнее предыдущих, поскольку каждое следующее число Фибоначчи зависит от двух предыдущих, но метод потоковой обработки применим и здесь.

 

int fib (int n)

{int fib1,fib2;

fib1=1; fib2=1;

if (n>2) {

for (int i=2; i<n; i++) {

int j; j=fib1+fib2; fib1=fib2; fib2=j;

}

};

return (fib2);

}

Итак, в потоке изменяется структура из двух элементов. Ее можно было бы прямо описать как структуру данных, и это следовало бы сделать, будь программа хоть чуть-чуть посложнее. Тогда вместо подпорки j пришлось бы ввести в качестве подпорки новое значение структуры.

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

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

 

int fib (int n)

{ if (n<3) return (1);

else return (fib (n-1) +fib (n-2));

}

 

Если n достаточно велико, каждое из предыдущих значений функции Фибоначчи будет вычисляться много раз, причем без всякого толку: результат всегда будет один и тот же! Зато все подпорки убраны...

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

 

Рис. 1 Золотая гора

 

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