Содержание
- 2. Алгоритмы и машина Тьюринга Понятие алгоритма является фундаментальным математическим понятием, которое не может быть выражено через
- 3. От алгоритма к программе Алгоритм как последовательность «элементарных» операций над данными из некоторого множества, завершающаяся получением
- 4. От алгоритма к программе Переход от алгоритма к программе приводит к возникновению ряда проблем, основными из
- 5. От программ к схемам программ Любое теоретическое исследование начинается с построения модели исследуемого объекта В случае
- 6. Операторный метод Начало теоретическому исследованию программ положили работы отечественных учёных, относящиеся к пятидесятым годам прошлого столетия.
- 7. Идея операторного метода Языки описания строения алгоритмов: машины Тьюринга, продукции Поста, нормальные алгоритмы Маркова, рекурсии и
- 8. Идея операторного метода Поэтому базисные блоки в описании должны быть достаточно крупными и выбираться в зависимости
- 9. Идея операторного метода Кроме того, вводятся дополнительные блоки-операторы, получившие название операторов управления Их назначение заключается в
- 10. Схемы Янова Идеи Ляпунова были развиты в работах его аспиранта Ю.И. Янова В 1958 году им
- 11. Схемы Янова
- 12. Продолжение работ Работу по эквивалентным преобразованиям операторных схем программ продолжали и другие ученики А.А.Ляпунова – А.П.Ершов,
- 13. Оптимизация и верификация программ Важность проблемы эквивалентных преобразований вызвана потребностью улучшать те или иные характеристики первоначально
- 14. Представления схем программ Схемы программ были введены в качестве объектов, на которых можно строить эквивалентные преобразования
- 15. Текстовое представление схем программ Используемые для этого языки являются упрощенными копиями языков программирования высокого уровня Основное
- 16. Пример текстового представления схемы
- 17. Представление схем программ графами В графе, представляющем схему программы, вершины помечаются операторами и предикатами, а дуги
- 18. Пример представления схемы в виде графа Ввод(x) y := a y := g (x, y) x
- 19. Интерпретация схемы Если на место каждого абстрактного символа в схеме подставить соответствующую операцию, либо предикат, то
- 20. Назначение схем программ Схемы – это более простые объекты по сравнению с программами Использование схем для
- 21. Классы схем программ Существуют различные классы схем программ, соответствующие либо различным классам программ, либо ориентированные на
- 22. Характеризуются базисом и структурой схемы Базис класса стандартных схем: фиксирует символы, из которых строятся схемы, указывает
- 23. Полный базис В класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов
- 24. Х = {x, х1, х2..., у, у1 у2..., z, z1, z2...} - множество символов, называемых переменными;
- 25. Р = {р(0), р(1), р(2)...; q(0), q(1), q(2)...; } - множество предикатных символов; р(0), q(0) -
- 26. Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам: односимвольные
- 27. Тестами (логическими выражениями) называются логические константы и слова вида р(n)(τ1, τ2,..., τn) Примеры: p(0), p(0)(х), q(3)(x,
- 28. Множество операторов включает пять типов: начальный оператор - слово вида start(х1, х2...хк), где k ≥0, а
- 29. условный оператор (тест) - логическое выражение; вхождения переменных в логическое выражение называются аргументами этого оператора; оператор
- 30. Подклассы используют ограниченные базисы. Так, например, подкласс V1 имеет базис: {х1, х2}, {а, f(1)}, {p(1)}, {start,
- 31. Графы стандартных схем Для этой формы представления стандартной схемой в базисе В называется конечный размеченный ориентированный
- 32. Графы стандартных схем вершина-распознаватель, помеченная условным оператором; имеет одну входящую дугу и две выходящие, помеченные символами
- 33. Правильные схемы Переменная x∈ XS задана на дуге e схемы S, если любой путь от начальной
- 34. Правильная схема и ее интерпретации
- 35. Формальное определение интерпретации Интерпретацией базиса B в области интерпретации D называется функция I, которая сопоставляет: каждой
- 36. Конечные интерпретации Определение интерпретации не уточняет природу объектов области интерпретации (множества D ) В частности это
- 37. Стандартные программы Пара (S, I), где S –схема в базисе B, а I – интерпретация этого
- 38. Примеры программ Базис: X = {x, y}, F = {g(2), h(1), a}, P = {p(1)}, {старт,
- 39. Память программы Памятью XS схемы S называется конечное множество переменных, упоминаемых в этой схеме Состоянием памяти
- 40. Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам: односимвольные
- 41. Тестами (логическими выражениями) называются логические константы и слова вида р(n)(τ1, τ2,..., τn) Примеры: p(0), p(0)(х), g(3)(x,
- 42. Значения термов и тестов Значение терма τ при интерпретации I и состоянии памяти W (обозначение: τI
- 44. Скачать презентацию