Математическая модель программы

Описание математической модели мы начнем с нескольких вспомогательных определений.

Переменные программы

Каждая программа работает с конечным числом переменных. Переменные разделяются на три типа: входные, промежуточные и выходные. Вектора этих переменных мы будем обозначать соответственно \(\mathbf{x} = (x_1, x_2, \ldots, x_a)\), \(\mathbf{y} = (y_1, y_2, \ldots, y_b)\) и \(\mathbf{z} = (z_1, z_2, \ldots, z_c)\). Входные переменные содержат исходные входные значение и никогда не меняются во время работы программы. Промежуточные переменные используются для хранения промежуточных результатов в процессе вычисления. Выходные переменные содержат значения, вычисляемые данной программой. Далее, если не будет сказано специально, входные переменные будем обозначать как \(x_1, x_2, \ldots\), промежуточные как \(y_1, y_2, \ldots\), выходные как \(z_1, z_2, \ldots\).

Каждая переменная \(v\) может принимать значения из некоторого множества \(\mbox{D}_v\), которое называется доменом переменной. Также, мы будем выделять три непустых домена:

Множество значений всех возможных переменных образует универсальный домен \(\mbox{D}\). Это значит, что для любой переменной \(v\) выполнено соотношение: \(\mbox{D}_v \subseteq \mbox{D}\). Кроме того, мы выделим два специальных значения: \(\mbox{Т}\) (истина) и \(\mbox{F}\) (ложь). Функции, принимающие значения только из множества \(\{\mbox{Т}, \mbox{F}\}\), мы будем называть предикатами на области определения функции. Напомним, что функцией из некоторого множества \(\mbox{Х}\) в некоторое множество \(\mbox{Y}\) называется отображение, ставящее каждому элементу множества \(\mbox{X}\) некоторый элемент множества \(\mbox{Y}\) единственным образом.

Расширенным доменом \(\mbox{D}^{+}_v\) переменной \(v\) будем называть домен этой переменной, дополненный специальным значением \(\omega\), которое не входит в универсальный домен: \(\mbox{D}^{+}_v = \mbox{D}_v \cup \{\omega\}\).

Операторы программы

Мы будем рассматривать 5 видов операторов программы над данным множеством переменных. Некоторым из них приписана функция:

  1. Начальный оператор START: \(\mathbf{y} \gets f(\mathbf{x})\). Здесь \(f\) является функцией \(\mbox{D}_x \to \mbox{D}^{+}_y\), инициализирующей промежуточные переменные программы на основе значений ее входных переменных.
  2. Оператор присваивания ASSIGN: \(\mathbf{y} \gets g(\mathbf{x},\mathbf{y})\). Здесь \(g\) является функцией \(\mbox{D}_x \times \mbox{D}_y \to \mbox{D}^{+}_y\), вычисляющей новые значения промежуточных переменных.
  3. Условный оператор TEST: \(t(\mathbf{x}, \mathbf{y})\). Здесь \(t\) является предикатом на множестве значений входных и промежуточных переменных программы.
  4. Оператор соединения JOIN.
  5. Оператор завершения HALT: \(\mathbf{z} \gets h(\mathbf{x}, \mathbf{y})\). Здесь \(h\) является функцией \(\mbox{D}_x \times \mbox{D}_y \to \mbox{D}^{+}_z\), устанавливающей значения выходных переменных программы.

Графическое представление операторов показано на рисунке ниже.

В программу могут входить несколько операторов одного и того же типа, помеченных одной и той же функцией. Поэтому для обеспечения уникальности одинаковых операторов в рамках одной программы, мы будем помечать каждый оператор уникальной меткой \(\ell_i\). Таким образом, каждый оператор программы состоит из метки оператора и тела оператора, принадлежащего к одному из пяти возможных типов. Множество меток всех операторов программы \(\mbox{P}\) будет обозначаться как \(\Lambda_\mbox{P}\).

Блок-схемы

