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