Структурированные программы
В этом разделе рассмотрим в качестве средства описания алгоритмов структурированные программы. Они вычисляют функции, используя минимальные средства: элементарные присваивания, условные операторы и циклы.
Определим вначале синтаксис структурированных программ. Зафиксируем для этого некоторое счетное множество имен переменных Var, которые будут использоваться в программах. Как обычно, будем считать, что оно включает имена x, x1,x2,…, y, y1,..., z,z1,... и т.п. В последующих определениях x, y, z - это произвольные переменные из Var.
Определение 7.1. Оператор присваивания. Присваивание - это выражение одного из следующих трех видов:
- x := x+1
- x := 0
- x := y.
Определение 7.2. Условия. Условие - это выражение одного из двух видов:
а) x = y или б) x < y.
Структурированные программы определяются индуктивно.
Определение 7.3.Структурированные программы.
- Каждое присваивание - это структурированная программа.
- Если ?1 и ?2 - структурированные программы, то и ?= ?1 ; ?2 - это структурированная программа.
-
Если ?1 и ?2 - структурированные программы, а ? - это условие, то
является структурированной программой.
-
Если ?1 - структурированная программа, а ? - это условие, то
все является структурированной программой.
- Других структурированных программ нет.
Конструкция в п. (б) называется последовательным применением или композицией программ ?1 и ?2, конструкция в п. (в) называется условным оператором; конструкция в п. (г) - это оператор цикла, ? - условие цикла, а ?1 - тело цикла.
С помощью структурированных программ (далее называемых просто программами) вычисляются (частичные) функции от натуральных аргументов, принимающие натуральные значения. С каждой программой ? свяжем естественным образом множество входящих в нее переменных Var?
(определите это множество индукцией по построению программы). В процессе работы программа изменяет значения этих переменных. Операционная семантика задает правила такого изменения.
Определение 7.4. Состояние - это отображение ? из множества переменных Var во множество N.
Для x

Разумеется, при рассмотрении конкретной программы ? нас будут интересовать значения переменных из Var?.
Определение 7.5. Операционная семантика программы ? - это отбражение (вообще говоря, частичное) типа S

- ( x := x+1)(?) = ?1, где ?1(y)=?(y) при y x, и ?1(x)=?(x)+1.
- ( x := 0)(?) = ?1, где ?1(y)=?(y) при y x, и ?1(x)=0.
- ( x := y)(?) = ?1, где ?1(z)=?(z) при z x, и ?1(x)=?(y)
- Пусть ?=?1;?2. Тогда ?(?)=(?1;?2)(?)=?2(?1(?)), при этом, если ?1(?)=? или ?1=?1(?) и ?2(?1)=?, то и ?(?)=?.
Пусть ?= если x = y то ?1 иначе ?2 конец. Тогда
Пусть ?= если x < y то ?1 иначе ?2 конец. Тогда
Пусть ?= пока x = y делай ?1 все. Тогда при ?(x)?(y) ?(?)= ?, а при ?(x) = ?(y) ?(?) - это первое такое состояние ?m в последовательности состояний ?0=?, ?1=?(?0),…, ?i+1=?(?i),…, что при im все состояния ?i определены, при i <m имеет место ?i(x) = ?i(y), и ?m(x)?m(y).- Семантику для цикла с условием x < y определите самостоятельно (см. задачу 7.1).
Пусть ? - программа, Var? - множество ее переменных. Выделим среди эти переменных некоторое подмножество входных
переменных x1,…, xn и одну результирующую (выходную) переменную y (она может быть одной из входных). Переменные из Var? , не являющиеся входными, будем называть вспомогательными.