Раздел 2. Проектирование программных продуктов

Тема 2.1. Алгоритмизация

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

1.1.1.   Этапы создания программного продукта

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

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

1. Составление технического задания на разработку программы. Исходными данными для выполнения работ этого этапа являются постановка задачи и анализ рынка программных продуктов.

На этом этапе требуется:

-         разработать обобщенный алгоритм (функциональную структуру алгоритма или состав объектов);

-         выбрать платформу программы – тип операционной системы:

-         определить необходимость разработки программы, которую можно переносить на другие платформы;

-         оценить необходимость сетевого варианта работы программы;

-         определить требования к техническим средствам обработки информации.;

-         специфицировать требования к пользовательскому интерфейсу.

2. Разработка технического проекта. На данном этапе выполняется комплекс наиболее важных работ:

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

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

-         разрабатывается модульная структура алгоритма и детализированные алгоритмы отдельных модулей;

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

Работы данного этапа зависят от выбранных инструментальных средств создания программ, технологии работ.

3. Рабочий проект (рабочая документация). Данный этап является технической реализацией проектных решений. Основным содержанием работ является разработка программных модулей или методов обработки объектов (собственно программирование), их автономная и комплексная отладка на контрольном примере, испытание работоспособности программного продукта в комплексе с системными и базовыми программными средствами.

Основной результат этого этапа – создание комплекта документации на программный продукт:

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

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

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

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

1.1.2.   Структура программных продуктов

Программные продукты имеют внутреннюю структуру (внутреннюю организацию), образованную взаимосвязанными программными модулями.

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

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

Структуризация программных продуктов позволяет:

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

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

-         контролировать трудозатраты и стоимость проектных работ и др.

Среди множества модулей различают:

-         головной модуль, который управляет запуском программного продукта (существует в единственном числе);

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

-         рабочие модули, выполняющие функции обработки;

-         сервисные модули и библиотеки, утилиты, осуществляющие обслуживающие функции.

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

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

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

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

ППП – это система программ, предназначенных для решения задач определенного класса.

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

1.1.3.   Виды проектирования программных продуктов

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

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

-         информационное моделирование предметной области и связанных с ней приложений;

-         объектно-ориентированное проектирование программных продуктов.

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

Алгоритмы большой сложности обычно представляют с помощью схем двух видов:

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

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

Представителями структурного проектирования являются следующие методы:

•        нисходящее проектирование;

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

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

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

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

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

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

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

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

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

В этом подходе выделяют следующие составляющие:

-         информационный анализ предметных областей (бизнес-областей);

-         информационное моделирование – построение комплекса взаимосвязанных моделей данных;

-         системное проектирование функций обработки данных;

-         детальное конструирование процедур обработки данных.

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

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

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

-         модели построения системы как совокупности объектов абстрактного типа данных;

-         модульной структуре программ;

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

В отличие от традиционного структурного подхода, объектно-ориентированный подход к проектированию программных продуктов основан на:

-         выделении классов;

-         установлении характерных свойств классов и методов их обработки;

-         создании иерархии классов;

-         наследовании свойств классов и методов их обработки.

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

1.1.4.   Понятие алгоритма

Решение задачи при помощи ЭВМ начинается с составления алгоритма. Что же такое алгоритм?

Происхождение термина «алгоритм» связывают с именем великого математика Мухаммеда аль-Хорезми (763–850 гг.), который разработал правила выполнения четырех арифметических действий. Первоначально алгоритмами называли правила, определяющие последовательность действий для получения суммы чисел, произведения и т.д. И многие годы понятие «алгоритм» использовалось математиками для описания правил решения математических задач.

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

Согласно ГОСТ 19781-74:

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

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

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

Основные особенности алгоритмов:

1.     Наличие ввода исходных данных.

2.     Наличие вывода результата выполнения алгоритма, поскольку цель выполнения алгоритма – получение результата, имеющего вполне определенное отношение к исходным данным.

3.     Алгоритм должен иметь дискретную структуру, т.е. алгоритм представляется в виде последовательности шагов, и выполнение каждого очередного шага начинается после завершения предыдущего.

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

5.     Конечность – исполнение алгоритма должно закончиться за конечное число шагов.

6.     Корректность – алгоритм должен задавать правильное решение задачи.

7.     Массовость (общность) – алгоритм разрабатывается для решения некоторого класса задач, различающихся исходными данными.

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

1.1.4.1. Способы записи алгоритмов

Разработанный алгоритм может быть представлен несколькими способами:

1)    на естественном языке (словесная запись алгоритма);

2)    в виде блок-схем (графическая форма);

3)    на языке программирования.

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

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

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

1.1.4.2. Представление алгоритмов в виде блок-схем

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

