Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
О схемах программ Схема проектирования цикла с помощью инварианта
Содержание
- 1. О схемах программ Схема проектирования цикла с помощью инварианта
- 2. Лекция 5О схемах программСхема проектирования цикла с помощью инварианта14.04.2015О схемах программ
- 3. Схема программы (Котов В.Е., Сабельфельд В.К.
- 4. 14.04.2015Схема программы// вычисление n! (n≥0)p = 1; k = n;while (k !=0) {
- 5. Списки (напоминание)14.04.2015О схемах программ
- 6. 14.04.2015Модельное представление линейного списка Скобочная запись: x
- 7. 14.04.2015Функция-конструктор Cons (x, y) x = a
- 8. 14.04.2015Иллюстрация Cons (Head (z), Tail (z)) = zHead(z)zTail(z)Cons( Head(z),Tail(z) ) = zО схемах программ
- 9. 14.04.2015Функция-конструктор Cons(x, y) Пустой список : (
- 10. list p, k, n ; pp =
- 11. 14.04.2015Ручная прокрутка программы при n = (т
- 12. 14.04.2015// вычисление n! (n≥0)p = 1; k = n;// inv: fct(k)
- 13. Требования к инварианту и варианту циклаИнтерпретация схемы:
- 14. list p, k, n ; pp =
- 15. Инвариант интерпретации со спискамиConcat ((к а р),
- 16. Требования к варианту циклаv(k) ≡ length(k)? 14.04.2015О схемах программ
- 17. 14.04.2015Картинки к телу цикла и к инвариантуReverse (n) = Concat (Reverse (k), p)kpО схемах программ
- 18. 14.04.2015О схемах программ
- 19. Скачать презентанцию
Лекция 5О схемах программСхема проектирования цикла с помощью инварианта14.04.2015О схемах программ
Слайды и текст этой презентации
Слайд 2Лекция 5
О схемах программ
Схема проектирования цикла с помощью инварианта
14.04.2015
О схемах
программ
Слайд 3Схема программы (Котов В.Е., Сабельфельд В.К. Теория схем программ. М.:
Наука, 1991 – 248 с.)
// вычисление n!
p = 1; k = n;
while (k ≠ 0) {
p = k
*p; k = k − 1;
}
Ручная прокрутка программы при n=5
Пример
14.04.2015
О схемах программ
Слайд 414.04.2015
Схема программы
// вычисление n! (n≥0)
p = 1; k = n;
while (k !=0) {
p = k *p;
k = k − 1;
}
// Схема программы:
p = pp; k = n;
while
(k !=kk) {p = h (k, p);
k = g (k);
}
Интерпретация схемы:
pp = 1; kk = 0; // константы
h(x, y) = x * y; g(x) = x – 1;
О схемах программ
Слайд 614.04.2015
Модельное представление линейного списка
Скобочная запись:
x = (a b
c d e) или [a, b, c, d, e] или
(a; b; c; d; e)Функции-селекторы: «голова» - head, first
«хвост» - tail, rest
применяются к непустому списку и позволяют разобрать его на составные части.
Например, Head (x) = a, Tail (x) = (b c d e),
Head (Tail (x)) = b, Tail (Tail (x)) = (c d e)
О схемах программ
Слайд 714.04.2015
Функция-конструктор Cons (x, y)
x = a - элемент базового
типа,
y = (b c d e) - список
Cons (x,
y) = (a b c d e)Свойства:
Cons ( Head (z), Tail (z)) = z
Head(Cons (x, y)) = x
Tail (Cons (x, y)) = y
О схемах программ
Слайд 814.04.2015
Иллюстрация
Cons (Head (z), Tail (z)) = z
Head(z)
z
Tail(z)
Cons( Head(z),Tail(z) )
= z
О схемах программ
Слайд 914.04.2015
Функция-конструктор Cons(x, y)
Пустой список : ( ) или Nil
Cons
(a, Nil) = Cons (a, ( )) = (a)
(a b
c d e) = Cons (a, Cons (b, Cons (c, Cons (d, Cons(e, Nil)))))
Это «операционное» представление списка
Функция-индикатор: Null (z)
Null (Nil) = true, z = (a b c d e) → Null (z) = false
Всегда Null (Cons (x, y)) = false
О схемах программ
Слайд 10list p, k, n ; pp = Nil; kk =
Nil;
g(x) = Tail (x); h(x, y)= ConsHd (x,y)= Cons
(Head (x), y);Null (x) ≡ (x=Nil)
// Схема программы:
p = pp; k = n;
while (k !=kk) {
p = h (k, p);
k = g(k);
}
Интерпретация схемы в случае списков
// Программа:
//вход – список n, м.б. пустой
p = Nil; k = n;
while (k !=Nil) { // !Null(k)
p = ConsHd (k, p);
k = Tail (k);
}
Результат: ? Reverse (n)
14.04.2015
О схемах программ
Слайд 1114.04.2015
Ручная прокрутка программы при n = (т о р г)
//
Программа:
//вход – список n, м.б. пустой
p = Nil; k
= n;while (k !=Nil) { // !Null(k)
p = ConsHd (k, p);
k = Tail (k);
}
О схемах программ
Слайд 1214.04.2015
// вычисление n! (n≥0)
p = 1; k = n;
// inv: fct(k) *p = fct(n)
// var: v
(k)= k
while (k !=0) {
p = k *p;
k = k − 1;
} // p
=fct(n)// Схема программы:
// вычисление f(n)
p = pp; k = n;
// inv: q (f(k),p) = f(n)
// var: v (k) ***
while (k !=kk) {
p = h (k, p);
k = g(k);
} // p = f(n)
Интерпретация схемы: pp, kk – константы.
h(x, y) = x * y; g(x) = x – 1; q(x, y) = x * y;
Примечание: почему h(x, y) и q(x, y) разные функции
Добавим утверждения, т.е. спецификацию (предусловие, постусловие) + инвариант цикла
fct(n)=n!
О схемах программ
Слайд 13Требования к инварианту и варианту цикла
Интерпретация схемы: pp, kk –
константы.
h(x, y) = x * y; g(x)
= x – 1; q(x, y) = x * y;При входе (p =pp) & (k =n) ⇒ q (f(k),p) = f(n)
Т.е. q (f(n),pp) =f(n)
При выходе (q (f(k),p)=f(n)) & (k =kk) ⇒ (p =f(n))
Свойство сохранения:
{(k !=kk) & (q (f(k),p) =f(n))}
p = h (k, p); k = g(k);
{(q (f(k),p) =f(n))}
14.04.2015
О схемах программ
Слайд 14list p, k, n ; pp = Nil; kk =
Nil;
g(x) = Tail (x); h(x, y)= ConsHd (x,y)= Cons
(Head (x), y); q (x,y) = Concat(x,y)
Интерпретация схемы в случае списков
// Программа: f(n)=Reverse(n)
//вход – список n, м.б. пустой
p = Nil; k = n;
// inv: q (f(k),p) = f(n)
// var: v (k)
while (k !=Nil) { // !Null(k)
p = ConsHd (k, p);
k = Tail (k);
} // p = f(n)
// Схема программы:
// вычисление f(n)
p = pp; k = n;
// inv: q (f(k),p) = f(n)
// var: v (k)
while (k !=kk) {
p = h (k, p);
k = g(k);
} // p = f(n)
14.04.2015
О схемах программ
Слайд 15Инвариант интерпретации со списками
Concat ((к а р), (т у з))
= (к а р т у з),
Concat (Nil,y) =y, Concat
(x,Nil) =xq (x,y) = Concat(x,y)
inv: q (f(k),p) = f(n)
т.е. Concat(Reverse(k),p) = Reverse(n)
Если ввести инфиксное обозначение
s1 ⊕ s2 = Concat (s1, s2),
то inv: Concat(Reverse(k),p) = Reverse(n) превратится в
Reverse(k) ⊕p = Reverse(n),
что легче интерпретировать как аналог
fct(k) *p = fct(n).
14.04.2015
О схемах программ
Слайд 1714.04.2015
Картинки к телу цикла и к инварианту
Reverse (n) = Concat
(Reverse (k), p)
k
p
О схемах программ
