Схемы программ (часть 1)

1. Схемы программ (часть 1)

Лекция 4

2. Алгоритмы и машина Тьюринга

Понятие алгоритма является фундаментальным
математическим понятием, которое не может быть
выражено через другие, а определяется
непосредственно (на интуитивном уровне) подробно
понятию натурального числа или множества
Машина Тьюринга – это один из способов
формализации понятия алгоритма, а точнее, понятия
вычислимой функции
Тезис о возможности представления любого
алгоритма эквивалентной машиной Тьюринга
недоказуем именно в силу априорности понятия
алгоритма

3. От алгоритма к программе

Алгоритм как последовательность «элементарных»
операций над данными из некоторого множества,
завершающаяся получением результата, может иметь
текстовое представление на некотором языке
Такое представление называется программой.
Пример – программа для машины Тьюринга

4. От алгоритма к программе

Переход от алгоритма к программе приводит к
возникновению ряда проблем, основными из которых
являются:
проблема соответствия программы алгоритму ,
проблема однозначности программного представления
алгоритма
Отсюда следует необходимость изучения программ
как самостоятельных объектов

5. От программ к схемам программ

Любое теоретическое исследование начинается с
построения модели исследуемого объекта
В случае программ такой теоретической моделью
являются схемы программ
Схемы программ должны удовлетворять
универсальным требованиям, предъявляемым к
моделям:
игнорировать некоторые несущественные свойства,
например, детали синтаксиса языка программирования;
воспроизводить все существенные для исследования
свойства;
позволять изучать не отдельные программы, а их классы;
допускать возможность модификации и расширения

6. Операторный метод

Начало теоретическому исследованию программ
положили работы отечественных учёных, относящиеся к
пятидесятым годам прошлого столетия. Их инициатором
был Алексей Андреевич Ляпунов
Он предложил операторный метод программирования,
в котором впервые была предпринята формализация
понятия программы и провозглашена, как
фундаментальная, проблема разработки
эквивалентных преобразований программ

7. Идея операторного метода

Языки описания строения алгоритмов: машины
Тьюринга, продукции Поста, нормальные алгоритмы
Маркова, рекурсии и т. п.
Общий недостаток этих языков:
1.
2.
алгоритмы расчленяются на элементарные операции, что
обусловливает огромные объемы описаний даже
простейших реальных алгоритмов;
жесткий набор базисных элементарных операций не
позволяет во всех случаях давать рациональное
представление алгоритма

8. Идея операторного метода

Поэтому базисные блоки в описании должны быть
достаточно крупными и выбираться в зависимости от
класса задач
Блоки должны связываться между собой логическими
условиями, определяющими порядок выполнения
блоков, обмен информацией и т.п.
Описание алгоритма через блоки и логические
условия было названо Ляпуновым логической схемой
алгоритма (схемой счета)
Блоки схемы счета Ляпунов называет операторами
счета, а логические условия – распознавателями

9. Идея операторного метода

Кроме того, вводятся дополнительные блокиоператоры, получившие название операторов
управления
Их назначение заключается в обеспечении нужной
последовательности переходов в цепочке операторов
счета и распознавателей
Пример логической схемы программы по Ляпунову:
xyz
1
x
2
ABy
2
f
1
2
z
3
Ct
3
Здесь A, B, C – операторы счета, x, y, z - переменные

10. Схемы Янова

Идеи Ляпунова были развиты в работах его аспиранта
Ю.И. Янова
В 1958 году им совместно с А.А. Ляпуновым была
опубликована статья, в которой:
дана формализация понятия схемы программы;
введено понятие эквивалентности схем;
предложен алгоритм, распознающий эквивалентность
схем;
введена графовая форма представления схем

11. Схемы Янова

12. Продолжение работ

Работу по эквивалентным преобразованиям
операторных схем программ продолжали и другие
ученики А.А.Ляпунова – А.П.Ершов, Р.И.Подловченко,
Н.А. Криницкий и другие
Слушатели первого ляпуновского курса
программирования А.П.Ершов, И.Б.Задыхайло,
Э.З.Любимский, В.С.Штаркман участвовали в
разработке первых в стране трансляторов,
(программирующих программ)

