НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Е.Л. Веретельникова

сборник задач
по курсу
«теория вычислительных процессов»

Часть 1.

доказательство правильности программ

Утверждено Редакционно-издательским советом университета
в качестве учебного пособия для практических занятий
по курсу «Теория вычислительных процессов»

НОВОСИБИРСК

Рецензенты: канд. техн. наук И.А. Полетаева, доц. каф. ПМт;
канд. техн. наук А.А. Боровков, доц. каф. Авт

Работа подготовлена на кафедре автоматики
для студентов III-IV курса АВТФ специальности 230105 (220400)
дневной и заочной форм обучения

Веретельникова Е.Л.

сборник задач по курсу «теория вычислительных процессов»: Часть 1. Доказательство правильности программ: сборник задач / Е.Л. Веретельникова. – Новосибирск: Изд-во НГТУ, 2006. – 48 с.

В работе изложены теоретический материал и практические задания для освоения основных принципов и приемов доказательства правильности программ, представленных блок-схемами или записанных на языках высокого уровня. Материал подразделен на восемь основных тем и сгруппирован таким образом, чтобы изучению одной темы соответствовало одно-два аудиторных занятия. В рамках каждой темы предлагаемые принципы доказательства иллюстрируются примерами, а затем предлагаются упражнения для самостоятельной работы.

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

© Новосибирский государственный
технический университет, 2006

Тема 1. МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ

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

Принцип простой индукции

Обычно математическую индукцию вводят как метод доказательства утверждений о положительных числах.

Пусть S(n) — некоторое высказывание о целом числе n и требуется доказать, что S(n) справедливо для всех положительных чисел n.

Согласно простой математической индукции, для этого необходимо

1. Доказать, что справедливо высказывание S(1).

2. Доказать, что если для любого положительного числа n справедливо высказывание S(n),то справедливо и высказы­вание S(n +1).

Пример использования простой индукции для доказательства правильности некоторого утверждения о положительных числах можно посмотреть в [1].

Принцип модифицированной простой индукции

Иногда необходимо доказать, что высказывание S(n) справедливо для всех целых n³n₀. Для этого можно довольно легко модифицировать принцип простой индукции. Чтобы доказать, что высказывание S(n) справедливо для всех целых n, необходимо:

1. Доказать, что справедливо S(n₀).

2. Доказать, что если S(n) справедливо для всех целых n³n₀, то справедливо и S(n+1).

В частности, если требуется доказать справедливость некоторого высказывания S(n) для любых положительных целых n (т. е. для n³0), то необходимо:

1. Доказать, что справедливо S(0).

2. Доказать, что для всех неотрицательных целых n справедливо S(n+1), если справедливо S(n).

Рассмотрим пример использования модифицированной простой индукции.

ПРИМЕР 1.1. Для любого неотрицательного числа n доказать, что

2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹ – 1.

Используя простую индукцию, мы должны

1. Доказать, что 2⁰ = 2⁰⁺¹ – 1. Это очевидно, так как

2⁰ = 1 = 2⁰⁺¹ – 1 = 2¹ – 1= 2 – 1 = 1.

2. Доказать, что если для всех неотрицательных целых n справедлива формула 2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹ – 1, то справедлива и формула

2⁰ + 2¹ + 2² + … + 2ⁿ + 2ⁿ⁺¹ = 2^(n+1)+1 – 1.

Высказывание 2⁰ + 2¹ + 2² + ... + 2 ⁿ = 2ⁿ⁺¹ – 1 называется гипотезой индукции. Второе положение доказывается следующим образом:

2⁰ + 2¹ + 2² + … + 2ⁿ + 2ⁿ⁺¹ = (2⁰ + 2¹ + 2² + … + 2ⁿ ) + 2ⁿ⁺¹ =

= (2ⁿ⁺¹ – 1) + 2ⁿ⁺¹ = ( 2ⁿ⁺¹ + 2ⁿ⁺¹ ) – 1 =2×2ⁿ⁺¹ – 1 = 2ⁿ⁺² – 1 = 2^(n+1)+1 – 1.

(По гипотезе индукции)

Что и требовалось доказать.

Поскольку мы доказали справедливость двух утвержде­ний, то по индукции формула 2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹ – 1.

считается справедливой для любого неотрицательного числа n.

Упражнения

1. Докажите, что дня любого положительного числа n справедливы формулы:

1) ; 2) ;

3) ; 4) 1+ 2 + 3 +...+ n = .

Обратите внимание, что из двух последних формул вытекает справедливость такой интересной формулы: .

2. Приведенные на рис. 1.1 графы представляют собой примеры пол­ных двоичных графов уровней 0, 1, 2 и 3. Полный двоичный граф уровня n подобен приведенным графам: из каждой его вершины, кроме вершин уровня п, выходят по два ребра. Вершины уровня п называются концевыми вершинами или листьями дерева. С помощью индукции по уровню n докажите, что число концевых вершин в полном двоичном дереве уровня п равно 2ⁿ. Напишите формулу для числа всех вершин в полном графе (как концевых, так и неконцевых) и докажите ее справедливость для любого положительного числа п.

3. На рис. 1.2 даны примеры полных графов, содержащих 1-5 вершин. Полный граф из п вершин аналогичен приведенным: пара любых его вершин соединена ребром. Напишите формулу для числа всех ребер в полном графе с п вершинами и докажите ее справедливость с помощью индукции по п.

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

5. 4. Доказать, что сумму п первых членов геометрической прогрессии можно вычислить по формуле (для q ≠ 1), учитывая, что п-ый член последовательности определяется как .

6. Доказать, пользуясь принципом простой индукции, что для любого положительного числа п общее число шаров в пирамиде из п рядов
(рис. 1.3) равно .

7. Найдите ошибку в следующем доказательстве. Доказать, что

для любого положительного целого числа п. Доказательство проводим методом индукции:

1. Для п = 1 формула справедлива, ибо .

2. Предположим, что формула справедлива для п, т.е.

.

Покажем, что эта формула справедлива и для п + 1:

(По гипотезе индукции)

Таким образом, утверждение справедливо и для п + 1. Хотя доказательство выглядит как будто правильно, тем не менее оно неверно, так как для п = 4

.

Однако .

8. Найдите ошибку в следующем доказательстве. Доказать, что в любой куче камешков все камешки одного цвета. Используем индукцию по числу камешков в куче.

1. Для п = 1 это высказывание очевидно, т.к. вся куча состоит из одного камешка и поэтому в куче есть камешки только одного цвета.

2. Предположим, что наше высказывание справедливо для любой кучи из п камешков. Покажем, что оно справедливо и для кучи из (п + 1) камешков. Кучу камешков можно представить следующим образом (рис. 1.5). Если же мы уберем (п + 1)-й камешек из этой кучи, то останется куча из п камешков (рис. 1.6). По гипотезе индукции все камешки в такой куче имеют один цвет. Представим себе, что вместо последнего мы выбрасываем первый камешек из кучи (рис. 1.7). Но здесь то же число п камешков и, следовательно, все они одного цвета. Отсюда следует, что и (п + 1) камешков будут одного цвета, т.к. известно, что камешки (рис. 1.8) одного цвета, а (п + 1)-й камешек того же цвета, что и п-й (даже больше, его цвет совпадает с цветом второго, третьего и т.д.). Отсюда и следует справедливость нашего утверждения.

Рис. 1.5 Рис. 1.6 Рис. 1.7 Рис. 1.8

При доказательствах некоторых высказываний о целых числах иногда требуется более строгая версия принципа индукции.

Принцип строгой индукции

Пусть S(n) – некоторое высказывание о целом числе n и требуется доказать, что S(n) справедливо для всех положи­тельных n. Для этого необходимо:

1) доказать, что справедливо S(1);

2) доказать, что если справедливы S(1), S(2), S(3), ..., S(n) для всех положительных n, то справедливо и S(n + 1).

