AOP_Tom1 (1021736), страница 134
Текст из файла (страница 134)
Теперь пусть 6((т, п)) =. д((гп, и)) = (т.п); 6((т, п,4)) = (4); И((т, и, а,Ь. 1)) (а, 6,0, 1); 6((т,п, а,Ь,з.,2)) ж (а,Ь, г,2); 6((т,п, а,6, г,З)) = (а,Ь, г, 3); 6((т, п,о,Ь, г,4)) = 6 (Я1 т, и, а, Ь, г, 4) ) ); 6((т, п, а, Ь, 5) ) = (а, Ь, 6, 1); 1((гп, и, а, Ь, г, 3) ) = 2 ((т, и, а, Ь, т', 4) ) = 2; в остальных случаях у(д) = 1. Тогда Сз представляет Сь Заме юкил. Конечно, весьма заманчиво попытаться дать более простое определение, напРимеР такое. ПУсть д отобРажает О~ в 14з и должно выполнатьса только следУющее условие; для любой вычисляемой последовательности хе, хм.,.
метода С~ д(ха). ,д(х~). является подпоследовательностью вычисляемой последовательности метода Сг, начинающейся с д(хе). Но эта определение неадекватно; в приведенном выше примере в методе С~ первоначальные значения т и и забываются, а в методе Сз — нет. Если Сз представляет С~ с помощью функций д, 6, 1, а Сз представляет Сз с помощью функций д, 1г~, у~, то Сз представляет С~ с помощью функций д'~, 11', 1", где д (х) = д (д(х)) Ь (х) 4 й(6 (х)) и 1 (д) = ~' 1з(дь) е<ь<г1лпгр если да = д н де+~ = 1зб Омй(дь).
Следовательно, определешгае выше отношение является транзитивным. Если функция г ограничена, то будем говорить, что Сз непосредстеенко представляет Сп это отношение также является транзитивным. Отношение "Сз представляет С~" порождает отношение эквивалентности, при котором два метода вычислений эквивалентны тогда н талька тогда, когда их функции от входных данных являются изоморфными, Отношение "Сз непосредственно представляет С~" порождает более интересное отношение эквивалентности, которое, вероятно, отвечает интуитивно понятному представлению о том, что это "в сущности, тот же самый алгоритм". Об альтернативном подходе к моделированию речь идет в рабате В.
'гр. Р!оуд, В. Ве!бе!, ТЬс Валдиаде о1 Ьйасутез (Сошросег Яс!еосе Ргезз, 1994), раздел 3.3. РАЗДЕЛ 1.2.1 1. (а) Докажите Р(0). (Ь) Докажите, что Р(О),...,Р(п) влекут за собой Р(п+ Ц для всех и > О. 2. Теорема не доказана для а = 2. Если во второй части доказательства принять и = 1, то придется допустить, что а ' = 1. Если это условие выполняется (т. е.
а = Ц, то теорема действительно справедлива. 3. На самом деле правая часть уравнения должна иметь вид 1 — 1/и. Ошибка возникает при доказательстве случая и = 1, когда левую часть нужно считать либо не имеющей смысла, либо равной нулю (поскольку есть и — 1 слагаемых). б.
Если и — простое число, то очевидно, что оно является произведением простых чисел. В противном случае и разлагается на множители, т. е. и = Ьт для некоторых я и т, 1 < Й, гп < и. Поскольку и Ь, н пз меньше и, по индукции их можно записать как произведение простых чисел. Следовательно, п является произведением простых чисел, фигурирующих в представлениях Ь и пз.
6. Используя обозначения, представленные на рис, 4, докажем, что А5 влечет Аб. Эта очевидно, так как из А5 следует, что (о' — да)гл+ (Ь' — о6)п = (а'зп+ Ь'и) — д(аш+ Ьп) = с — дд = г. У. и'-(и — Ц'+ — (-Ц"1'=14.2+" +п=п(п+Ц/2. 8. (а) Покажем, что (пз — и+Ц+(пз — и+3)+ +(и +и — Ц равно пз. Этасумма равна (1+3+ - +(аз<-и — ц) — (1+3+ +(пз — и — ц) = ((из+и)/2) -((пз — и)/2) = и (мы воспользовались соотношением (2)).
Но требовалось дать доказательство по индукции, поэтому нужно использовать другой подход! Ддя и = 1 доказательство очевидна. Пусть и > 1; так как (и+ цз — (и+ ц = пз — и+ 2п, то, сравнивая слагаемые сумм для значений параметров и+ 1 и и, получвезк что (и+ ц-я сумма равна п-й сумме плюс 2 1» Ь+ ) ( +1) — ~', р раз а это равно и + 2п + и + Зп+ 1 = (и+ ц . (Ь) Поскольку первое слагаемое длн (и + ц-й суммы на два больше последнего слагаемого зьй суммы, то из соотношения (2) получаем, что 1 + 2 + . + пз равно сумме последовательных нечетных чисел от 1 до и + и — 1 = з з з (п(п+ ц/2) = (1-р 2+ .
+ п)з. 10. Для и = 10 доказательство очевидно. Если и > 10, то имеем 2"+' = 2 2" > (1+1/и) 2", а па предположению индукции это больше, чем (1 + 1/п)зпз = (и + цз. 11. (-Ц" (и+ Ц/(4(п+ Ц + Ц. 12. Единственным нетривиальным моментом такого обобщения нвляется вычисление целого числа о на шаге Е2.
Это можно сделать путем повторного вычитания, сводя задачу к выяснению, является ли и+ вз/2 положительным, отрицательным нли равным нулю, что уже не представляет особых проблем. Легко показать, что если и + оз/2 = в' + в'з/2, то в = и' и о = в', так как з/2— иррациональное число. Теперь ясно, что 1 н з/2 не имеют общего делителя, если лзы определим делилюсть в следующем смысле: и+о з/2 делит а(ичвз/2) тогда и только тогда, когда а — целое число.
Алгоритм, обобщенный подобным образом, вычисляет регулярную цепную дробь отношений его входов (см. раздел 4.5.3). (Зимечание. Расширим понятие делимости следующим образом: будем говорить, что в + оз/2 делит о(и + вз/2) тогда и только тогда, когда а имеет вид и' 4- в'з/2, где и' и и' — целые числа.
В этом случае сускесозеует способ обобщить алгоритм Е таким образом, чтобы он всегда был конечным. Действительно, если на шаге Е2 мы имеем с = и + вз/2 и 3 = и' + е'з/2, то получаем с/И = с(и' — и'ь/2)/(и'~ — 2е'~) = х + уз/2, где х и у— рациональные числа. Пусть теперь у = и" + е" т/2, где и" и е" — зто ближайшие к х и у целые числа, и положим г = с — дИ. Если г = и"' + е"'з/2, та )а"'з — 2е™) < )и'з — 2е'~~. Следовательно, выполнение алгоритма завершится через конечное число шагов. Более подробную информацию об этом можно найти в учебниках по теории чисел, в разделах, посвященных квадратичным евклидовым областям.] 13.
Добавьте "Т < 3(н — И) + йе к утверждениям АА А4, АА Аб, где Ь принимает значения 2, 3, 3, 1 соответственно. Добавьте также "И > О" к утверждению А4. 13. (а) Положим А = а в (ш); отсюда следует, что любое непустае вполне упорядоченное множества имеет иинимальный (или наименьший) элемент. (Ь) Пусть х -х у, если )х) < (у) или если )х) = )у) и х < О < у. (с) Нет, так как подмножество всех действительных положительных чисел не удовлетворяет условию (а(1). (Замечание.
Пользуясь так называемой аксиомой выбора, можно дать довольно сложное доказательства того, что любое множества можно вполне упорядочить каким-то образом; на до сих пар никто не определил явным образом отношение, которое вполне упорядочивает множество действительных чисел.) (б) Чтобы доказать для Т„свойства (ш), воспользуемся индукпией по н. Пусть А— непустое подмножества Т; рассмотрим Аи которое представляет собой множество первых компонент элементов А. Так как А~ — это непустое подмножество 5, а Я вполне упорядочена, та А~ содержит наименьший элемент х. Теперь рассмотрии А„, которое является подмножествам тех элементов из А, первая компонента которых равна х; А, можно считать подмножествам Т и если у всех ега элементов изъять первую компоненту.
Поэтому па индукции А содержит наименьший элемент (х,хм, ..,х„), который на самом деле является наименьшим элементом А. (е) Нет, хотя свойства (1) и (й) выполняются. Если Я содержит по меньшей мере два различных элемента, о -с Ь, то множество (Ь), (о,Ь), (о,о, Ь), (о,о,о,6), (а,а, а,а,6), не имеет наименьшего элемента. С другой стороны, Т можно вполне упорядочить, если определить в Т„отношение (хм..,,х ) и (ум...,у„) при т < п или (хм,..,х ) -( (ум..., у ) при нз = гь (Г) Пусть множество о вполне упорядочено отношением < Если такая бесконечная последовательность существует, то множества А, содержащее члены этой последовательности, не будет удовлетворять свойству (! 11), так как ни один элемент этой последовательности не может быть наименьшим.
Обратна, пусть и --отношение, удовлетворяющее ушювиям (1) и (О), но не (Й), и пусть А — непустае подмножество Я, не имеющее наименьшего элемента. Так как А — непустое, мы мажем найти х~ из А; так как х~ не является наименьшим элементом А, та существует хз из А, для которого хз ч хм так как хз тоже не является наименьшим элементом, мы мажем найти хз М хз и т. д. (б) Пусть А — множество ясех х, для которых утверждение Р(х) ложно. Если А не пусто, та она содержит наименьший элемент хе. Следовательно, Р(у) верно для всех у и хо.
Но отсюда вытекает, чта Р(хе) верно, следовательно, хе не принадлежит А (получаем противоречие), Таким образом, А должно быть пустын, т. е утверждение Р(х) всегда верна. РАЗДЕЛ 1.2.2 1. Такога числа нет; зшя любага положительного рашзональнога числа г можно указать меньшее число, например г/2. 2. Нет, если подряд идет бесконечно многа девяток; в этом случае согласно соотношению (2) десятичным представлением даннога действительного числа будет 1+.24ОООООО.... 3. -1/27, но в тексте раздела операция возведения в степень отрицательнык чисел не определена.
4. 4. 6. Для любого действительного числа существует единственное десятичное представление, поэтому х = у тогда и только тогда, когда т = и и И, = е, для всех ! > 1. Если х ф у, то нужно сравнивать т с и, И~ с еы Из с ез и т. дл когДа обнаружится первое неравенство, большая цифра будет принадлежать большему из чисел (х, у). 7. Можно воспользоваться нндукцией по х и сначала доказать эти правила для положительного, а затем для отрицательного х. Детали доказательства мы здесь опускаем.
О. Испытывая последовательно и = 0,1,2,, находим значение п, для которого и < и < (и+1) . Предполагая по индукции, что п,4,...,4ь ~ уже определены, находим цифру йэ из условия ')"- ~ ' ' ) и+ — + .+ — /! <и< ~п+ — +..+ — + — /! 10 1Оэ ( — ~ 10 10ь 10" / 9. ((Ьг7е)"г")~" = (((Ьггг)"г")") = ((Ьггг)")' = ((Ьг7Я)ч)" = Ь"", следовательно (Ьг7ч)"7" = Ь""гг". Таким образом, второе правило доказано. Теперь на основе второго правила докажем первое; Ьг~'Ьюв = (Ьмг")г" (Ь'дн)'" = (Ьмю)г"+~" = Ьг7гг"7". 10, Если !обш 2 = р/9, где р и д положительны, та 2г = 10г, а это невозможно, так как правая часть уравнения делится на 5, а левая нет, 11. Бесконечно многа! Независимо от того, сколько дано цифр десятичного представления числа х, мы все равно не знаем, будет ли 10 = 1.99999... илн 2.00000..., если цифры х соответствуют цифрам !обш 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