13. Оптимизация и верификация программ

Важность проблемы эквивалентных преобразований
вызвана потребностью улучшать те или иные
характеристики первоначально создаваемых
программ, не искажая при этом реализуемую
программой функцию
Эта задача получила название проблемы
оптимизации программ
Очень скоро к ней присоединилась проблема
верификации программ, состоящая в проверке того,
действительно ли программа реализует ту функцию,
для вычисления которой она построена

14. Представления схем программ

Схемы программ были введены в качестве объектов,
на которых можно строить эквивалентные
преобразования программ, сохраняющие их
управляющую структуру и отвлекающиеся от
детального описания операторов и логических
условий, используемых в программах.
Схемы программ как и любая модель должны иметь
какое-то представление
Для схем программ используются два основных
представления – текстовое и графовое

15. Текстовое представление схем программ

Используемые для этого языки являются
упрощенными копиями языков программирования
высокого уровня
Основное отличие текста программы от текста ее
схемы состоит в следующем:
каждый оператор программы единственным образом
задает некоторую вычислимую функцию над данными, а
из этих отдельных функций образуется функция программы
в целом;
в схемах индивидуальные операции и функции заменены
абстрактными символами переменных-операций и
переменных-предикатов

16. Пример текстового представления схемы

Программы
Вычисление факториала
Инверсия слова
begin integer x, y;
ввод (x);
y:=1;
L: if x=0 then goto L1
y:=x*y;
x:=x-1;
goto L;
L1: вывод (y);
end
begin string x, y;
ввод (x);
y:=е;
L: if x=e then goto L1
y:=CopyFirst (x, y);
x:=DelFirst (x);
goto L;
L1: вывод (y);
end
Схема программ
begin
ввод (x);
y:=a;
L: if p(x) then goto L1
y:=g (x, y);
x:=h (x);
goto L;
L1: вывод (y);
end

17. Представление схем программ графами

В графе, представляющем схему программы, вершины
помечаются операторами и предикатами, а дуги
показывают возможные пути перехода от оператора к
оператору
Представление схемы в виде графа является более
наглядным, однако только при относительно малых
своих объемах

18. Пример представления схемы в виде графа

Ввод(x)
y := a
p (x)
L
1
0
y := g (x, y)
L1
Вывод (y)
x := h (x)

19. Интерпретация схемы

Если на место каждого абстрактного символа в схеме
подставить соответствующую операцию, либо
предикат, то схема превращается в программу
Процесс такой подстановки называется
интерпретацией схемы
Для одной и той же схемы могут быть предложены
различные интерпретации и, соответственно,
получены разные программы

20. Назначение схем программ

Схемы – это более простые объекты по сравнению с
программами
Использование схем для анализа свойств программ
делает этот анализ более простым
Результаты анализа схем носят более общий характер
по сравнению с результатами анализа отдельных
программ

21. Классы схем программ

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

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

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

23. Полный базис

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

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

Х = {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...;

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

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

26. Термы

Термами (функциональными выражениями)
называются слова, построенные из переменных,
функциональных и специальных символов по
следующим правилам:
◦
◦
◦
односимвольные слова, состоящие из переменных или
констант, являются термами;
слово τ вида f(n)(τ1, τ2, ..., τn), где τ1, τ2, ..., τn - термы,
является термом;
те и только те слова, о которых говорится в п.п. 1,2,
являются термами
Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a))

27. Тесты

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

28. Операторы

Множество операторов включает пять типов:
◦
◦
◦
начальный оператор - слово вида start(х1, х2...хк), где k ≥0,
а х1, х2...хк - переменные, называемые результатом этого
оператора;
заключительный оператор - слово вида stop(τ1, τ2,..., τn),
где n ≥ 0, а τ1, τ2,..., τn - термы; вхождения переменных в
термы τ называются аргументами этого оператора;
оператор присваивания - слово вида х := τ, где х –
переменная (результат оператора), а τ - терм;
вхождения переменных в термы называются
аргументами этого оператора;

29. Операторы

условный оператор (тест) - логическое выражение;
вхождения переменных в логическое выражение
называются аргументами этого оператора;
оператор петли - односимвольное слово loop.
Среди операторов присваивания выделим случаи:
когда τ - переменная, то оператор называется
пересылкой (х:=у) и когда τ - константа, то оператор
называется засылкой (х:=а).

30. Подклассы стандартных схем

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

31. Графы стандартных схем

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

32. Графы стандартных схем

вершина-распознаватель, помеченная условным
оператором; имеет одну входящую дугу и две выходящие,
помеченные символами 1 и 0;
вершина-петля, помеченная оператором петли; не имеет
выходящих дуг
Множество переменных, используемых в схеме S,
составляет ее память XS
Для удобства дальнейших рассуждений будем
снабжать вершины графа схемы именами, используя в
качестве таковых целые числа
Начальная вершина имеет имя 0

33. Правильные схемы

Переменная x XS задана на дуге e схемы S, если
любой путь от начальной вершины и
заканчивающийся дугой е содержит хотя бы один
оператор с результатом x
Схема называется правильной, если на каждой ее дуге
е заданы все переменные, которые являются
аргументами оператора, помечающего конечную
вершину этой дуги
Разметкой графа схемы называется процесс
сопоставления каждой из его дуг множества заданных
на ней переменных

34. Правильная схема и ее интерпретации

35. Формальное определение интерпретации

Интерпретацией базиса B в области интерпретации
D называется функция I, которая
сопоставляет:
каждой переменной x из базиса B – некоторый элемент d=I(x)
из области интерпретации D;
каждой константе a из базиса B – некоторый элемент d=I(a) из
области интерпретации D;
каждому функциональному символу f(n) (n≥1) – всюду
определенную функцию F(n) = I(f(n)): D(n) → D;
каждой логической константе p(0) – один из символов
множества {0,1};
каждому предикатному символу p(n) (n≥1) – всюду
определенный предикат P(n) = I(p(n)): D(n) → {0,1};

36. Конечные интерпретации

Определение интерпретации не уточняет природу
объектов области интерпретации (множества D )
В частности это могут быть множества всех целых
чисел, всех слов в некотором алфавите или
подмножества этих множеств
Интерпретация I называется конечной, если ее
область D – конечное множество

37. Стандартные программы

Пара (S, I), где S –схема в базисе B, а I –
интерпретация этого базиса, называется
интерпретированной стандартной схемой или
стандартной программой

38. Примеры программ

Базис:
X = {x, y}, F = {g(2), h(1), a},
P = {p(1)}, {старт, стоп, :=}
Интерпретация базиса:
D – множество целых
неотрицательных чисел
I(x)=4, I(y)=1, I(a)=1
I(g)=G(d1,d2), где G(d1,d2)= d1*d2
I(h)=H(d), где H(d)=d-1
I(p)=P(d), где P(d)=1 при d=0 и
P(d)=0 при d<>0

39. Память программы

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

40. Термы

Термами (функциональными выражениями)
называются слова, построенные из переменных,
функциональных и специальных символов по
следующим правилам:
◦
◦
◦
40
односимвольные слова, состоящие из переменных или
констант, являются термами;
слово τ вида f(n)(τ1, τ2, ..., τn), где τ1, τ2, ..., τn - термы, является
термом;
те и только те слова, о которых говорится в п.п. 1,2,
являются термами
Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a))

41. Тесты

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

42. Значения термов и тестов

Значение терма при интерпретации I и состоянии
памяти W (обозначение: I (W ) ) определяется
следующим образом:
1.
2.
3.
если = x , где x – переменная, то I (W ) = W (x);
если = a, где a – константа, то I (W ) = I (a);
если = f(n) ( 1, 2, . . . , n), то I (W ) = I (f(n) ) ( 1I (W ) , 2I (W ) , . . . ,
nI (W ) );
Аналогично определяется значение теста при
интерпретации I и состоянии памяти W (обозначение:
I (W ) ): если = p(n)( 1, 2, . . . , n), n 0, то
I (W ) = I (p(n) ) ( 1I (W ) , 2I (W ) , . . . , nI (W ) );
42

43. Конфигурация программы

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