Д. Кнут - Искусство программирования том 1 (1119450), страница 11
Текст из файла (страница 11)
М. ТпНпб) о проверке корректности алгоритмов в Нерог! о/ а СопГегепсе оп Н!8Л Вреес( Аи!осла!!с Са!си!аНп8 МасЛ!паз (Сапл)лгЫбе Вп!уч 1949), 67-68 н рисунки. Эта работа переиздана с колы ментариями Ф. Л. Моррис (Е. !.. МогНз) и К. Б. Джонс (С. В. Зопез) в Аппа!з о/ ГЛе Н!з!огу о/ СотриНп8 6 (1984), 139-143.] В понимании теории программ большую помощь могут оказать одии-два оператора, описывающих состояние машины в тщательно вьшрэиные моменты вРемени ...
Высшая Форма тЕОрЕтичЕСкОгО мЕтОДа — этО поедоставление для утверждений неопровержимых математических доказательств. А высшая Форма экспериментальиого метода — это тестиОоеэиие программы иэ машине для различнык начальных условий и объявление ее гоРной, если утверждения выполняются в каждом случае. Каждый из методов имеет свои недостатки, — А.
М. ТЬЮРИНГ (А. М, ТОР!Нб), Реггапп Мага ! Ргодгагпгп!пд Мариаl (1950) УП!эАЖНЕНИЯ 1. (05) Объясните, как можно модифицировать идею доказательства методом математической яцлукцяи в случае, если некоторое утверждение Р(п) нужно доказать для всех неотрицательных целых чисел, т. е, для и = О, 1, 2, ..., а не для и = 1, 2, 3, .. 2. (!5) Найдите ошибку в следующем доказательстве. "Теорема. Пусть о — любое положительное число. Двя всех целых положительных чисел п имеем а" ' = 1. Докаэагпельсглеа Если и = 1, а" ' = а' ' = ае = 1. По индукции предполагая, что теорема верна для 1, 2, ..., и, имеем ,„+„, „а" 'ха" ' 1х1 — — =1 еы-1) — 1 1 1 1 3 1 + — + .+ 1х2 2хЗ (и — 1)хп 2 и Доказательсглео.
Используем индукцию по п. Для и = 1 доказательство очевидно: 3/2— 1/п = 1/(1 х 2). Предполагая, что теорема верна для п, имеем: 1 1 + + (и — 1) хп и х(п+1) 3 1 1 3 1 у1 1 1 3 1 — — — + = — — — + 2 и п(п+1) 2 п 'лп и+1/ 2 я+1 1х2 4.
(20] Докажите, что числа Фнбоначчн удовлетворяют не только соотношению (3), но и неравенству г„> 4" следовательно, теорема верна также для п + 1У 3. [!3) Следующее доказательство по индукции выглядит корректным, но по непонятной причине для п = б левая часть уравнения дает +и+ м+ те+ за е а~ра"~" л е 3. В чем же ошибка? "Теорема. 5. [21] Простпое число — это целое число, большее единицы, которое делится только на 1 и на само себя. Используя данное определение н метод математической индукции, докажите, что любое целое число, большее единицы, можно записать как произведение одного или нескольких простых чисел. (Для удобства будем считать, что простое число— это "произведение" одного простага числа, т. е.
его самого.) О. [20] Докажите, чта если соотношения (6) справедливы непосредственно перед выполнением шага Е4, то оин верны и после его выполнения. 7. [2З] Сформулируйте и докажите па индукции правило вычисления сумм 1г, 2г — 1г, 3г 2г» 1г 4г 3г+2г 1з 5г 4г» 3г 2г» 1ги т д. В. [25] (а) Докажите по индукции следующую теорему Никомаха (%сошасЬиз) (ок. 100 г.
н. э.): 1з = 1, 2 = Зтб, 3 = 7+9+11, 4 = 13+15+17+19 ит. д,* (Ь) Воспользуйтесь этим результатом для доказательства замечательной формулы 1 +2 +. +п = (1+2+ +и) . з з з г [Замечание. Интересная геометрическая интерпретация этой формулы, предложенная автору Р. В. Флойдом, показана на рис. 5. Идея этого построения связана с теоремой Никомаха и рис. 3. Другие "наглядные" доказательства можно найти в книгах Мартина Гарднера (Магг!и Сагс!пег), Клас»ей 17оабйлозз (Ь»е»г з'ог)п Ргеешаи, 198б), СЬаргег 1б, а также Л.
Н. Сопъау, В. К. Сиу, ТЬе Воа!» ау ХшпЬегз (зь»езг з'ог)с: Сорегп!сиз, 1990), СЬаргег 2.] Сторона = 5+5+5+5+5+5 = 5 (5+1)' Сторона = 5+4+3»-2+1+1+2+3+4+5 = 2(1+2+ + 5) Площадь = 4 1 +4 2 2 44 3 3 +4 4 4 +4 5 бг = 4(1 +2 +. +5з) Рис. 5. Геометрическая интерпретация упр. 8, (Ь) прн п = 5. 9. [20] Докажите по индукции, что если 0 < а < 1, то (1 — а)" > 1 — па. 10. [М22] Докажите по индукции, что если и > 10, то 2" > и . 11. [МЯО] Найдите и докажите простую формулу для следующей суммы: 1з 3 5з ( — 1)" (2п.»- 1)з 1»+4 34+4 54+4 + + (2п+ 1)» + 4 12.
[М25] Покажите, как можно обобщить алгоритм Е, чтобы, как было указано в тексте, для него допускалнсь входные значения вида и+ от»'2, где и н о — целые числа, и вычисления по-прежнему выполнялись элементарным образом (т. е. ие выражая иррациональное числа з/2 бесконечной десятичной дробью), Докажите, что прн пз = 1 и п = з/2 выполнение алгоритма никогда не закончится. ь 13. [М23] Обобщите алгоритм Е, введя новую переменную Т и добавив в начале каждого шага операцию Т»- Т+ 1. (Таким образом, переменная Т вЂ” счетчик выполненных шагов.) * требуется доказать формулу (пг — и + 1) + (пг — п + 3) + + (пг + п — 1) = пз.
— — прим. оерсь. Предположим, что первоначальное значение Т равно нулю, поэтому утверждение А1 на рис, 4 примет вид т > О, и > О, Т = О. Аналогично к А2 следует добавить дополнительное Ъ, условие Т = 1. Покажите, как добавить к утверждениям дополнительные условия таким образом, чтобы из любого утверждения А1, А2,, Аб следовало, что Т < Зи, и чтобы можно была провести доказательство по индукции.
(Следовательно, вычисления должны закончиться лгаксимум через Зи шагов.) 14. [50) (Р. В. Флойд) Составьте компьютерную программу, йй вйюд которой подаются программы, написанные на некотором языке программирования, вместе с необязательными утверждениями н которая пытается сформулировать остальные утверждения, необходимые для доказательства корректности входной компьютерной программы.
Например, постарайтесь составить программу, с помощью которой люжно доказать корректность алгоритма Е, если даны только утверждения А1, Ад н Аб. Более подробную информацию об этом можно найти в статьях Р. В. Флойда и Дж. К. Кинга (1. С.
Кшб) (1Р1Р Сопкгеез ргосееббпйв, 1971). ь 1б. (НМ28] (Обабщеннал индукпал.) В тексте показано, как доказывать по индукции утверждения Р(и), зависящие от единственного целого числа и, но ничего не говорится о там, как доказывать утверждения Р(т, и), зависящие от двух целых чисел, В подобных случаях обычно используют что-то вроде "двойной индукции", и поэтому доказательство часто выглядит давольно запутанным.
Но на самом деле существует важный принцип доказательства, который является более общим, чем простая индукция, и применяется не толька в подобных случаях, но и тогда, когда утверждения нужно доказывать для несчетных множеств, например если нужна доказать Р(х) для всех действительных х. Этот общий принцип называется вполне упорядоченностью. Пусть "<" — отношение на множестве 2, удовлетворяющее следующим свойствам.
1) Для любых х, у и г из Н, если х < у и у м г, то х < г. й) Для любых х и у из Н выполняется ровно одна из следующих трех возможностей: х <у,хжулибоу-сх. Ш) Если А — любое непустое подмножество 5. то существует элемент х из А, такой, что х < у (т. е. х м у или х = у) для всех у из А. Говорят, что это отношение вполне упорядочивает множество Н. Например, очевидна, чта множество положительных целых чисел вполне упорядочено обычным отношением "меньше чем" ("<"). а) Покажите, что множество всех целых чисел не является вполне упорядоченным отношением "<". Ь) Определите на множестве всех целых чисел отношение вполне упорядоченности.
с) Является ли множества всех неотрицательных действительных чисел вполне упорядоченным отношением "<'у г() (Лекспкогрефический порядок.) Пусть множество 5 вполне упорядочено отношгниелг "-4" н пусть Т, п > О, — множество всех наборов (хм хг,..., х„) элементов хг нз 2. Определим отношение (хп хг,..., х„) -< (уп уг,..., У„), если существует некоторое (г, 1 < й < и, акое, что хг = уг для 1 < г < )г, а хл < ул в 5.
Будет ли отношение "<" вполне упорядочивать Т ! е) Продолжая п, (а), положим Т = ()юм Т; определим отношение (хпхг,.,.,х ) < (ум уз,, у ), если хг —— уг для 1 < у' < л и хл м ул для некоторого и < ппп(гп,и) или если т < и и хг = Уу Дла 1 < г < т. БУдетли отношение "-4» вполне УпоРЯдочивать Т? 1) Покажите, что отношение "-4" вполне упорядочивает множество Н тогда и только тогда, когда оно удовлетворяет приведенным выше условиям (1) и (й) и не существует бесконечной последовательности хм хг, хз, ..., такой, что хг+~ -4 х„для всех д > 1.
е) Пусть множество Я вполне упорядочено отношением "К" и пусть Р(х) — это утверждение, зависящее от элемента х из л. Покажите, что если Р(х) можно доказать, предполагая, что Р(у) верно для всех у К х, то Р(х) верно для всех х из 8. (Замечагшя. П (8) — это обещанное выше обобщение простой индукшги. Если Я вЂ”.это множество положительных целых чисел, то мы получаем простой случай математической индукции, рассмотренный в тексте. Причем нас просят доказать, что Р(1) верно, если Р(у) верно для всех положительных целых у < 1:, это то же самое, что просить нас просто доказать Р(1), поскольку Р(у) безусловно верно для всех таких у (таких у просто не существует). Итак, во многих случаях доказательство Р(1) не требует особой аргументации.
П. (с1) в сочетании с (8) дает нам довольно сильный метод и-мерной индукции для доказательства утверждений Р(тп..., т„), зависящих от и целых положительных чисел гпм ...,7по П. (Г) можно применить к компьютерным алгоритмам следующим образом. Если каждому состоянию вычисления х поставить в соответствие ааемент /(х), принадлежащий вполне упорядоченному множеству 5, таким образом, чтобы каждый шаг вычислений переводил состояние х в состояние у так, что /(у) < /(х), то алгоритм будет конечным.
Этот принцип обобщает рассуждения о строго убывающих значениях н, которые использовались при доказательстве конечности алгоритма 1.1Е.) 1.2.2. Числа, степени и логарифмы Давайте начнем с того, что поближе познакомимся с числами, с которыми нам придется иметь дело. Пелые числа — это , — 3, — 2, — 1, О, 1, 2, 3, (отрицательные, положительные и нуль).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