В качестве модели программы мы будем использовать блок-схемы. Блок-схемой называется тройка \((V,N,E)\), где:

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

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

  1. В блок-схеме присутствует ровно один начальный оператор и не менее одного завершающего оператора.
  2. Любой оператор находится на ориентированном пути от начального оператора к некоторому завершающему оператору.
  3. Число связок, выходящих из каждого оператора, и пометки этих связок соответствуют типу оператора:
    1. Из оператора присваивания выходит ровно 1 дуга, помеченная символом \(\varepsilon\).
    2. Из начального оператора выходит ровно 1 дуга, помеченная символом \(\varepsilon\).
    3. Из условного оператора выходит ровно 2 дуги, причем одна из них помечена символом \(\mbox{T}\), а другая – символом \(\mbox{F}\).
    4. Из оператора соединения выходит ровно 1 дуга, помеченная символом \(\varepsilon\).
    5. Из завершающего оператора не выходит ни одной дуги.
  4. Число связок, входящих в каждый оператор, соответствует его типу:
    1. В начальный оператор не входит ни одна дуга.
    2. В оператор присваивания, условный и завершающий оператор входит ровно одна дуга.
    3. В оператор соединения входит не менее одной дуги.

Заметим, что для каждого оператора \(n\) и символа \(s\) в корректно-определенной блок-схеме \((V,N,E)\) существует не более одного оператора \(n'\), такого, что \((n,s,n') \in E\). Такой оператор \(n'\) (если он существует) мы будем называть последователем оператора \(n\) по пометке \(s\) и обозначать как \(succ(n,s)\).

Далее мы будем рассматривать только корректно-определенные блок-схемы, и, поэтому, слово «корректно-определенная» будет опускаться.

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

Для определения функций будет использоваться следующая нотация:

$$ (y_1, y_2, \ldots, y_b) \gets (f_1(\mathbf{x}, \mathbf{y}), f_2(\mathbf{x}, \mathbf{y}), \ldots, f_b(\mathbf{x}, \mathbf{y})) $$

Пример графического представления блок-схем можно увидеть на рисунке выше, где представлена блок-схема программы целочисленного деления. В этом примере множество переменных \(V = \{x_1, x_2, y_1, y_2, z_1, z_2\}\) состоит из двух входных, двух промежуточных и двух выходных переменных. Доменом всех переменных является множество целых чисел.

Далее без ограничения общности под «программами» понимаются их блок-схемы.

Семантика блок-схем

Конфигурацией программы \(\mbox{P}\) будем называть пару \((\ell, \sigma)\), где:

Если \(\sigma \in \mbox{D}^{+}_x \times \mbox{D}^{+}_y\) – вектор значений входных и промежуточных переменных программы, а функция \(f : \mbox{D}^{+}_x \times \mbox{D}^{+}_y \to \mbox{D}^{+}_y\) вычисляет новые значения переменных \(\mathbf{y}\), то вектор значений входных и промежуточных переменных программы, полученный путем замены в \(\sigma\) значений переменных \(\mathbf{y}\) на \(f(\sigma)\), мы будем обозначать как \(\sigma[\mathbf{y} \gets f(\mathbf{x}, \mathbf{y})]\).

Конечная или бесконечная последовательность конфигураций \( \{ \mbox{C}_i \mid i = 1, \ldots, n, \ldots \} \) программы P называется вычислением, если:
  1. Метка первой конфигурации программы является меткой начального оператора.
  2. Значения всех входных переменных программы являются определенными ( \(\ne \omega \) ) и неизменными во всех конфигурациях вычисления.
  3. Значения промежуточных переменных в первой конфигурации равны \(\omega\) (не определены).
  4. Если метка \(\ell_i\) текущего оператора конфигурации \(\mbox{C}_i\) является меткой начального оператора START: \(\mathbf{y} \gets f(\mathbf{x})\), то следующая конфигурация \(\mbox{C}_{i+1}\) состоит из метки оператора \(succ(n_i, \varepsilon)\) и вектора значений переменных \(\sigma_{i+1} = \sigma_i[\mathbf{y} \gets f(\mathbf{x})]\).
  5. Если метка \(\ell_i\) текущего оператора конфигурации \(\mbox{C}_i\) является меткой оператора присваивания ASSIGN: \(\mathbf{y} \gets g(\mathbf{x},\mathbf{y})\), то следующая конфигурация \(\mbox{C}_{i+1}\) состоит из метки оператора \(succ(n_i, \varepsilon)\) и вектора значений переменных \(\sigma_{i+1} = \sigma_i[\mathbf{y} \gets g(\mathbf{x}, \mathbf{y})]\).
  6. Если метка \(\ell_i\) текущего оператора конфигурации \(\mbox{C}_i\) является меткой условного оператора TEST: \(t(\mathbf{x}, \mathbf{y})\) и предикат \(t(\mathbf{x}, \mathbf{y})\) при значениях переменных \(\sigma_i\) принимает значение \(\mbox{F}\), то следующая конфигурация \(\mbox{C}_{i+1}\) состоит из метки оператора \(succ(n_i, \varepsilon)\) и вектора значений переменных \(\sigma_{i+1} = \sigma_i\).
  7. Если метка \(\ell_i\) текущего оператора конфигурации \(\mbox{C}_i\) является меткой оператора соединения JOIN, то следующая конфигурация \(\mbox{C}_{i+1}\) состоит из метки оператора \(succ(n_i, \varepsilon)\) и вектора значений переменных \(\sigma_{i+1} = \sigma_i\).
  8. Если метка \(\ell_i\) текущего оператора конфигурации \(\mbox{C}_i\) является меткой завершающего оператора HALT, то \(\mbox{C}_i\) является последней конфигурацией вычисления.
  9. Если в конфигурации \(\mbox{C}_{i+1}\) значение какой-либо промежуточной переменной равно \(\omega\), то это последняя конфигурация вычисления.

Тем самым, возможны три вида вычислений:

  1. Конечные последовательности конфигураций, в последней конфигурации никакие значения переменных не равны \(\omega\).
  2. Конечные последовательности конфигураций, в последней конфигурации значения некоторых переменных равны \(\omega\).
  3. Бесконечные последовательности конфигураций.

Лемма 1. Для каждой блок-схемы \(\mbox{P}\) и вектора значений ее входных переменных \(\mathbf{x}\) существует единственное вычисление, в первой конфигурации которого значения входных переменных равны \(\mathbf{x}\).

Каждой блок-схеме \(\mbox{P}\) мы поставим в соответствие функцию \(\mbox{M}[\mbox{P}]\) из входного домена блок-схемы в выходной домен, расширенный специальным значением \( \omega (\mbox{M}[\mbox{P}]: \mbox{D}_x \to \mbox{D}^{+}_z) \). Если вычисление блок-схемы \(\mbox{P}\) на векторе входных переменных \(\mathbf{x}\) является конечным, в последней конфигурации которого нет \(\omega\), и завершается на операторе HALT, то функция \(\mbox{M}[\mbox{P}](\mathbf{x})\) принимает значение \(h(\mathbf{x}, \mathbf{y}_n)\), где h – функция завершающего оператора последней конфигурации вычисления, а \(\mathbf{y}_n\) – вектор значений промежуточных переменных из последней конфигурации вычисления. В противном случае функция \(\mbox{M}[\mbox{P}](\mathbf{x})\) принимает значение \(\omega\).

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

Задачи и упражнения

  1. Перечислите все операторы в блок-схеме целочисленного деления, приведенной на рисунке.

  2. Приведите блок-схему с единственной входной и единственной выходной переменной, вычисляющую квадрат входной переменной.
  3. Приведите блок-схему с единственной входной и единственной выходной переменной, вычисляющую факториал значения входной переменной, если она неотрицательна. Можно предполагать, что отрицательные значения входной переменной не будут использоваться в вычислениях этой блок-схемы.
  4. Приведите блок-схему с единственной входной и единственной выходной переменной, вычисляющую \( [\frac{x+1}{x}]\), где х — это значение входной переменной, для положительных значений х. Можно предполагать, что неположительные значения х не будут использоваться в вычислениях этой блок-схемы.
  5. Приведите блок-схему с единственной входной и единственной выходной переменной, вычисляющую \(\frac{x \cdot (x+1)}{2}\), где х — это значение входной переменной, для неотрицательных значений х. Можно предполагать, что отрицательные значения х не будут использоваться в вычислениях этой блок-схемы.
  6. Приведите блок-схему с единственной входной переменной, не завершающуюся на бесконечном числе ее значений.
  7. Приведите блок-схему с двумя входными переменными \(x_1\) и \(x_2\) и единственной выходной переменной, которая вычисляет количество простых чисел между \(x_1\) и \(x_2\).
  8. Ответьте на вопрос: зацикливается ли блок-схема, изображенная на рисунке из упражнения 1. Если да, то приведите всевозможные пары значений входных переменных, при которых она зацикливается. Если нет, обоснуйте свой ответ.
  9. Приведите пример блок-схемы каждого из следующих видов, если они существуют:
    • в которых количество циклов меньше числа операторов соединения;
    • в которых количество циклов равно числу операторов соединения;
    • в которых количество циклов больше числа операторов соединения.