Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Вычисления предназначаются для того, чтобы получить опре деленный нужный результат. Начавшись в дискретный момент tb, они завершатся в более поздний дискретный момент и мы предполагаем, что их результат может быть описан путем сравнения "состояния в момент t0 " и "состояния в момент t Если никакие промежуточные состояния не принимаются в рассмотрение, то считается, что результат достигается некоторым простым действием.
Если же мы включаем в рассмотрение ряд промежуточных состояний, то это означает, что мы разлагаем действие на временные этапы. Оно представляется как последовательное вычисление, т. е. временная последовательность некоторых поддеиствий, и мы должны убедиться в том, что общий эффект этой последовательности поддействий на самом деле тождествен желаемому результату всего вычисления.
В простейшем случае производится разбор, или разложение, на конечное число поддействий, которые могут быть перенумерованы. Это можно представить в виде блок-схемы следующим образом:
Правильность такого разложения должна быть доказана рассуждением с перечислением. При этом логический разрыв между программой и вычислением может быть сокращен благодаря требованию, чтобы каждый линейный участок текста программы содержал имена или описания поддействий в том порядке, в котором они должны выполняться.
Заголовок альтернативы
if условие then оператор 1 else оператор 2
является "надстройкой" по отношению к "оператору Г' и "оператору 2": это две альтернативы, которые не могут быть выражены одновременно при обычной линейной записи.)
Хоор обобщил понятие заголовка альтернативы, введя конструкцию case-of, обеспечивающую выбор среди более чем двух возможностей. В виде блок-схем это выражается следующим образом:
Общее свойство всех этих блок-схем состоит в том, что у каждой из них один вход вверху и один выход внизу. Пунктирные блоки обозначают, что каждая блок-схема может в свою очередь интерпретироваться (независимо от содержимого пунктирного контура) как единое действие при последовательных вычислениях. Если говорить чуть более точно, мы имеем дело с большим числом возможных вычислений, непосредственно разлагаемых в одну и ту же временную последовательность поддействий, и только при более детальном рассмотрении, а именно при заглядывании внутрь пунктирного блока, выясняется, что над разнообразием возможных вычислений такое поддействие может принимать одну из перечисленных различных форм.,
Сказанного выше достаточно, чтобы рассматривать класс вычислений, которые непосредственно разлагаются на одни и те же последовательные пронумерованные поддействия. Однако этого недостаточно, чтобы рассматривать класс вычислений, которые непосредственно разлагаются на различное число поддействий. (Речь идет о том, что число поддействий изменяется в рамках рассматриваемого класса вычислений.) Именно здесь становится очевидной полезность заголовков повторения. Сошлемся на операторы "while условие do оператор" и "repeat оператор until" условие", которые могут быть представлены в виде блок-схем следующим образом:
Эти блок-схемы также характеризуются наличием одного входа вверху и одного выхода внизу. Они позволяют нам выразить мысль, что действие, представляемое пунктирным блоком, оказывается при детальном рассмотрении последовательностью из "достаточного числа" поддействий определенного вида.
Итак, мы познакомились с тремя типами разложения; можно называть их соответственно "сочленением", "выбором" и "повторением". Для понимания первых двух служит рассуждение с перечислением, а для последнего нужна математическая индукция.
Программы, при написании которых управление последовательностью действий осуществляется только при помощи выбора и повторения, допускают непосредственный перевод на некий язык программирования, который отличается от исходного только тем, что все управление последовательностью действий должно быть выражено передачами управления на метки. Однако обратное утверждение было бы неправильным. Напротив, если мы ограничимся указанными тремя типами разложения, то это приведет к ограничению топологии блок-схем по сравнению с различными блок-схемами, которые могут быть получены, если разрешить проведение стрелок из любого блока в любой другой блок. Отказавшись от большого разнообразия блок-схем и ограничившись данными тремя типами операторов управления, мы следуем тем самым некоей последовательностной дисциплине.
Почему я предлагаю придерживаться этой последовательностной дисциплины? Это решение может быть обосновано различными способами, и я попытаюсь изложить несколько таких обоснований в надежде на то, что хотя бы одно из них удовлетворит моих читателей.
В конечном счете мы стремимся изготовлять такие хорошо организованные программы, чтобы интеллектуальное усилие (оцениваемое неформально), которое необходимо для их понимания, было пропорционально размеру программы (оцениваемому столь же неформально). В частности, мы должны остерегаться чрезмерных рассуждений с перечислением, что побуждает нас руководствоваться старым правилом „разделяй и властвуй"; в этом причина того, что мы предлагаем последовательно разлагать вычисления на этапы.
Разложение сочленением мы можем понимать с помощью рассуждения с перечислением. (Это возможно при условии, что число поддействий, на которые непосредственно разлагается вычисление, достаточно мало, а результаты их применения сформулированы достаточно точно. Мы вернемся к обсуждению этих требований позднее, а пока будем предполагать, что эти условия удовлетворяются.) При этом удобно высказывать суждения относительно вычислений, пользуясь текстом программы, поскольку связь между продвижением вычислений и продвижением по тексту программы является тривиальной. В частности, если при детальном рассмотрении оказывается, что некое поддействие управляется заголовком выбора или заголовком повторения, это не затрудняет понимания непосредственного разложения, так как принимается во внимание только общий эффект поддействия.
30. Неоднозначность определения программы. Проблема сравнения программ.
Дата публикования: 2015-01-26; Прочитано: 307 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!