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

Лекция. Анализ корректности и разрешимости концептуальной модели

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

                                                                                   

                                                                                                     

 

 

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

 

 

Содержание

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

 

1. Правила корректности  и разрешимости КМ ВП

2. Понятие процедурной спецификации и порядок ее синтеза

 

Литература

1. [8], с.75-80, 119-129.

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

1.

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

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

 

Введение

 

 

В ходе последней лекции была обоснована необходимость концептуального проектирования программного обеспечения ИС, определена структура КМ ВП и рассмотрен порядок ее построения.

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

Лекция направлена на изучение порядка  анализа КМ ВП и синтеза процедурных спецификаций.

 

 

 

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

 

1. Правила корректности  и разрешимости КМ ВП

В КМ ВП предусматривается проведение логического анализа ее корректности и разрешимости. Логический анализ классифицируется на:

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

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

Определение корректности  структур  отношений  выполняется в ходе статического анализа (рис. 1):

рис. 1.

Анализ корректности имен объектов. Для любых двух объектах модели справедливо:

"o_i, "o_j, n_o(o_i) = n_o(o_j) ® t_ho(o_i) = t_ho(o_j)  &

& "o_x , o_x Îh_o(o_i),  $o_y , o_y Îh_o(o_j)  &  n_o(o_x) = n_o(o_y).

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

Анализ корректности имен процессов. Для любых двух процессов модели справедливо:

"p_i, "p_j , n_p(p_i) = n_p(p_j) ® t_hp(p_i) = t_hp(p_j)  &

& "p_x , p_x Îh_p(p_i),  $p_y , p_y Îh_p(p_j)  & n_p(p_x) = n_p(p_y) &

& "o_x , o_x Îin(p_i),  $o_y , o_y Îin(p_j)  &  n_o(o_x) = n_o(o_y)  &

& "o_z , o_z Îout(p_i),  $o_w , o_w Îout(p_j)  &  n_o(o_z) = n_o(o_w).

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

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

Анализ корректности типов процессов. Если совпадают типы процессов, то должны совпадать типы их отношений иерархии, типы подчиненных им процессов (подпроцессов), мощности множеств однотипных подпроцессов, типы их входных и выходных объектов, а также мощности множеств однотипных входных и выходных объектов.

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

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

Анализ отношений  следования. В модели отношения следования не могут:

связывать процессы,  подчиненные  друг другу отношениями иерархии;

задаваться "перекрестно" и противоречить друг другу.

Под разрешимостью понимается возможность получения результирующих данных в КМВП путем указания исходных. Анализ разрешимости КМ ВП сводится к анализу отдельных ее элементов, называемых шаблонами.

Шаблоном КМ ВП относительно некоторого выбранного процесса p_i называется следующий набор множеств:

{p_j | p_jÎh_p(p_i)} – подчиненные p_i процессы;

{o_i | o_iÎin(p_i)} – входные объекты процесса p_i;

{o_j | o_jÎin(p_i)} – выходные объекты процесса p_i;

{o_k | o_kÎh_o(o_i), o_iÎin(p_i)} – компоненты входных объектов процесса p_i;

{o_l | o_lÎh_o(o_j), o_jÎout(p_i)} – компоненты выходных объектов процесса p_i;

{o_m | o_mÎin(p_k) V o_mÎout(p_k), p_kÎh_p(p_i)} – входные и выходные данные процессов, подчиненных p_i;

множества {o_i},{o_j},{o_k},{o_l},{o_m} могут частично пересекаться.

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

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

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

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

 

 

2. Понятие процедурной  спецификации и порядок ее  синтеза

 

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

Свойства спецификации:

Полнота спецификации означает, что ничто существенное из задачи в ней не упущено и не забыто.

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

Понятность спецификации – ясность и читабельность.

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

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

1. Для каждого процесса, связанного с подчиненными отношением "&" (рис.2) генерируется процедура, состоящая из вызовов процессов более низкого уровня.

Здесь: type_X - имя типа процесса X ;

type_Y - имя типа процесса Y;

type_Z - имя типа процесса Z .

Для случая отношения "V" генерируется условный оператор или  оператор выбора (при количестве альтернатив  больше двух) (рис.3). Здесь type_X – имя  типа процесса X, определяющее условие  выбора дальнейшего хода вычислений – инициирование процесса Y (при  выполнении данного условия) или выполнение процедуры Z (в противном случае).

Для случая итерационного отношения " " генерируется оператор цикла (рис.4):

где type_X – имя типа процесса X (t_p(X)), определяющее условие выполнения цикла.

2. Если процесс имеет  входные и выходные данные (рис. 5), то при синтезе

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

- вызова процедуры – генерируется список фактических параметров.

Здесь: type_A – имя типа инфообъекта A;

type_B – имя типа инфообъекта  B;

type_C – имя типа инфообъекта  C;

type_D – имя типа инфообъекта  D.

3. Для информационных  объектов в текст спецификации включаются описания типов и переменных. Для каждого неэлементарного данного связанного со своими компонентами отношением "&" синтезируется запись (рис. 6):

В случае отношения иерархии между объектами типа "V" синтезируется запись с вариантами (рис. 7.):

В случае итерационного  отношения (*) – синтезируется массив (рис. 8):

4. При синтезе тела  процедуры  (рис.9) последовательность  вызова составляющих это тело процедур определяется возможной последовательностью выполнения процессов:

процесс не может быть выполнен раньше, чем будут сформированы его входные данные;

процесс не может быть выполнен раньше, чем будут выполнены  предшествующие ему процессы.

Процесс Z должен выполняться  после Y, так как он использует выходной инфообъект процесса Y – инфообъект D, поэтому процедура <type_Z> вызывается после <type_Y> в теле процедуры <type_X>.