Введение в схемы, автоматы и алгоритмы



             

Структурированные программы


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

Определим вначале синтаксис структурированных программ. Зафиксируем для этого некоторое счетное множество имен переменных 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 - структурированные программы, а ? - это условие, то

    \Pi= \mbox{ если } \Phi \mbox{ то } \Pi_1 \mbox{ иначе } \Pi_2 \mbox{ конец }

    является структурированной программой.

  • Если ?1 - структурированная программа, а ? - это условие, то

    \Pi= \mbox{ пока } \Phi \mbox{ делай }\Pi_1

    все является структурированной программой.

  • Других структурированных программ нет.

Конструкция в п. (б) называется последовательным применением или композицией программ ?1 и ?2, конструкция в п. (в) называется условным оператором; конструкция в п. (г) - это оператор цикла, ? - условие цикла, а ?1 - тело цикла.

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

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

Определение 7.4. Состояние - это отображение ? из множества переменных Var во множество N.


Содержание  Назад  Вперед