К началу 70-х годов ХХ века, когда развитие языков программирования достигло достаточно высокого уровня, а создаваемые программные комплексы достигли достаточно внушительных размеров (сотни тысяч – миллионы команд), стало очевидно, что программные проекты стали слишком сложными для успешного проектирования, кодирования и отладки в приемлемые сроки. Программисты, решающие сложные задачи, столкнулись с проблемой роста количества и размера программ до такой степени, что дальнейший процесс разработки становился практически неуправляемым, и никто из разработчиков не мог с уверенностью сказать, что созданный программный продукт всегда выполняет то, что требуется, и что он не выполняет ничего такого, что не требуется. Таким образом, возникла проблема коренного изменения подходов к созданию больших программных комплексов.
структурной методологии
структурное программирование
1) четко структурировать программу, что улучшило ее понимание программистами;
2) выполнять доказательства ее корректности и тем самым повышать надежность функционирования программы;
3) сокращать сроки разработки программ.
Оператор GOTO нужно считать вредным
Структурное программирование
|
|
|
|
Эдсгер Вибе Дейкстра (1930 – 2002) — нидерландский учёный, идеи которого оказали влияние на развитие компьютерной индустрии. Известен как создатель алгоритма поиска кратчайшего пути на графе, один из основателей структурного программирования. В 1972 г. стал лауреатом премии Тьюринга. |
Никлаус Вирт (1934) — швейцарский учёный, специалист в области информатики, один из известнейших теоретиков в области разработки языков программирования, профессор компьютерных наук, лауреат премии Тьюринга 1984 г. Ведущий разработчик языков программирования Паскаль, Модула-2, Оберон. |
Рис. 1.
Методология структурного программирования появилась как следствие возрастания сложности решаемых на компьютерах задач, и соответственного усложнения программного обеспечения: в 70-е годы XX в. объёмы и сложность программ достигли такого уровня, что «интуитивная» (неструктурированная) разработка программ, которая была нормой в более раннее время, перестала удовлетворять потребностям практики. Программы становились слишком сложными, чтобы их можно было нормально сопровождать, поэтому потребовалась какая-то систематизация процесса разработки и структуры программ.
Наиболее сильной критике со стороны разработчиков структурного подхода к программированию подвергся оператор GOTO (оператор безусловного перехода ).
Неправильное и необдуманное использование произвольных переходов в тексте программы приводило к получению запутанных, плохо структурированных программ (т.н. спагетти-кода ), по тексту которых практически невозможно было понять порядок исполнения и взаимозависимость фрагментов.
последовательной декомпозиции
Типичными методами структурного программирования являются:
нисходящее проектирование
модульное
структурное кодирование
В соответствии с методологией структурного программирования:
1. Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:
последовательное исполнение
ветвление
цикл
В программе базовые конструкции могут быть вложены друг в друга произвольным образом, но никаких других средств управления последовательностью выполнения операций не предусматривается.
подпрограмм
3. Разработка программы ведётся пошагово, методом «сверху вниз».
Сначала пишется текст основной программы, в котором, вместо каждого связного логического фрагмента текста, вставляется вызов подпрограммы, которая будет выполнять этот фрагмент. Вместо настоящих, работающих подпрограмм, в программу вставляются «заглушки », которые ничего не делают. Полученная программа проверяется и отлаживается. После того, как программист убедится, что подпрограммы вызываются в правильной последовательности (т.е. общая структура программы верна), подпрограммы-заглушки последовательно заменяются на реально работающие, причём разработка каждой подпрограммы ведётся тем же методом, что и основной программы. Разработка заканчивается тогда, когда не останется ни одной «заглушки», которая не была бы удалена. Такая последовательность гарантирует, что на каждом этапе разработки программист одновременно имеет дело с обозримым и понятным ему множеством фрагментов, и может быть уверен, что общая структура всех более высоких уровней программы верна. При сопровождении и внесении изменений в программу выясняется, в какие именно процедуры нужно внести изменения, и они вносятся, не затрагивая части программы, непосредственно не связанные с ними. Это позволяет гарантировать, что при внесении изменений и исправлении ошибок не выйдет из строя какая-то часть программы, находящаяся в данный момент вне зоны внимания программиста.
Следование принципам структурного программирования сделало тексты программ, даже довольно крупных, нормально читаемыми. Серьёзно облегчилось понимание программ, появилась возможность разработки программ в нормальном промышленном режиме, когда программу может без особых затруднений понять не только её автор, но и другие программисты. Это позволило разрабатывать достаточно крупные для того времени программные комплексы силами коллективов разработчиков, и сопровождать эти комплексы в течение многих лет, даже в условиях неизбежных изменений в составе персонала.
Методология структурной разработки программного обеспечения была признана «самой сильной формализацией 70-х годов». После этого слово «структурный» стало модным в отрасли, и его начали использовать везде, где надо и где не надо. Появились работы по «структурному проектированию», «структурному тестированию», «структурному дизайну» и т.д.
К достоинствам структурного программирования можно отнести следующее:
1. Структурное программирование позволяет значительно сократить число вариантов построения программы по одной и той же спецификации, что значительно снижает сложность программы и облегчает понимание её другими разработчиками.
2. В структурированных программах логически связанные операторы находятся визуально ближе, а слабо связанные — дальше, что позволяет обходиться без блок-схем и других графических форм изображения алгоритмов (по сути, сама программа является собственной блок-схемой).
3. Сильно упрощается процесс тестирования и отладки структурированных программ.
Рассмотрим более подробно основные методы структурного программирования.
1.1. Цели и принципы структурного программирования
Целями структурного программирования
Обеспечение дисциплины программирования
Улучшение читабельность программы
· избегать использования языковых конструкций с неочевидной семантикой;
· стремиться к локализации действия управляющих конструкций и использования структур данных;
· разрабатывать программу так, чтобы ее можно было читать от начала до конца без управляющих переходов на другую страницу.
Повышение эффективности программ
Повышение надежности программ
Уменьшение времени и стоимости программной разработки
принципы структурного программирования
Таблица 1.
|
Принцип |
Пояснение |
|
Абстракция |
Абстракция позволяет программисту вообразить требуемое решение проблемы без сиюминутного учета множества деталей. Программист может рассматривать программу по уровням: верхний уровень показывает большую абстракцию, упрощает взгляд на проект, в то время как нижний уровень показывает мелкие детали реализации. |
|
Формальность |
Использование при разработке программы строгого методического подхода, что является базой для превращения программирования из импровизации в инженерную дисциплину. Этот принцип дает основания для доказательства правильности программ, так как позволяет изучать программы (алгоритмы) как математические объекты. |
|
«Разделяй и властвуй» |
Разделение программы на отдельные фрагменты (модули), которые просты по управлению и допускают независимую отладку и тестирование. |
|
Иерархическое упорядочение |
Структура разбиения на части не менее важна, чем сам факт такого разделения. Этот принцип выдвигает требование иерархического структурирования взаимосвязей между модулями программного комплекса, что облегчает достижение целей структурного программирования. |
1.2. Нисходящее проектирование
Спецификация задачи служит отправной точкой в создании программы. Нужно понять, какие действия должны быть совершены для решения задачи, описать их на естественном языке и на достаточно высоком уровне абстракции.
Спецификация задачи является ее первичным проектом. От неё мы движемся к программе, постепенно уточняя описание.
методом проектирования сверху вниз
Пример 1.
Решение:
1. Первичная цель
Одеть.
2. Конкретизация цели на первом шаге
Одеть нижнюю половину.
Одеть верхнюю половину.
2.1. Нижнюю половину можно одеть в два этапа:
Надеть брюки.
Надеть носки и ботинки.
2.2. Верхнюю половину можно также одеть в два этапа:
Надеть рубашку.
Надеть куртку.
3. Окончательный проект
Надеть брюки.
Надеть носки.
Надеть ботинки.
Надеть рубашку.
Надеть куртку.
Метод нисходящего проектирования
Рис. 2.
Последовательность действий по разработке ФСА приложения следующая:
цели автоматизации
состав приложений
характер взаимосвязи
функции обработки данных
декомпозиция функций обработки
Подобная структура приложения отражает наиболее важное – состав и взаимосвязь функций обработки информации для реализации приложения, хотя и не раскрывает логику выполнения каждой отдельной функции, условия или периодичность их вызовов.
1.3. Модульное программирование
Модульное программирование
Модуль
подпрограмма
многократно используемые модули
Некоторые программные продукты используют модули из готовых библиотек стандартных подпрограмм, процедур, функций, объектов, методов обработки данных.
Среди множества модулей различают:
головной модуль
управляющий модуль
рабочие модули
сервисные модули и библиотеки
В работе программного продукта активизируются необходимые программные модули. Управляющие модули задают последовательность вызова на выполнение очередного модуля. Информационная связь модулей обеспечивается за счет использования общей базы данных либо межмодульной передачи данных через переменные обмена.
Каждый модуль может оформляться как самостоятельно хранимый файл; для функционирования программного продукта необходимо наличие программных модулей в полном составе.
свойствами
· один вход и один выход – на входе программный модуль получает определенный набор исходных данных, выполняет содержательную обработку и возвращает один набор результатных данных, т.е. реализуется стандартный принцип IPO (Input–Process–Output – вход-процесс-выход );
функциональная завершенность
логическая независимость
слабые информационные связи с другими программными модулями
обозримый по размеру и сложности программный код
Модули содержат:
· определение доступных для обработки данных;
· операции обработки данных;
· схемы взаимосвязи с другими модулями.
Спецификации
Однотипные функции реализуются одними и теми же модулями. Функция верхнего уровня обеспечивается главным модулем; он управляет выполнением нижестоящих функций, которым соответствуют подчиненные модули.
При определении набора модулей, реализующих функции конкретного алгоритма, необходимо учитывать следующее:
· каждый модуль вызывается на выполнение вышестоящим модулем и, закончив работу, возвращает управление вызвавшему его модулю;
· принятие основных решений в алгоритме выносится на максимально «высокий» по иерархии уровень;
· для использования одной и той же функции в разных местах алгоритма создается один модуль, который вызывается на выполнение по мере необходимости.
функционально-модульная схема
Состав и вид программных модулей, их назначение и характер использования в программе в значительной степени определяются инструментальными средствами.
Рис. 3.
Большинство современных программ прикладного характера, ориентированных на конечного пользователя, работают в диалоговом режиме взаимодействия с пользователем таким образом, что ведется обмен сообщениями, влияющими на обработку данных. В диалоговом режиме под воздействием пользователя осуществляются запуск функций обработки, изменение свойств объектов, производится настройка параметров выдачи информации и т.п. Диалоговый процесс управляется согласно созданному сценарию, для которого определяются:
· точки (момент, условие) начала диалога;
· инициатор диалога – человек или программный продукт;
· параметры и содержание диалога – сообщения, состав и структура меню, экранные формы и т.п.;
· реакция программного продукта на завершение диалога.
объектно-ориентированные инструментальные средства разработки программ
1.4. Структурное кодирование
структурное кодирование
Структурное кодирование
структурных операторов
структурированной
теорема о структурировании
Теорема устанавливает, что как бы сложна ни была задача, схему алгоритм ее решения (и, соответственно, программу) всегда можно представить в виде композиции трех типов вложенных блоков:
· следования (begin-end – начало-конец ),
· ветвления (if —then —else – если-то-иначе ),
· циклов с предусловием (while – пока ).
функциональной полнотой
На практике данная теорема позволяет избежать использования операторов перехода goto , что делает алгоритмы и программы наглядными и легко понимаемыми.
Виды основных управляющих структур алгоритма приведены на рис. 4.
1. Структура типа «следование »
выполнить S 1;
выполнить S 2;
…
выполнить Sn
В линейном вычислительном процессе все операции выполняются последовательно в порядке их записи. Типовым примером такого процесса является стандартная вычислительная схема, состоящая из трех этапов:
1) ввод исходных данных;
2) вычисление по формулам;
3) вывод результата.
Pascal
Begin
S
S
Sn
End
2. Структура типа «ветвление »
если Р
то выполнить S 1
иначе выполнить S 2
Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Pascal
If
Then
Else
3. Структура типа «цикл с предусловием »
до тех пор пока Р
выполнять S
Выполнение цикла прекращается, когда условие Р не выполняется.
В языке Pascal такая структура имеет следующий формат:
While
S
В расширенный комплект элементарных алгоритмических структур дополнительно входят следующие управляющие конструкции (рис. 5).
4.
если Р
то выполнить S 1
Pascal
If
Then
5
Case
1: S1;
2: S2;
…
n: Sn
Else S
End;
Структура типа « цикл с постусловием »
Pascal
Repeat
S
Until
Структура типа « цикл с параметром »
· задание начального значения используемого параметра цикла (например, если переменной цикла является i , то ей присваивается значение i 1, т.е. i :=i 1);
· выполнение действий S , предусмотренных в теле цикла;
· изменение параметра цикла, который обеспечивает вычисление результата с новыми начальными данными (например, если параметр цикла i изменяется с шагом i 3, i :=i + i 3);
· проверка текущего значения параметра цикла с заданным конечным значением (i <=i 2);
· переход к повторению тела цикла, если параметр цикла не превысил конечного значения, иначе — выполнение следующих действий или вывод результата.
Pascal
For
S
Рассматривая схему программы, можно выделить в ней части (фрагменты), достаточно простые и понятные по структуре. Представление этих фрагментов укрупненными блоками существенно облегчает восприятие алгоритма (а в дальнейшем и программы) в целом.
Структурные операторы обычно применяются уже на ранних стадиях нисходящего проектирования программы.
структурное программирование
1. Структурное программирование — методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX в. Э.Дейкстрой, разработана и дополнена Н.Виртом. Типичными методами структурного программирования являются: нисходящее проектирование (проектирование сверху вниз); модульное (процедурное) программирование; структурное кодирование.
2. Целями структурного программирования являются: обеспечение дисциплины программирования, повышение эффективности и надежности программ, уменьшение времени и стоимости программной разработки. Основные принципы структурного программирования: абстракция, формальность, «разделяй и властвуй», иерархическое упорядочение.
3. Метод нисходящего проектирования предполагает последовательное разложение общей функции обработки данных на простые функциональные элементы («сверху-вниз»).
Средства достижения целей на предыдущем уровне превращаются в цели на нижнем.
4. Структурное кодирование — это метод написания программ, имеющих определенную структуру. Он основан на использовании небольшого набора структурных операторов, правильность которых легко проанализировать и установить. При этом одни операторы состоят из других, вложенных в них.
5. Фундаментом структурного программирования является теорема о структурировании, сформулированная итальянскими математиками К.Бомом и Дж.Якопини в 1966 г. Теорема устанавливает, что как бы сложна ни была задача, схему алгоритм ее решения (и, соответственно, программу) всегда можно представить в виде композиции трех типов вложенных блоков: следования (begin-end – начало-конец), ветвления (if-then-else – если-то-иначе), циклов с предусловием (while – пока).