Существует Государственный стандарт, определяющий правила создания блок-схем. Конфигурация блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19.701-90 "Схемы алгоритмов и программ". В табл. 2.1 приведены обозначения некоторых элементов, которых будет вполне достаточно для изображения алгоритмов при выполнении студенческих работ.

Правила составления блок-схем:

1.     Каждая блок-схема должна иметь блок «Начало» и один блок «Конец».

2.     «Начало» должно быть соединено с блоком «Конец» линиями потока по каждой из имеющихся на блок-схеме ветвей.

3.     В блок-схеме не должно быть блоков, кроме блока «Конец», из которых не выходит линия потока, равно как и блоков, из которых управление передается «в никуда».

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

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

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

7.     От блока «Начало» в отличие от всех остальных блоков линия потока только выходит, так как этот блок – первый в блок-схеме.

8.     Блок «Конец» имеет только вход, так как это последний блок в блок-схеме.

9.     Для простоты чтения желательно, чтобы линия потока входила в блок «Процесс» сверху, а выходила снизу.

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

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

1.1.4.3. Типы алгоритмов

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

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

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

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

Каждое из возможных направлений дальнейших действий называется ветвью.

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

Различают несколько видов разветвляющихся алгоритмов.

1. «Обход» – такое разветвление, когда одна из ветвей не содержит ни одного оператора, т.е. как бы обходит несколько действий другой ветви.

2. «Разветвление» – такой тип разветвления, когда в каждой из ветвей содержится некоторый набор действий.

3. «Множественный выбор» – особый тип разветвления, когда каждая из нескольких ветвей содержит некоторый набор действий. Выбор направления зависит от значения некоторого выражения.

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

Различают:

•        циклы с известным числом повторений (или со счетчиком);

•        циклы с неизвестным числом повторений (циклы с предусловием и циклы с постусловием).

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

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

Циклы со счетчиком

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

Блок-схема циклического алгоритма в этом случае выглядит так:

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

В дальнейшем мы будем использовать в блок-схемах для изображения цикла со счетчиком блок «Подготовка». В блоке «Подготовка» записывается счетчик цикла (I), далее последовательно указываются начальное значение (Iн), конечное значение (Iк) счетчика цикла и шаг его изменения (h). Если шаг изменения h равен 1, его можно не записывать. Желательно, чтобы линия потока входила в блок сверху, линия потока к телу цикла выходила снизу, слева (или справа) входила линия потока перехода к следующему шагу цикла, а справа (или слева) выходила линия потока – выход из цикла.

При использовании цикла со счетчиком необходимо соблюдать некоторые требования:

§  в теле цикла нельзя принудительно изменять значение счетчика цикла;

§  не разрешается передавать управление оператору тела цикла извне, т.е. вход в цикл допускается только через начало цикла.

Циклы с предусловием

Циклы с предусловием чаще всего используют тогда, когда неизвестно число повторений цикла. Циклы с предусловием – это такие циклы, в которых до начала выполнения тела цикла проверяется условие выполнения следующего шага цикла. Если значение этого условия истинно (т.е. условие выполняется), то выполняется тело цикла. В теле цикла должно изменяться значение по крайней мере одной переменной, которая влияет на значение условия (иначе произойдет «зацикливание»). Далее опять проверяется условие выполнения цикла, и если значение условия ложно, то осуществляется выход из цикла.

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

Особенность этого типа цикла в том, что тело цикла может не выполниться ни разу, если условие первоначально ложно в первом варианте (или истинно во втором).

На блок-схеме такой цикл реализуется следующей конструкцией:

Циклы с постусловием

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

На блок-схеме этот тип цикла изображается следующим образом:

Сложные циклы

Циклы, которые содержат внутри себя (в теле цикла) один или несколько других циклов, называются сложными или вложенными циклами.

При этом циклы, охватывающие другие циклы, называются внешними, а циклы, входящие во внешние, – внутренними циклами.

На каждом шаге внешнего цикла внутренний цикл «прокручивается» полностью.

Контрольные вопросы

1.     Перечислите этапы создания программного продукта.

2.     Для чего выполняется структуризация программ?

3.     Что такое модуль, какие виды модулей вы знаете?

4.     Назовите и охарактеризуйте методы структурного проектирования.

5.     На чем основывается объектно-ориентированный подход?

6.     Что такое алгоритм?

7.     Перечислите основные особенности алгоритмов.

8.     Назовите способы представления алгоритмов.

9.     Что такое блок-схема, каковы правила составления блок-схем?

10. Какой алгоритм называется линейным?

11. Перечислите виды разветвляющихся алгоритмов.

12. Какие виды циклов вы знаете?

13. Объясните работу циклов со счетчиком.

14. В чем отличие циклов с предусловием от циклов с постусловием?

15. Что такое сложные циклы?

Скачано с www.znanio.ru