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

Министерство образования и науки Российской Федерации

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

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

Часть 1.

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

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

НОВОСИБИРСК

2006

Рецензенты:        

       

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20 + 21 + 22 + … + 2n = 2n+1 – 1.

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

1.  Доказать,  что  20 = 20+1 – 1.  Это  очевидно,  так как

20 = 1 = 20+1 – 1 = 21 – 1= 2 – 1 = 1.

2. Доказать, что если для всех неотрицательных целых n справедлива формула 

20 + 21 + 22 + … + 2n = 2n+1 – 1,

то справедлива и формула 

20 + 21 + 22 + … + 2n + 2n+1 = 2(n+1)+1 – 1.

Высказывание 20 + 21 + 22 + ... + 2 n = 2n+1 – 1 называется гипотезой индукции. Второе положение доказывается следующим образом:

20 + 21 + 22 + … + 2n + 2n+1  = (20 + 21 + 22 + … + 2n ) + 2n+1 =

= (2n+1 – 1) + 2n+1 = ( 2n+1 + 2n+1 ) – 1 =2⋅2n+1  – 1 = 2n+2 – 1 = 2(n+1)+1 – 1.

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

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

Поскольку мы доказали справедливость двух утвержде­ний, то по индукции формула

20 + 21 + 22 + … + 2n = 2n+1 – 1.

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

Иногда нужно доказать справедливость высказывания S(n) для целых n, удовлетворяющих условию n0≤n≤m0. Так как между n0 и m0 находится конечное число целых чисел, то справедливость S(n) можно доказать простым перебором всех возможных вариантов. Однако легче, а иногда и необходимо (если, например, мы не знаем конкретных значений n0 и m0) доказать S(n) по индукции. В этом случае можно воспользоваться одним из двух вариантов индукции:

Простая нисходящая индукция

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

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

Простая восходящая индукция

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

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

Интуитивно понятно, что этого достаточно для доказательства справедливости S(n) при любых n, удовлетворяющих условию n0 ≤n≤m0.

Упражнения

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

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

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

.

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

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)-й камешек из этой кучи, то останется куча из п камешков:

По гипотезе индукции все камешки в такой куче имеют один цвет. Представим себе, что вместо последнего мы выбрасываем первый камешек из кучи: