Теоретическое исследование моделей программы, решающей заданную задачу

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

Размещено на

Федеральное агентство связи

Сибирский государственный университет телекоммуникаций и информатики

Пояснительная записка к курсовой работе по дисциплине: “Теория вычислительных процессов”

на тему: “Теоретическое исследование моделей программы, решающей заданную задачу”

Задание к курсовой работе

Написать программу решения задачи, номер которой совпадает с номером в журнале (вариант №5).

Составить и исследовать ССП в линейной и графовой формах.

Указать интерпретацию ССП и составить протокол выполнения программы.

Построить и исследовать инварианты и ограничения цикла(ов).

Доказать частичную и полную правильность программы.

Представить схему программы в виде сети Петри и осуществить анализ ее свойств на основе дерева достижимости.

Задача к курсовой работе

Вариант 5

Задано множество прямых на плоскости (коэффициентами своих уравнений). Подсчитать количество точек пересечения этих прямых.

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

Базис класса стандартных схем программ.

Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы.

Базис класса фиксирует символы, из которых строятся схемы, указывает их роль (переменные, функциональные символы и др.), задает вид выражений и операторов схем.

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

Множества символов полного базиса:

Х = x, х1, х2..., у, у1 у2..., z, z1, z2... - множество символов, называемых переменными;

F = f(0), f(1), f(2)..., g(0), g(1), g(2)..., h(0), h(1), h(2)...- множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c...;

Р = р(0), р(1), р(2)...; q(0), q(1), q(2)...; - множество предикатных символов; р(0), q(0) - ; нульместные символы называют логическими константами;

start, stop, ...,:= ит. д.- множество специальных символов.

Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам:

односимвольные слова, состоящие из переменных или констант, являются термами;

слово ф вида f(n)(ф1, ф2...фn), где ф1, ф2...фn - термы, является термом;

те и только те слова, о которых говорится в п.п. 1,2, являются термами.

Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a)).

Тестами (логическими выражениями) называются логические константы и слова вида р(n)(ф1, ф2,...,фn). Примеры: p(0), p(0)(х), g(3)(x, y, z), p(2) (f(2(x, y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.

Множество операторов включает пять типов:

начальный оператор - слово вида start(х1, х2...хк), где k ?0, а х1, х2...хк - переменные, называемые результатом этого оператора;

заключительный оператор - слово вида stop(ф1, ф2...фn), где n ?0, а ф1, ф2...фn - термы; вхождения переменных в термы ф называются аргументами этого оператора;

оператор присваивания - слово вида х := ф, где х - переменная (результат оператора), а ф - терм; вхождения переменных в термы называются аргументами этого оператора;

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

оператор петли - односимвольное слово loop.

Среди операторов присваивания выделим случаи: когда ф - переменная, то оператор называется пересылкой (х:=у) и когда ф - константа, то оператор называется засылкой (х:=а).

Подклассы используют ограниченные базисы. Так, например, подкласс У1 имеет базис:

х1, х2, а, f(1), p(1),start,stop, (,),:=, ,и множество операторов start(х1, х2); х1:=f(x1), x2=f(x2), x1:=а, х2:=а, р(х1), р(х2), stop(х1,х2), т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.[1]

Графовая форма стандартной схемы

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

Стандартной схемой в базисе В называется конечный (размеченный ориентированный) граф без свободных дуг и с вершинами следующих пяти видов:

Начальная вершина (ровно одна) помечена начальным о1ператором. Из нее выходит ровно одна дуга. Нет дуг, ведущих к начальной вершине.

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

Вершина-преобразователь. Помечена оператором присваивания. Из нее выходит ровно одна дуга.

Вершина-распознаватель. Помечена условным оператором (называемым условием данной вершины). Из нее выходит ровно две дуги, помеченные 1 (левая) и 0 (правая).

Вершина-петля. Помечена оператором петли. Из нее не выходит ни одной дуги.

Конечное множество переменных схемы S составляют ее память ХS.

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

Вершины именуются (метки вершины) целым неотрицательным числом (0, 1, 2...). Начальная вершина всегда помечается меткой 0.

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

Вершины изображены прямоугольниками, а вершина-распознаватель - овалом. Операторы записаны внутри вершины. [1]

Линейная форма стандартной схемы

Для использования линейной формы СПП множество специальных символов расширим дополнительными символами :,goto, if, then, else. СПП в линейной форме представляет собой последовательность инструкций, которая строится следующим образом:

если выходная дуга начальной вершины с оператором start(х1,..., хn) ведет к вершине с меткой L, то начальной вершине соответствует инструкция:

0: start(х1,..., хn) goto L;

если вершина схемы S с меткой L - преобразователь с оператором присваивания х:=ф, выходная дуга которого ведет к вершине с меткой L1, то этому преобразователю соответствует инструкция:

L: x: =фgotoL1;

если вершина с меткой L - заключительная вершина с оператором stop(ф1,...фm), то ей соответствует инструкция

L:stop(ф1,..., фm);

если вершина с меткой L - распознаватель с условием р(ф1,...фk), причем 1-дуга ведет к вершине с меткой L1, а 0-дуга - к вершине с меткой L0, то этому распознавателю соответствует инструкция

L: if р(ф1,...фk) then L1 else L0;

если вершина с меткой L - петля, то ей соответствует инструкция

L: loop. [1]

Интерпретация стандартных схем программ

ССП не является записью алгоритма, поэтому позволяет исследовать только структурные свойства программ, но не семантику вычислений. При построении «семантической» теории схем программ вводится понятие интерпретация ССП. Определим это понятие.

Пусть в некотором базисе В определен класс ССП. Интерпретацией базиса В в области интерпретации D называется функция I, которая сопоставляет:

каждой переменной х из базиса В - некоторый элемент d = I(x) из области интерпретации D;

каждой константе а из базиса В - некоторый элемент d = I(а) из области интерпретации D;

каждому функциональному символу f(n) - всюду определенную функцию F(n)=I(f(n));

каждой логической константе р(0) - один символ множества 0,1 ;

каждому предикатному символу р(n) - всюду определенный предикат P(n) = I(p(n)).

Пара (S,I) называется интерпретированной стандартной схемой (ИСС), или стандартной программой(СП).

Определим понятие выполнения программы.

Состоянием памяти программы (S,I) называют функцию W: XS D, которая каждой переменной x из памяти схемы S сопоставляет элемент W(x) из области интерпретации D.

Значение терма ф при интерпретации I и состоянии памяти W (обозначим фI(W)) определяется следующим образом:

1) если ф=х, x - переменная, то фI(W) = W(x);

2) если ф=a, a - константа, то фI(W) = I(a);

3) если ф=f(n)(ф1, ф2..., фn), то фI(W)= I(f(n))(ф1I(W), ф2I(W),..., фnI(W)).

Аналогично определяется значение теста при интерпретации I и состоянии памяти W или I(W): если =р(n)(ф1, ф2..., фn), то I(W)= I(p(n))(ф1I(W), ф2I(W),... фnI(W)), n ?0.

Конфигурацией программы называют пару U=(L,W), где L - метка вершины схемы S, а W - состояние ее памяти. Выполнение программы описывается конечной или бесконечной последовательностей конфигураций, которую называют про...