Рассмотрим пример использования строгой индукции, когда предположений простой индукции оказывается недостаточно для доказательства.

Пример 1.2. Рассмотрим последовательность чисел, называемых числами Фибоначчи. В нее входят f₀ = 0, f₁ = 1, f₂ = 1, f₃ = 2, , f₄ = 3, f₅ = 5, f₆ = 8, ... , где (n + 1)-е число Фибоначчи определяется как f_{n + 1}= f_n + f_{n – 1} (для n ³ 1). Пусть a = (1 + )/2 и требуется доказать, что f_n £ a^{n – 1} для любого неотрицательного числа a. Для доказательства используем метод строгой индукции по n. Так как доказывается высказывание о неотрицательных числах, а принцип индукции сфо-рмулирован для положительных, используем очевидную модификацию метода.

1. Для n = 0 необходимо показать, что f₀ £ a^{0 – 1} . Это справедливо, так как f₀ = 0 = a^–1. Необходимо рассмотреть особый случай, когда n = 1. Здесь мы имеем f₁ = 1 £ 1=a⁰ = a^1–1.

2. Предположим, что f_m £ a^{m – 1} справедливо для всех неотрицательных целых чисел m = 0, 1, 2, ... , n. Нужно показать, что f_n+1 £ a^{(n + 1) – 1} также справедливо. По гипотезе индукции f_n £ a^{n – 1} и f_n–1 £ a^{(n – 1) – 1}. Поэтому

f_{n + 1} = f_n + f_{n – 1} £a^{n – 1} + a^{n – 2} = a^{n – 2} × (a+1).

Обратите внимание, что

a² = a + 1.

Фактически мы так и выбирали a, чтобы выполнялось условие a + 1 = a². Поэтому мы получаем

f_{n + 1} = f_n + f_{n – 1} £ a^{n – 2} × (a+1) = a^{n – 2} × a² = aⁿ = a^{(n + 1) – 1} .

что и требовалось доказать.

Отметим, что необходимо было знать, что и f_n, и f_n–1 удовлетворяют гипотезе индукции. Только в этом случае доказательство возможно. Одного только знания о справедливости высказывания для f_n недостаточно. Таким образом, строгая индукция нам необходима по существу. Отметим также, что в данном частном случае нам потребовалось доказывать, что f₀ £ a⁰ и f₁ £ a¹; мы не можем записать f₁ как f₀ + f_–1 , так как f_–1 не существует.

Упражнения

9. Простым числом называется положительное число, делящееся без остатка только на 1 и на само себя. Попытаться доказать самостоятельно, что каждое положительное число n можно представить в виде произведения одного и более простых чисел, используя строгую индукцию по n. (Подробное решение этой задачи приведено в [2], [3].)

10. Изменить приведенный в данном разделе принцип индукции для доказательства справедливости высказывания S(n) для целых чисел n, удовлетворяющих условию n ³ n₀, а не только для любых положительных целых чисел.

11. Используя простую индукцию, докажите справедливость следующих формул:

а) для всех неотрицательных целых n;

б) для любого положительного числа n;

в) всех неотрицательных целых чисел n.

12. Используя метод строгой индукции, докажите справедливость следующих формул:

а) , где для любого положительного a;

б) всех неотрицательных n.

13. Найдите ошибку в следующем доказательстве. Мы хотим доказать, что a ^{n – 1} = 1 для любого положительного числа n. Используем строгую индукцию:

1. Для п = 1 эта формула справедлива, так как a ^{n – 1} = a ^{1 – 1} = a ⁰ = 1.

2. Предположим, что высказывание справедливо для 1, 2, 3, ..., п, т.е. a ⁰ = 1, a ¹ = 1, a ² = 1, a ^{n – 1} = 1. Нужно показать, что a ^{(n +1) – 1} = 1:

a ^{(n +1) – 1} = a ⁿ = a ¹ · a ^{n – 1} = 1 · 1 = 1.

(По гипотезе индукции)

Тема 2. ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ
БЛОК-СХЕМ ПРОГРАММ

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: