7108

СТРУКТУРНОЕ ПРОЕКТИРОВАНИЕ И ПРОГРАММИРОВАНИЕ

Практическая работа

Информатика, кибернетика и программирование

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

Русский

2013-01-16

99.72 KB

42 чел.

СТРУКТУРНОЕ ПРОЕКТИРОВАНИЕ И ПРОГРАММИРОВАНИЕ

Нисходящее проектирование *

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

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

  1.  определяются цели автоматизации предметной области и их иерар
    хия
    (цель-подцель);
  2.  устанавливается состав приложений (задач обработки), обеспечи
    вающих реализацию поставленных целей;
  3.  уточняется характер взаимосвязи приложений и их основные харак
    теристики (информация для решения задач, время и периодичность реше
    ния, условия выполнения);
  4.  определяются необходимые для решения задач функции обработки
    данных;
  5.  выполняется декомпозиция функций обработки до необходимой
    структурной сложности.

Функциональная структура приложений.

Цель 

Ц: 

1 

1 

Подцели 

пЦ 

1 

n4is 

1 

Приложения 

п, 

П2 

Пп 

1 

Функции 

Ф1 

Ф2 

Фгг 

1                          1 

Фгг 

ll 

Фт2                          Фтр 


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

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

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

Структурное программирование включает три составляющие: проектирование сверх}' - вниз или нисходящее проектирование программ; модульное программирование и структурное программирование.

Нисходящее проектирование программ

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

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

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

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

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

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

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

Модульное программирование

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

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

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

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

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

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

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

Структурное кодирование

Третьим составным элементом структурного программирования является структурное кодирование, которое представляет собой метод написания хорошо структурированных программных модулей, удобных для тестирования, модификации и использования. Метод предусматривает написание программных модулей произвольного размера и сложности на основе ограниченного множества базисных логических структур. Метод аналогичен принципу, положенном}' в основу проектирования схем, где любая логическая структура может быть создана из элементарных структур И, ИЛИ и НЕ. Структурное кодирование базируется на строго доказанной теореме о структурировании, которая утверждает, что любую правильную программ}' (с одним входом и одним выходом, без зацикливаний и недостижимых команд) можно написать с использованием следующих логических структур: последовательности двух или более операторов; выбора одного из двух операторов (IF THEN, ELSE); повторения (или управления циклом) оператора, пока выполняется некоторое условие (DO WHILE).

а)

б)


L 

•'•v 

Программа, следующая за h, которой не было е исходной программе, присваивает значение j для новой переменной L (программному счетчику). Далее, для каждого предикатного узла с номером, например, /

составим новую программу gi типа ifthenelse

Теперь построим инициированную программу типа whiledo с дополнительной частью в виде вложенной структуры ifthenelse, проверяющей значения L от 1 до п. Каждая выходная линия ifflienelse, соответствующая значению истина, соединяется с узлом g-b являющимся функциональным или предикатным узлом исходной программы.

Чтение структурированных программ

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


Цель чтения программ

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

Существуют две основные причины для чтения программ: 1) верификация правильности реализации программой заданной функции и 2) установление программной функции программы. Верификация программы позволяет получить рецензию на проект относительно корректности последнего. Такую рецензию можно использовать для выявления других качеств проекта, помимо его корректности, таких, как эффективность и соответствие требованиям реализуемости. Определение программной функции включает «распознавание» проекта, которое является наиболее трудной частью анализа незнакомой программы или нахождения наиболее простых путей ее модификации.

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

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

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

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

Чтение элементарных программ

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

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

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

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

Чтение путем поэтапного абстрагирования

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

j' ~7 >-\_ .... -,-...   •         ,   ...

Логические комментарии в структурированных программах

В язык PDL вводятся логические комментарии, которые можно рассматривать как усовершенствованные обычные комментарии, используемыми в программах. Логические комментарии документируют все детали проекта программы, организуя их в иерархию абстракций. Используемые принципы чтения программ были получены, исходя их алгебраических свойств программы. Место в программе и назначение логических комментариев хорошо определяются этими алгебраическими свойствами, а их содержание соответствует результатам чтения н абстрагирования элементарных программ. Затруднения, возникающие при чтении плохо документированных программ, объясняются отсутствием логических комментариев; в тех же случаях, когда такие логические комментарии имеются, чтение программы сводится к проверке их правильности и улучшению там, где это возможно.

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

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

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

Y

Стратегии программирования         , .   -_

'•а.' _\

Программирование на основе принципа пошагового совершенствования

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

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

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

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

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

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

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

Программирование с использованием принципа пошаговой реорганизации

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

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

1. Пошаговое совершенствование

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

2. Пошаговая реорганизация

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


Эквивалентность программ

Понятие эквивалентности программ играет важную роль при упрощении повторяющихся структур. Существуют два вида эквивалентности программ. Если две программы имеют тождественные деревья, то они эквивалентны по выполнению, если же они имеют тождественные программные функции, то они функционально эквивалентны. Например, программы


эквивалентны по выполнению, в то время как программы

функционально эквивалентны, но не эквивалентны по выполнению. Эквивалентность по выполнению предполагает функциональную эквивалентность, но не наоборот.

Элементарные программы

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

>


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

Составные программы

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

Составные программы могут быть определены как программы произвольного размера, но ограниченной сложности, гак как элементарные программы выбираются из фиксированного базисного множества. Каждое базисное множество элементарных программ позволяет создавать конкретный класс составных программ, являющихся подмножеством всех возможных простых программ. Например, множество {последовательность ifthenelse} дает возможность сформировать класс программ без циклов, а множество {ifthenelse, whuedo) приводит к классу программ, деревья выполнения которых содержат на любом пути не более одного классов составных программ являются подмножествами других. Например, множество {последовательность dountu) позволяет создавать подмножество программ, формируемых множеством (последовательность, ifthen, whuedo).

Структурированной программой, называется составная программа, сформированная на основе фиксированного базисного множества.

Теорема о структурировании

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

Теорема о структурировании: Любая простая программа функциональна эквивалентна структурированной программе, составленной из элементов базисного множества (последовательность, ifthenelse, whuedo} с использованием функции и предикатов исходной программы, а также присваиваний и тестов над дополнительным счетчиком.

составим новую последовательную программ;/ gi (с номером входной линии /):

Доказательство: Рассмотрим произвольную простую программу с произвольным числом функциональных и предикатных узлов 1, 2, ..., п, начршающуюся с первого узла, инцидентного входной линии. (Если входной линии инцидентны один или несколько узлов слияния, то следует двигаться вдоль их выходных линий до тех пор, пока не встретится первый функциональный или предикатный узел). Дадим для выходной линии программы номер 0. Теперь присвоим выходным линиям каждого функционального и предикатного узла, если последние имеются, а в противном случае (т. е. при достижении выходной линии) припишем номер 0. Далее для каждого функционального узла исходной программы, имеющего, например, номер / (функция Л) и выходную линию,/

 


>

 

На рисунке показаны основные логические структуры: последовательности (а), выбора (6), повторения (в). Каждая структура имеет один вход и один выход. Комбинации правильных программ, полученные с использованием трех основных логических структур, также являются правильными программами. При использовании только указанных структур отпадает необходимость в безусловных переходах и метках. Применение структурного кодирования в значительной степени уменьшает сложность программ. Существенным моментом является то, что при замене любого функционального блока в схеме правильной программы на любую из трех основных логических структур программа остается е классе правильных программ. При структурном кодировании структура последовательности формализует тот факт, что операторы программы выполняются в порядке их появления, структура выбора -выбор одного из двух действий исходя из выполнения некоторого условия (оператор IF THEN, ELSE), структура повторения - выполнение группы операторов до тех пор, пока выполняется некоторое условие (оператор DO WHILE или итеративный DO).

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

Таким образом, чтобы получить структурированную программу, следует избегагь операторов GO TO. Каждый программный модуль должен состоять из последовательности операторов IF, WHEN, ELSE, циклов или операторов CASE. В случае, если язык не имеет достаточного количества языковых конструкций для структурного программирования (ФОРТРАН, КОБОЛ), рекомендуется применять операторы GO TO только для переходов вперед и там, где возможно заменять их операторами CALL или PERFORM. В языках ПЛ/1 и АЛГОЛ имеется большая часть рекомендованных конструкций, что позволяет легко писать структурированные программы.

Язык проектирования программ PDL    <- '   '

Разработка и модернизация больших систем могут затянуться на месяцы, годы или даже десятилетня. В течение этого времени требуется эффективное взаимодействие разработчиков и пользователей с целью выяснения предполагаемой и действительной структур системы и ее работоспособности. В таких случаях помогают описания, сделанные на естественном языке, но этот язык не позволяет представить в структурированной форме функции системы и их взаимосвязь. В то же время языки программирования часто обеспечивают требуемую форму описания системы только с помощью однообразных выразительных средств низкого уровня, так что общие концепции проектирования растворяются в массе деталей. Кроме того, языки гфогрзммироЕания имеют специальный синтаксис н ориентированны на определенные применения, чего, вообще говоря, хотелось бы избежать на этапе проектирования. Таким образом, имеется насущная потребность в языке (который был бы пригоден как для специалистов по разработке программного обеспечения, так н для неспециалистов) для создания и описания в определенных терминах проектов программного обеспечения. Такой язык должен быть способен выразить идеи проектирования на всех этапах разработки системы, начиная с описания системы на высоком уровне, затем на промежуточном уровне - уровне операций - н, возможно, даже на более низком уровне, если такая необходимость возникнет. Язык должен обеспечивать проектирование управляющей логики и структуры данных, а также запись комментариев. Проекты программ, записанные на этом языке, должны быть простыми в обращении. Для всех этих целей вводится множество соглашений, позволяющих представить проекты программного обеспечения в текстовой форме. Эти соглашения определяет язык проектирования программ Process Design Language, сокращенно называемый PDL. Язык PDL - это не полностью формализованный, доступный для понимания специализированный язык, включающий особенности естественного языка и правил написания математических формул. Он позволяет описывать проекты программного обеспечения с точки зрения их логики, без учета специфики конкретной вычислительной системы и расположения программ в физической памяти. Структуры языка PDL облегчают разработку системы и программы. Этот язык способствует установлению лучшего понимания между людьми в процессе разработки больших программ и допускает почти прямую гранслящло на традиционные языки программирования, а также позволяет разработать руководства для пользователей и операторов и другие документы, доступные для изучения.

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

Внешний синтаксис языка PDL для описания управляющих структур включает:

последовательные структуры

последовательность

индексную последовательность (типа fordo) развлетвляющнеся структуры

ifthenelse

ifthen

структуры выбора (типа case) циклические структуры

whiledo dounbl dowMedo

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

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

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

Выполнение структурированных программ

Простые программы

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

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

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


Схемы и деревья выполнения

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

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

  1.  Начать создание с входной линии и связанного с ней предикатного,
    функционального узла или узла слияния блок-схемы программы.
  2.  На каждом шаге построения рассматривать каждый путь выполнения
    (ориентированная цепь из линий и узлов, инцидентная входной
    линии) в Е - схеме. Если рассматриваемый путь выполнения
    заканчивается непосредственно функциональным, предикатным
    узлом или узлом слияния, ранее не входившим в этот путь, то все
    выходные линии таких узлов (из блок - схемы) и узлы, с которыми
    эти линии соединены, если таковые имеются, включить в пути
    выполнения.
  3.  Формирование Е-схемы считать законченным, если все пути
    выполнения оканчиваются выходными линиями или узлами.

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

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

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

ФьФ2 неразложимы на составляющие: они предполагают непосредственную программную реализацию. Фт представлены в виде структурного объединения более простых функций. Для всех функций-компонентов осуществляется самостоятельная программная реализация; составные функции Фт реализуются как программные модули, управляющие функциями-компонентами.

t МОДУЛЬНОЕ ПРОГРАММИРОВАНИЕ

Модуль характеризуют:

  1.  один вход и один выход — на входе программный модуль получает
    определенный набор исходных данных, выполняет содержательную обра
    ботку и возвращает один набор результатных данных;
  2.  функциональная завершенность — модуль выполняет ряд операций
    для реализации каждой отдельной функции;
  3.  логическая независимость — результат работы программного моду
    ля зависит только от исходных данных, но не зависит от работы других
    модулей;
  4.  слабые информационные связи с другими программными модулями;
  5.  обозримый по размеру и сложности программный элемент.
    Каждый модуль состоит из спецификации и тела.
    Спецификации оп
    ределяют правила использования модуля, а
    тело — способ реализации
    процесса обработки.

Модульная структура программных продуктов

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

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

Функционально-модульная структура приложения

Модуль 2

 Фт

Модуль k

JL

 Фх

Модуль V 

 

Модуль 3

 Модуль п

_L

Модуль Р

 Модуль 3

 Модуль Р

 Модуль t


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

Состав и вид программных модулей их назначение и характер использования зависят от инструментальных средств. Например, если отнести к средствам СУБД, отдельными модулями могут быть экранные формы, отчеты, макросы, меню. Алгоритмы большой сложности обычно представляются в виде схем двух типов: обобщенная схема алгоритма и детальная схема алгоритма (содержание каждого элемента с использованием управляющих структур в блок-схемах алгоритма, псевдокодах или алгоритмических языков высокого уровня).

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

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

Типы управляющих структур

1) Последовательность

С

Начало

 Применение управляющей структуры

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

Действие 1

Действие 2

С

 Конец

 

2) Альтернатива

 В блоке Условие содержится условие выбора альтернативы обработки. Каждая альтернатива выполняется 1 раз. Развитием данного типа структуры является множественная альтернатива, когда последовательно проверяются условия выполнения определенных альтернатив. Если очередное условие истинно, обрабатывается соответствующая ему альтернатива, после чего происходит выход. В противном случае — переход к проверке условия следующей альтернативы.

Если ни одно из условий не выполнилось,
происходит выход.


3) Цикл

 В блоке Условие задается условие тела цикла. Тело цикла - произвольная последовательность блоков обработки.


ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОЕКТИРОВАНИЕ Основные понятия объектно-ориентированного проектирования

Метод объектно-ориентированного проектирования основывается на:

  1.  модели построения системы как совокупности объектов абстрактного
    типа данных;
  2.  модульной структуре программ;
  3.  нисходящем проектировании, используемом при выделении объектов.
    Понятия:

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

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

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

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

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

Соотношение основных понятий ОО подхода.

об W об W об  1     -объекты

- свойства

- методы обработки

 


В объектно-ориентированном программировании используется следующий формат записи работы с объектами: ОБЪЕКТ. МЕТОД   и    ОБЪЕКТ. СВОЙСТВО.МЕТОД


 

А также другие работы, которые могут Вас заинтересовать

82232. Тільки пам’ять не сивіє... До річниці Великої Перемоги 213 KB
  Що закарбувалося в нашій пам’яті пам’яті наших батьків дідів і прадідів Революції політ людини в космос Чорнобильська катастрофа Друга світова війна і проголошення незалежності України І радісні і сумні події. Але однією з найбільших трагедій була є і залишається війна.
82233. Вода – основа жизни 55 KB
  Развивать логическое мышление умение делать вводы. Храни природу человек Жизнь в озере и в океане Покой прудов течение рек Глоток воды в своем стакане 3 ведущий В декабре 1922 года Генеральная Ассамблея ООН объявила 22 марта Всемирным днем водных ресурсов.
82234. Wir lesen gern. Ми охоче читаємо 38.5 KB
  Мета: Узагальнення та систематизація знань учнів, навчання монологічного та діалогічного мовлення в межах даної теми, тренування навичок аудіювання, навчання виразному читанню та віршованому перекладу поезії класиків німецької літератури. Розвивати мовленнєві, інтелектуальні та пізнавальні здібності учнів.
82235. Социально-гуманитарные науки (СГН) как феномен, зародившийся на Западе, его общечеловеческое значение 34.93 KB
  Предпосылки науки создавались в древневосточных цивилизациях Египте Вавилоне Индии Китае Древней Греции в форме эмпирических знаний о природе и обществе в виде отдельных элементов зачатков астрономии этики логики математики и др. а в тех реальных общественноисторических социокультурных факторах которые еще не создали объективных условий для формирования науки как особой системы знания своеобразного духовного феномена и социального института в этом целостном триединстве . Таким образом в античный и средневековый периоды...
82236. Субъект, объект и предмет познания в социально-гуманитарных науках. Проблема межпредметных связей 48.72 KB
  Субъект социально-гуманитарного познания это специально подготовленный ученый или группа ученых которые изучают различные сферы общества продукты духовной деятельности человека. В социально-гуманитарных науках субъект всегда включен в объект исследования в его познавательной деятельности всегда присутствует как рациональные так и бессознательные моменты познания. Субъект в социально-гуманитарных науках играет огромную роль так как он определяет: предмет и методы исследования способы интерпретации полученного знания объективность и...
82237. Науки о природе и науки об обществе (их сходства и отличия): современные трактовки и проблемы 39.22 KB
  Шаги в развитии проблемы классификации наук предпринятые в частности Вильгельмом Дильтеем 1833-1911 привели к отделению наук о духе и наук о природе. В работе Введение в науки о духе философ различает их прежде всего по предмету. Предмет наук о природе составляют внешние по отношению к человеку явления.
82238. Конвергенция естественнонаучного и социально – гуманитарного знания в неклассической науке, эволюция и механизмы взаимодействия 42.89 KB
  Представители философия жизни Дильтей Ницше Зиммель Бергсон утверждают что жизнь – первичная реальность органический прцесс для познания которого нужны интуиция понимание вживание вчувствование. Предмет социального познания – культурно значимая индивидуальная действительность. Признается возможность объективного познания культурноисторических и соц явлений. Соцгум познание признается частным видом научного познания подчиняющимся общим научным закономерностям.
82239. Применение общенаучных достижений в социально-гуманитарном познании. Междисциплинарные связи и научная картина мира в социально-гуманитарных науках 34.93 KB
  Социальногуманитарные науки как и наука в целом всегда создают целостные картины общества. Научная картина общества – это целостная система знаний которая объясняет основные законы возникновения и существования окружающей социальной действительности и систематизирует конкретные знания полученные в различных областях социальногуманитарных наук. Она представляет собой своеобразную модель общества включающую в себя общие понятия принципы гипотезы прежде всего обществознания которые сформулированы в терминах обыденного языка и...
82240. Индивидуальный и коллективный субъекты, формы их существования. Включённость сознания субъекта, его системы ценностей и интересов в объект исследования СГН 40.74 KB
  Означает ли сказанное что мы должны признать футбольную команду самостоятельным субъектом деятельности И не означает ли такое признание что мы приписываем собственную деятельность ее сознательно или стихийно сложившиеся надындивидуальные условия регулятивные механизмы и результаты некоему мифологическому субъекту вполне подобному Абсолютной Идее Гегеля действующей посредством живых людей Такова например позиция Э.Если мы не хотим впасть в какуюто туманную мистику или мифологию в понимании общества то можно ли вообще видеть в нем...