Лекции по "Информационному технологии"

Лекция. Общие сведения о концептуальной модели

вычислительных процессов

                                                                                   

                                                                                                      Лекция № 7

 

 

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

 

 

Содержание

(Программные  вопросы лекции)

 

1. Формальное определение  концептуальной модели вычислительных  процессов

2. Модель атрибутов КМ ВП

3. Обобщенный алгоритм формирования КМ ВП

 

Литература

1. [8], с.33-74.

Учебно-материальное обеспечение

1.

Организационно-методические указания

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

 

Введение

 

 

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

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

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

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

Вопросы КП ВП рассматриваются  в ходе изучения данной темы.

Лекция направлена на изучение основ построения КМ ВП, структуры модели и правил согласованности ее элементов.

 

 

 

Учебные вопросы

 

1. Формальное  определение концептуальной модели  вычислительных процессов

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

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

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

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

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

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

В качестве теоретической основы математической модели языка применяется аксиоматическая теория множеств.

КМ ВП включает:

множества процессов и объектов модели;

отношения, задаваемые над множествами  элементов модели;

множества атрибутов элементов  модели;

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

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

Схема вычислительного процесса (S_ВП) определяется следующим кортежем множеств:

,

где P={p_i} – множество процессов обработки информации;

O={o_i} – множество информационных объектов ;

H={H_p, H_o} – отношения иерархии:

 – отношения иерархии процессов;

 – отношения иерархии инфообъектов;

Q = {In, Out} – отношения  взаимодействия;

 – отношения входные инфообъекты  процесса процесс;

 – отношения процесс –  выходные инфообъекты процесса;

 – отношения следования процессов.

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

Описываемые в S_ВП отношения (H, Q, S) устанавливаются между некоторым процессом (объектом) и некоторым подмножеством множеств P и O (элементом B(P), B(O), где B - булеан).

Булеаном множества D (B(D)) называется множество всех допустимых подмножеств (включая D и "пустое" Æ) множества D.

Пример: D={1, 2, 3}. B(D)={{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3},Æ}

|B(D)|=2ⁿ, где n = |D|.

Отношения иерархии H_p, H_o устанавливают соответствие между отдельными процессами (объектами) и множествами подчиненных им процессов (объектов). Отношения иерархии удобно представлять в форме функциональных отображений:

где p_i – суперпроцесс;

{p_j} – множество подчиненных p_i процессов;

o_i – информационный суперобъект;

{o_j} – множество подчиненных o_i объектов.

Запись вида: говорит о том, что процесс p_j принадлежит множеству процессов, подчиненных процессу p_i.

Аналогично для  .

Отношения взаимодействия Q позволяют определить входные и выходные инфообъекты процессов:

где {o_i} – совокупность входных, а {o_j} – совокупность выходных инфообъектов процесса p_i.

Каждой тройке <входные  объекты процесса, процесс, выходные объекты процесса> может быть поставлено в соответствие предложение следующего вида:

которое рассматривается  как:

аксиома вычислимости для  процессов самого нижнего уровня иерархии ;

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

Отношения следования S задают частичный порядок выполнения процессов:

,

где {p_i} – множество процессов, которые обязательно должны быть выполнены перед запуском процесса .

 

2. Модель атрибутов  КМ ВП

С элементами КМ ВП (процессами и объектами) связана модель атрибутов А_ВП:

А_ВП  = <N_p, T_p, N_o, T_o, T_h>,

где: N_p – множество имен процессов и функция ;

T_p – множество имен типов процессов и функция ;

N_o – множество имен объектов и функция ;

T_o – множество имен типов объектов и функция ;

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

Имена процессов (N_p) (словосочетание с указанием действия путем использования глагола в повелительном наклонении) и объектов (N_o) отражают соответственно смысл выполняемых процессом действий, назначение (роль) инфообъекта в ходе решения задач, описываемых моделью. Например, "Собрать данные по штурманской службе", "Сведения о ЛА" и т.д. В спецификации имена являются комментарием.

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

Тип процесса (определяемый именем из T_p) указывает на метод, алгоритм реализации процесса и в спецификации (в зависимости от типа отношения иерархии T_h ) будет являться именем процедуры, условием выбора или условием завершения цикла.

Имя типа объекта (из множества T_o) играет роль, аналогичную типам в языках программирования высокого уровня, указывает на структуру, форму представления объекта, применимость (годность) объекта к процедуре (процессу) обработки. С учетом типа отношения иерархии T_o в спецификации формируются структуры данных типа: RECORD, CASE, ARRAY.

Отношения иерархии, связываемые  с процессами и объектами, позволяют  расширять описательные возможности  модели и определять такие отношения, как "процесс – подпроцессы" ("объект – компоненты объекта"); "процесс –варианты процесса" ("объект – варианты представления объекта"); "итеративный процесс – тело процесса" ("множество однотипных элементов – элемент множества").

Рассмотрим интерпретацию  каждого из указанных в T_h типов иерархических отношений.

Отношение "&" –  композиция [t_hp(p_i)=&, t_ho(o_i)=&] может рассматриваться как построение абстрактного объекта агрегацией его элементов.

Для некоторого p_i при t_hp(p_i)=& выполнение состоит в выполнении всех p_j таких, что . Иначе говоря, выполнение процесса, связанного с подчиненными иерархическим отношением типа композиция, требует выполнения всех его подпроцессов (рис.1).

Аналогично для инфообъектов (рис.2), преобразуемых в процессе: объект o_i при t_ho(o_i)=& определен, если определен каждый из детализирующих его j-ых компонентов, .

Отношение "V" – классификация [t_hp(p_i)=V, t_ho(o_i)=V] указывает на то, что понятие верхнего уровня есть обобщение для группы понятий нижнего.

Выполнение некоторого процесса p_i при t_hp(p_i)=V состоит в выполнении хотя бы одного из подчиненных ему процессов . Имя типа корневого процесса должно отражать условие выбора варианта реализации. Например, процесс "Определить тип аварийной ситуации" реализован, если выполнен один из его подпроцессов: "Записать объективную информацию", "Получить информацию о ЛА, требующих посадку" (рис. 3а)

Рис. 3.

Для информационных объектов: некоторый o_i при t_ho(o_i)=V считается определенным, если определен хотя бы один из подчиненных ему объектов . Объект "Полетное задание" определен, если существует хотя бы один из его составляющих: "Планируемое полетное задание" или "Фактическое полетное задание ".

Отношение "*" – итерация [t_hp(p_i)=*, t_ho(o_i)=*] позволяет определять в схеме вычислительного процесса итеративные процессы и описывать регулярные композиции информационных объектов. Интерпретация отношений итерации заключается в следующем.

Для некоторого p_i при t_hp(p_i)=* выполнение состоит в повторении всех неопределенное или заданное количество раз. Для итерационных иерархических отношений могут задаваться пороговые значения числа повторений, которые будут использоваться в ходе количественной оценки проекта: , где N – множество натуральных чисел.

Информационному объекту o_i, для которого определен способ декомпозиции типа t_ho(o_i)=*, при реализации может быть поставлена в соответствие любая регулярная структура данных. При данном типе иерархии информационному объекту может быть поставлено в соответствие максимальное количество элементов n, т.е. , воспринимается как максимальное количество компонентов в регулярной среде данных.

 

3. Обобщенный  алгоритм формирования КМ ВП

 

Схему формирования модели по шагам (в общем виде) можно представить следующим образом:

ШАГ 1. {p_j}=h_p(p_i) – декомпозиция суперпроцесса p_i на подпроцессы {p_j}.

ШАГ 2. , in(p_j)={o_k}, out(p_j)={o_l} – определение входных и выходных данных (инфообъектов) для всех подпроцессов.

ШАГ 3. {o_i}, {o_j} – определение суперобъектов (суперданных) верхнего уровня.

ШАГ 4. {o_i}=in(p_i), {o_j}=out(p_i) – определение отношений взаимодействия между суперпроцессами и суперданными.

ШАГ 5. Статический анализ модели (анализ корректности).

ШАГ 6. Динамический анализ модели (разрешимость моделируемой задачи).