Задания для самостоятельной работы
1. Проследите, как выполняется рекурсивная программа, реализующая функцию Аккермана, при следующих аргументов: а) А(1, 2); б) А(1, 1); в) А(2, 1).
2. Для рекурсивной программы, применимой к любым двум спискам L1, L2:
INT (L1, L2) º IF L1 = NIL ТНЕN NIL
ЕLSЕ IF МЕМВЕR (САR (L1), L2) ТНЕN
CONS (САR (L1), INT (CDR (L1), L2))
ЕLSЕ ОТНЕRWISЕ INT (CDR (L1), L2)
Выпишите последовательность вычислений для INT ( [D C B], [А В С]).
3. Рассмотрите рекурсивную программу, применимую для любых неотрицательных целых чисел N:
F(N) º IF N = 0 ТНЕN 1
ЕLSЕ ОТНЕRWISЕ 2 • F(N – 1),
выведите формулу для вычисляемой функции F(N) и докажите ее правильность.
4.4. Контрольные вопросы к защите Лабораторной работы №3
Тема2 «Рекурсивные программы. Структурная индукция»
1. Что такое рекурсивная программа?
2. В чем заключается принцип структурной индукции?
3. С какой целью применяется структурная индукция?
4. Можно ли использовать структурную индукцию для доказательства правильности нерекурсивных программ?
Литература
1. Андерсен Р. Доказательство правильности программ. – М.: Мир, 1982.- 163с.
2. Веретельникова Е.Л. Доказательство правильности программ: Метод индуктивных утверждений. Конспект лекций. – Новосибирск, Изд-во НГТУ, 2004. – 59c.
3. Веретельникова Е.Л. Доказательство правильности программ: Дополнительные приемы. Конспект лекций. – Новосибирск, Изд-во НГТУ, 2005. – 36 с.
|
|
|
4. Веретельникова Е.Л. Сборник задач по курсу «теория вычислительных процессов»: Часть 1. Доказательство правильности программ: сборник задач. – Новосибирск: Изд-во НГТУ, 2006. – 48 с.
Романов Е.Л. Практикум по программированию на С++: Уч. пособие. СПб: БХВ-Петербург; Новосибирск: Изд-во НГТУ, 2004. – 432 с.
Оглавление
Глава 1. МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ.. 3
1.1. Простая индукция. 3
1.2. Строгая математическая индукции. 6
1.3. Задания для самостоятельной работы.. 9
1.4. Контрольные вопросы к защите Лабораторной работы №1 «Математическая индукция» 9
Глава 2. ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ БЛОК-СХЕМ ПРОГРАММ... 10
2.1. Основные принципы доказательства правильности для блок-схем.. 11
2.2. Метод индуктивных утверждений. 21
2.3. Задания для самостоятельной работы.. 29
2.4. Контрольные вопросы к защите Лабораторной работы №2 Тема1 «Доказательство правильности блок-схем», Тема2 «Доказательство правильности блок-схем методом индуктивных утверждений». 29
Глава 3. ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ ПРОГРАММ, НАПИСАННЫХ НА ОБЫЧНЫХ ЯЗЫКАХ ПРОГРАММИРОВАНИЯ.. 31
3.1. Основные примы доказательства правильности программ.. 31
3.2. Задания для самостоятельной работы.. 37
3.3. Контрольные вопросы к защите Лабораторной работы №3 Тема1 «Доказательство правильности программ». 37
|
|
|
Глава 4. ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ РЕКУРСИВНЫХ ПРОГРАММ... 37
4.1. Упрощенный язык программирования для иллюстрации понятия рекурсии. 38
4.2. Структурная индукция. 44
4.3. Задания для самостоятельной работы.. 47
4.4. Контрольные вопросы к защите Лабораторной работы №3 Тема2 «Рекурсивные программы. Структурная индукция». 48
Литература. 48
Дата добавления: 2018-05-12; просмотров: 337; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!