Схемы программ (часть 1) презентация

Содержание

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

Слайд 1Схемы программ (часть 1)
Лекция 4

Слайд 2Алгоритмы и машина Тьюринга
Понятие алгоритма является фундаментальным математическим понятием, которое не

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

Слайд 3От алгоритма к программе
Алгоритм как последовательность «элементарных» операций над данными из

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

Слайд 4От алгоритма к программе
Переход от алгоритма к программе приводит к возникновению

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

Слайд 5От программ к схемам программ
Любое теоретическое исследование начинается с построения модели

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

Слайд 6Операторный метод
Начало теоретическому исследованию программ положили работы отечественных учёных, относящиеся к

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

Слайд 7Идея операторного метода
Языки описания строения алгоритмов: машины Тьюринга, продукции Поста, нормальные

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

Слайд 8Идея операторного метода
Поэтому базисные блоки в описании должны быть достаточно крупными

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

Слайд 9Идея операторного метода
Кроме того, вводятся дополнительные блоки-операторы, получившие название операторов управления


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

x y z x A B y f z C t
1 2 2 1 2 3 3
Здесь A, B, C – операторы счета, x, y, z - переменные

Слайд 10Схемы Янова
Идеи Ляпунова были развиты в работах его аспиранта Ю.И. Янова
В

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

Слайд 11Схемы Янова

Слайд 12Продолжение работ
Работу по эквивалентным преобразованиям операторных схем программ продолжали и другие

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

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

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

Слайд 14Представления схем программ
Схемы программ были введены в качестве объектов, на которых

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

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

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

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

Слайд 17Представление схем программ графами
В графе, представляющем схему программы, вершины помечаются операторами

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

Слайд 18Пример представления схемы в виде графа
Ввод(x)
y := a
y := g (x,

y)

x := h (x)

Вывод (y)

p (x)

L

L1

0

1

Слайд 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

Слайд 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))
Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.

Тесты

Слайд 42Значения термов и тестов
Значение терма τ при интерпретации I и состоянии

памяти W (обозначение: τI (W ) ) определяется следующим образом:
если τ = 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 ) );

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

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

Похожие презентации

Методология DFD 614
Развитие моделирования 315
Абстрактные структуры данных 578
Организация методической защиты информации на предприятии 288
Классификация неопределенных факторов 234
Выбор валюты в документах внутреннего товародвижения 205

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика