Виды моделей программ и их представление в виде графов

Методология проектирования ПП

Лекция № 5

Проектирование (Functional design, Detailed design) - процесс преобразования задания на разработку (внешней спецификации) в задание на кодирование. Содержание процесса - построение, анализ и детализация моделей создаваемого ПП. Модель (в инженерном и научном смысле) - это упрощенное описание объекта или явления, в котором отражены те его свойства, которые существенны для целей его изучения или построения (от несущественных абстрагируемся!) - т.е., модель есть абстракция, и уместно говорить об уровнях абстракции. Чем выше уровень абстракции, тем более общая (краткая, обозримая), но зато и менее точная (детальная) модель. Вопрос 1.

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

Основные традиционные виды моделей:

· Функциональная структура

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

а) отношение часть-целое (отношение эквивалентности), тогда соответствующий граф - дерево иерархии ФБ

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

· Алгоритмическая (процедурная) модель

Описывает алгоритм как последовательность шагов, т.е. отношение предшествования во времени (отношение частичного порядка) ФБ. Изображается блок-схемой алгоритма (Flow Chart, или схема потока управления) или в виде псевдокода. Вопрос 3.

· Информационная модель

Ее компоненты - порции информации: структуры данных, записи, файлы и, возможно, ФБ, их обрабатывающие. Два варианта:

А) Схема потока данных (Data Flow Diagram, DFD) описывает отношения на двух множествах: порций данных и ФБ. Избражается двудольным графом; дуги – отношения двух типов: «быть входными данными» и «быть выходными данными» – одновременно заменяют собой ФБ ввода / вывода или пересылки данных.

Б) Инфологическая (информационно-логическая) модель описывает логические отношения между объектами, отображаемыми в базе данных. Чаще всего это реляционная модель или модель «сущность-связь» (Entity-Relationship, ER-model) – исходная для построения схемы базы данных.

· Событийная структура (модель состояний и переходов)

Здесь компоненты – состояния системы, отношения – переходы между ними. Изображается диаграммой состояний и переходов (State-Transition Diagram, STD), причем дуги нагружены событиями, вызывающими переходы и, возможно, другими условиями.

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

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

Ввод А

Вывод А

Сортировка- слияние

Ввод D

Ввод исходных данных

Программа пополнения словаря

Функциональная структура:

(ФБ "Сортировка-слияние" может состоять из более мелких блоков, и т.д.). Заметим, что из этой модели не очевидна последовательность выполнения компонентов, например, в данном примере порядок, в котором выполняется ввод А и D, а в более общем случае - выбор между компонентами и их повторение.

2. Алгоритмическая модель - блок-схема:

Здесь явно изображается последовательность выполнения и выбор (разветвление). Зато на одной блок-схеме трудно показать вложенность блоков "Ввод А" и "Ввод D" в блок более высокого уровня иерархии "Ввод исходных данных". Детализация, например, блока "Сортировка-слияние" возможна на другой блок-схеме. Вопрос 4. Очевидно, функциональная структура и алгоритмическая модель взаимосвязаны и взаимодополнительны. Блок-схемы нагляднее текстов (особенно для непрофессионалов), как любая графика, но устарели ввиду их громоздкости и сложности автоматической обработки. Они вытеснены псевдокодом - текстовой нотацией, где управляющие конструкции (разветвление, цикл, вызов подпрограммы и т.д.) заимствуются из языка программирования (Паскаля, Си), а содержание ФБ записывается неформально, на естественном языке, как и в блок-схемах. Существуют и специально разработанные псевдокоды, как язык PDL (Program Design Language) фирмы IBM. Наш пример: Start; Ввод файла дополнений D; If D пуст Then Stop; Ввод файла словаря А; Сортировка-слияние; Вывод файла словаря А; Stop

3. Схема потока данных:

Такая модель описывает взаимосвязь ФБ по данным: входным, выходным или общим (глобальным) переменным. Удобна для описания, например, автоматизированного документооборота в АСУ.

4. Диаграмма состояний и переходов:

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

Для различных видов ПП и их частей удобны различные виды моделей. Функциональная структура наиболее универсальна; она служит для функциональной декомпозиции проекта – расчленения на части с целью последующего разделения труда и этапности разработки. Например, в технологии Microsoft на основе внешней специ-фикации все основные функции ПП упорядочиваются по убыванию степени важности и разбиваются на 3-4 группы - подпроекты, работа над которыми будет вестись после-довательно. Каждый подпроект заканчивается выпуском промежуточной "контроль-ной" версии ПП (milestone release) в соответствии со спиральной моделью ЖЦ.

Алгоримическая модель (обычно на псевдокоде, С или Паскале) необходима для описания нетривиальных алгоритмов. Схемы потока данных лучше подходят для тех систем обработки данных, где вычисления тривиальны, а обмен – интенсивен. HIPO – технология фирмы IBM 70-х годов ("Hierarchical Input-Processing-Output”) полностью основывалась на DFD. В наши дни DFD применяются в CASE-системах проектирования корпоративных ИС: IDEF и BPwin. Интересно также применение DFD для разработки программ для суперкомпьютеров (см. Приложение; Вопрос 6.).

Модель баз данных “сущность-связь” – более общая и наглядная, чем реляционная. Она используется в популярной CASE ERwin. На рис. ниже – пример: фрагмент модели базы данных предприятия в нотации Чена. Прямоугольниками изображаются сущности, ромбами – отношения (связи).

Событийная модель удобна для описания реактивных (responsive) систем, к которым относятся системы реального времени и диалоговые программы. В них состояния соответствуют приостановке вычислений в ожидании некоторого события, вызывающего переход в другое состояние - в зависимости от вида события. Windows и другие ОС с оконным интерфейсом построены по такой модели и поэтому называются системами, продвигаемыми событиями (event-driven systems). Проекты сложных ПП обычно требуют описания несколькими видами моделей, взаимно дополняющими друг друга, и именно таков подход UML. (Многомодельность вообще характерна для описания сложных систем.) Однако смешение средств разных видов в одной модели недопустимо.