Дудаков С.М. Математическое введение в информатику
Подождите немного. Документ загружается.
Глава 3
Структурированные программы
3.1 Синтаксис
Мы определим некоторый универсальный язык программирования и бу-
дем подробно изучать свойства ЯП на его примере. Позднее мы введем
и другие ЯП.
Определение 3.1. (Предметная область) Предметная область
ЯП — это множество объектов, с которыми ЯП позволяет работать
без дополнительных программных частей.
В большинстве ЯП предметная область включает в себя:
1. целые числа некоторого диапазона;
2. рациональные числа (с некоторыми ограничениями);
3. символы;
4. логические значения (истина, ложь, неизвестно).
То есть практически все ЯП позволяют оперировать этими объектами.
Кроме того, в большинстве ЯП есть и другие объекты предметной обла-
сти, например, комплексные числа, векторы, функции, графы, списки и
так далее.
Для нашего ЯП мы введем предметную область в виде множества на-
туральных чисел ω. Это некоторая абстракция, так как чисел бесконечно
много, а память любого реального вычислительного устройства конечна.
Но мы пока не будем рассматривать ограничения, присущие реальным
ЯП.
32 Глава 3. Структурированные программы
Определение 3.2. (Константа) Константа в ЯП — это некото-
рое имя, которое представляет некоторый зафиксированный элемент
предметной области.
Мы будем считать, что в нашем ЯП есть константа 0, представляющая
число 0.
Определение 3.3. (Операция) Операция в ЯП — это некоторое (мо-
жет быть частичное) отображение предметной области в себя, ко-
торое имеет фиксированное имя в ЯП.
Практически во всех ЯП есть операции, соответствующие арифмети-
ческим функциям +, −, ×, /.
В нашем ЯП мы введем только одну операцию — succ, которая бу-
дет означать прибавление единицы: succ (0) = 1, succ (3) = 4. Как мы
увидим, все остальные операции можно определить через succ, и можно
написать любую программу, используя только эту операцию. Заметим,
что операция succ определена для любого элемента нашей предметной
области.
Кроме того, нам потребуется какой-то способ для запоминания про-
межуточных результатов вычисления. Для этого используется следую-
щий элемент ЯП — переменные. Каждая переменная имеет некоторое
имя. Мы будем считать, что всевозможные имена переменных составля-
ют некоторое счетное множество V. Кроме того, мы будем для удобства
полагать, что
1. разные переменные имеют разные имена;
2. разные имена обозначают разные переменные.
Эти ограничения введены только для удобства изложения, в реальных
ЯП они могут не выполняться. Обычно мы будем в качестве имен пе-
ременных использовать буквы конца латинского алфавита, возможно, с
индексами: x, y
1
, v
u
и т.д.
В семантике реальных языков программирования переменной обыч-
но считают некоторую область памяти, связанную с ее именем. Мы же
будем отождествлять переменную и ее имя.
Часто нам будут встречаться последовательности однотипных пе-
ременных (а так же и других объектов), например, x
1
, x
2
, . . . , x
n
или
3.1. Синтаксис 33
y
1
, y
2
, . . . , y
m
. Для краткости, такие последовательности будем обозна-
чать как
x или y соответственно.
Знаком тильды ∼ мы будем обозначать графическое совпадение
синтаксических объектов (строк).
Пример 3.1. Пусть
m ∼ abc = def
n ∼ xyz ◦ abd
Тогда
mn ∼ abc = defxyz ◦ abd
Если a, b, c — синтаксические объекты и a ∼ bc, то b называют пре-
фиксом a, c — суффиксом a. Если префикс (суффикс) a отличается
от самого a, то такой префикс (суффикс) называют собственным.
В любом языке структурного программирования имеется оператор,
который позволяет сохранить в переменной результат. Чтобы определить
такой оператор для нашего ЯП введем понятие выражения.
Определение 3.4. (Выражение) Определим, что такое выражение,
по индукции.
1. Если x — имя переменной, то x — выражение.
2. Если c — константа, то c — выражение.
3. Если e
1
, . . . , e
n
— выражения, а o — это n-м естная операция, то
o (e
1
, . . . , e
n
) — выражение.
Других выражений нет.
Рассмотрим пример.
Пример 3.2. 0, x, succ (0), succ (succ (x)) — выражения.
Минимальным элементом ЯП, который означает выполнение каких-
либо действий, является оператор. Для сохранения промежуточных ре-
зультатов в нашем Я П будет служить оператор присваивания.
Определение 3.5. (Оператор присваивания) Оператор присваива-
ния — формула вида
x = e;
где x — имя переменной (левая часть оператора присваивания),
e — некоторое выражение (правая часть оператора присваива-
ния).
34 Глава 3. Структурированные программы
Оператор присваивания имеется практически во всех языках струк-
турного программирования. Этот оператор будет служить нам «кирпи-
чом», из которого мы будем строить все наши программы.
Пример 3.3. Примеры операторов присваивания:
x = succ (x) ;
y = succ (succ (0)) ;
Следующее наше понятие — тест.
Определение 3.6. (Тест) Тест — формула вида
e
1
= e
2
или вида
e
1
< e
2
,
где e
1
и e
2
— выражения. Часто, если конкретный знак сравнения не
имеет для нас значения, то мы будем записывать тест в виде
e
1
◦ e
2
подразумевая, что вместо ◦ может стоять или <, или =.
Пример 3.4. Примеры тестов:
x < succ (0)
succ (x) = succ (succ (y)) .
Замечание 3.1. Заметим, что оператор присваивания
x = e;
отличается от теста
x = e
наличием в конце точки с запятой (;).
Теперь мы можем определить, что такое структурированная програм-
ма.
3.1. Синтаксис 35
Определение 3.7. (Структурированная программа) Как и в слу-
чае с выражениями мы будем давать определение структурированной
программы (или структурной программы) по индукции.
1. Оператор присваивания x = e; является программой.
2. Следование. Если Π
1
и Π
2
— программы, то Π
1
Π
2
— програм-
ма.
3. Неполное ветвление. Если Π
1
— программа, а T — тест, то
if T then
Π
1
end;
является программой.
4. Полное ветвление. Если Π
1
и Π
2
— программы, а T — тест,
то
if T then
Π
1
else
Π
2
end;
является программой.
5. Цикл. Если Π
1
— программа, а T — тест, то
while T do
Π
1
end;
является программой.
Рассмотрим несколько примеров.
Пример 3.5. Операторы присваивания
x = 0;
и
y = succ (x) ;
являются программами. Поэтому их соединение:
x = 0;
y = succ (x) ;
36 Глава 3. Структурированные программы
тоже является программой. Также програм мами являются и сле-
дующие конструкции, которые получены с помощью пунктов 3, 4 и 5
соответственно:
1.
if x = 0 then
x = 0;
y = succ (x) ;
end;
2.
if x < succ (y) then
x = succ (y) ;
else
y = 0;
end;
3.
while succ (x) < y do
z = succ (z) ;
y = succ (x) ;
end;
Определение 3.8. (Множество переменных) Пусть e — выраже-
ние. Определим множество Var (e).
1. Var (x) = {x}, если x — переменная.
2. Var (c) = ∅, если c — константа.
3. Var (o (e
1
, . . . , e
n
)) = Var (e
1
) ∪ ··· ∪ Var (e
n
), если o — n-местная
операция, e
1
, . . . , e
n
— выражения.
Для теста T ∼ e
1
◦ e
2
:
Var (T ) = Var (e
1
) ∪ Var (e
2
) .
Для прог раммы Π мы определим два множества Var (Π) и LVar (Π) —
множество изменяемых переменных:
1. Π ∼ x = e;. Var (Π) = {x} ∪ Var (e), LVar (Π) = {x}.
2. Π ∼ Π
1
Π
2
Var (Π) = Var (Π
1
) ∪ Var (Π
2
) ,
LVar (Π) = LVar (Π
1
) ∪ LVar (Π
2
) .
3.1. Синтаксис 37
3.
Π ∼
if T then
Π
1
end;
Var (Π) = Var (T ) ∪ Var (Π
1
), LVar (Π) = LVar (Π
1
).
4.
Π ∼
if T then
Π
1
else
Π
2
end;
Var (Π) = Var (T ) ∪ Var (Π
1
) ∪ Var (Π
2
) ,
LVar (Π) = LVar (Π
1
) ∪ LVar (Π
2
) .
5.
Π ∼
while T do
Π
1
end;
Var (Π) = Var (T ) ∪ Var (Π
1
), LVar (Π) = LVar (Π
1
).
Таким образом, Var (a) — это множество переменных, которые встре-
чаются в a, LVar (Π) — множество переменных программы Π, которые
встречаются в левой части операторов присваивания.
Пример 3.6. Для программ из примера 3.5 на стр. 35:
1. Var (Π) = {x, y}, LVar (Π) = {x, y}.
2. Var (Π) = {x, y}, LVar (Π) = {x, y}.
3. Var (Π) = {x, y, z}, LVar (Π) = {y, z}.
Некоторые переменные программы используются для того, чтобы пе-
редать входные данные, другие — чтобы программа могла сообщить ре-
зультат. Чтобы выделить эти переменные, мы будем записывать наши
алгоритмы в специальном виде.
38 Глава 3. Структурированные программы
Alg Max;
arg x, y;
if x < y then
Max = y;
else
Max = x;
end;
end;
Рис. 3.1: Наибольшее из двух чисел.
Определение 3.9. (Алгоритм) Будем называть алгоритмом следу-
ющую конструкцию:
Alg Имя алгоритма;
arg Список входных переменных;
Тело алгоритма
end;
После Alg указывается имя, которое мы даем алгоритму (имя алго-
ритма), после arg — список переменных, в которых задаются началь-
ные условия (входные переменные). Каждая переменная может по-
являться в этом списке не более одного раза. Тело алгоритма (про-
грамму) A, мы будем обозначать Π
A
. Среди всех переменных мы будем
выделять одну — выходную переменную. Выходная переменная бу-
дет им еть такое же имя, как сам алгоритм. Выходная переменная не
может являться частью выражения. Следовательно, она может ис-
пользоваться только в левой части оператора присваивания. Выходная
переменная не может быть входной переменной.
Пример 3.7. Рассмотрим алгоритм на рис. 3.1. В данном случае, имя
алгоритма — Max, входные переменные — x и y. Тело алгоритма:
if x < y then
Max = y;
else
Max = x;
end;
Результат получается в выходной переменной Max. Заметим, что в
данной программе нельзя использовать операторы вида
x = Max;
3.1. Синтаксис 39
или
if Max < y then
.
.
.
end;
потому что в этом случае Max было бы выражением, а выходную пе-
ременную в выражениях использовать запрещено.
Лемма 3.1. (О сбалансированности) В любой программе Π сумма
количества слов if и while равна количеству слов end. В любом префик-
се прог раммы сумма количества слов if и while не меньше количества
слов end.
Доказательство. Доказательство — индукция по построению про-
граммы. Обозначим сумму количеств if и while в программе Π с помо-
щью I (Π), количество end — E (Π).
Базис индукции.
Если Π — оператор присваивания, то I (Π) = E (Π) = 0.
Шаг индукции.
1. Если Π ∼ Π
1
Π
2
, Π
1
и Π
2
— программы, то I (Π) = I (Π
1
) + I (Π
2
),
E (Π) = E (Π
1
) + E (Π
2
). По индукционному предположению,
I (Π
1
) = E (Π
1
) и I (Π
2
) = E (Π
2
). Следовательно, I (Π) = E (Π).
Пусть теперь Π
3
— префикс Π. Тогда или Π
3
— начальный фрагмент
Π
1
и для него утверждение выполняется по индукционному предполо-
жению, или Π
3
∼ Π
1
Π
4
, где Π
4
— префикс Π
2
. По индукционному пред-
положению I (Π
1
) = E (Π
1
) и I (Π
4
) ≥ E (Π
4
). Следовательно,
I (Π
3
) = I (Π
1
) + I (Π
4
) ≥ E (Π
1
) + E (Π
4
) = E (Π
3
) .
2. Пусть
Π ∼
if T then
Π
1
end;
Π
1
— программа. Тогда
I (Π) = 1 + I (Π
1
) = 1 + E (Π
1
) = E (Π) .
Если Π
3
— префикс Π, то или Π
3
не содержит ничего из Π
1
, тогда I (Π
3
) =
1 > 0 = E (Π
3
), или
Π
3
∼ if T then Π
4
40 Глава 3. Структурированные программы
где Π
4
— префикс Π
1
. Тогда
I (Π
3
) = 1 + I (Π
4
) > E (Π
4
) = E (Π
3
) .
3. Для полного ветвления и цикла доказательство аналогично.
∗
Задача 3.1. Обоснуйте индукционный шаг для полного ветвления и
цикла.
Задача 3.2. Верно ли, что в любом суффиксе любой программы коли-
чество слов end не меньше, чем суммарное количество if и while?
Лемма 3.2. (О суффиксе программы) Если Π ∼ Π
1
Π
2
, Π и Π
1
—
программы, Π
1
6∼ Π, то Π
2
— программа.
Доказательство. Индукция по построению Π.
Базис индукции.
Пусть Π ∼ x = e; — оператор присваивания. Любая программа окан-
чивается точкой с запятой. Внутри Π точка с запятой не встречается.
Π
1
— тоже программа, следовательно, она тоже оканчивается точкой с
запятой. Но это означает, что Π
1
∼ Π. Противоречие. Следовательно,
такой случай невозможен.
Шаг индукции.
1. Пусть
Π ∼
if T then
Π
3
else
Π
4
end;
Так как Π
1
оканчивается точкой с запятой, то граница между Π
1
и Π
2
проходит или внутри Π
3
, или внутри Π
4
. Рассмотрим первый случай:
Π
1
∼ if T then Π
0
3
Π
2
∼ Π
00
3
else Π
4
end;
Здесь Π
3
∼ Π
0
3
Π
00
3
. Так как Π
0
3
— префикс программы Π
3
, то в нем
сумма количеств if и while не меньше количества end. Но тогда в Π
1
сумма количеств if и while больше количества end, что противоречит
предыдущей лемме. Следовательно, такая ситуация невозможна.