Бабенко - Основы численного анализа (947491), страница 8
Текст из файла (страница 8)
шш(у: д'(хд, ..., х„, у) .—. 1). Символически записываем д(хд ° х ) = тдк(д (хд, ..., х„, у) = 1). Операция перебора определена дк-дд лишь на подмножестве Го функций (', для которых у с описанным свойством существует тйш всех хд, ..., .то Е (о )". Это ставит перебор в особов положение по сравнению с другими двумя операциями. Бслн операция перебора продолжается бесконечно, го считается, что д(хд, ..., х„) для набора хд, ..., х„не определена. ьь дддноодсестддоом рекурсивных функций () Нд"д называется наименьк=о шее подмножество в () Гд" д, содержащее все ддростейшие функции л(х), к=о Глава К Постановка задач численного анализа 1~"', рг,, и замкнутое относительно операций подстановки, рекурсии и перебора, применяемого к эломентам из Р;, = () Ко" . Если перебор Цьэю в=О применяется к элементам, пе принадлежащим Ра, то получается множество часгаично рекурсивных функций.
Таблицу ряда таких функций читатель найдет в работе )86, с. 48 — 50), Переход от числовых рекурсивных функций к словарным производится следующим образом. Введем нумерацию слов совокупности б(Л). Номер пустого слова положим равным нулю. Символы алфавита занумеруем числами 1, 2, ..., р (в каком-либо порядке), и пусть а, символ с номером 1. По определению номером слова и = ае„а,., аы называем число с(ц) = 1е -ь Нр —...
—;1,р', Символами с(а) и оп условимся обозначать соответственно алфавитный номер слова а и слово, имеющее номер и,. Так как при фиксированном р каждое положительное число п представимо лишь одним способом -- в виде и = 1о М Нр+... —, 1,р' (1, = 1, 2, ..., р), то каждое число есть алфавитный номер одного и только одного слова совокупности б(Л). Числовая функция ((хм ..., хь) называется функцией, предстаавллюи1ей словарную функцию Е в нумерацни о, если ~"(охы ..., оз-ч) — о~(х1.....
хи) для всех натуральных хм ..., х„. Следовательно, г(йе .. цв) = о,)(с(сц), ..., с(ч„)), ,1(хы ..., х„) — -- с(г(охм ..., ах„)). ь1астичпая словарная функция Р' называется общерекурсивной или частпично рекурсивной, если таковой является числовая функция, представляющая Г. Теорема 1 [42). Класс нормально вы'вюлимых частичных функций,. заданных в произвольном алфавите Л, совпадает с классом всех одноместных частично рекурсивных словарных функций в алфавите Л. Аналогичное положение имеет место и для других формализаций понятия алгоритма, таких, как машина Тьюринга и автомат Неймана. Таким образом, классы функций.
вычислимых по Маркову, Тьюрингу, Нейману и другие, одни и те же и совпадают с классом частично рекурсивных функций. Следовательно, различные формализации понятия алгоритма оказываются эквивалентными. Последнему высказыванию можно придать еще и тот смысл, который заложен в теоремах равносильности. А именно, если имеются два типа алгоритмов, то строится процедура (имитационная программа), которая для каждого алгоритма одного класса строит алгоритм другого класса, имитирующий работу алгоритма из первого класса.
'З 3, Несколько гамсчаний о аонлтии алгоритма 33 Эти и некоторые другие соображения приводят к мысли считать алгоритмом одну из формализаций понятия алгоритма. В частности, А. А. Марков предлагает принять следующий принцип нормализации алгоритмоо: всякий алгорипгм о алфаоипгс А вполне экоиоалснгпсн относительно А нскоторомц нормальному алгоритмц над А.
Другими словами, всякий алгоритм нормализуем. Это высказывание не может быть доказано "- оно является гипотезой. Ее значение, прежде всего, состоит в том, что она уточняет общее, интуитивное понятие алгоритма через специальное, но четкое понятие нормального алгоритма в некотором алфавите. Однако принцип нормализации не только уточняет понятие алгоритма и определяет класс алгоритмических вычислимых функций, но и утверждает пригодность этого понятия. Принимая этот принцип, мы делаем экстраполяцию в будущее,.ибо утверждаем,что.,какой бы алгоритм ни был изобретен, он обязательно будет нормализуем. Принцип нормализации можно рассматривать как одну из форм тезиса Черча или основной гипотезы теории алгоритмов. На чем основывается уверенность в справедливости принимаемой гипотезы? В основном на опыте.
Все известные алгоритмы, которые были придуманы в течение нескольких тысячелетий истории математики, не содержат ни одного ненормализуемого алгоритма (или., что то же самое, ни одного алгоритма, которьш нельзя было бы задать в виде тьюринговской функциональной схемы). В математической литературе иногда принято сравнивать основную гипотезу теории алгоритмов (в нашем изложении это принцип нормализации) с физическими законами. Но такое сравнение двусмысленно. Хотя физические законы берутся из опыта, но в процессе развития науки происходит их уточнение. В этом смысле ничего подобного не должно происходить с основной гипотезой теории алгоритмов,ибо это свело бы па пот тс грапдиозпыс построения,которые па пей основаны.
5. Заключение. В вопросах конструирования вычислительных алгоритмов, разбираемых ниже, мы будем исходить из интуитивного представления об алгоритме. 1(ак правило, алгоритмы будут представлены и описаны на содержательном языка математики. Однако они легко могут быть записаны на каком-либо языке программирования высокого уровня, и тем самым в силу принципа нормализации они будут эквивалентны нормальному алгоритму. Поэтому на первый взгляд численный анализ и не нуждается в формализованном понятии алгоритма.
Однако цри более глубоком рассмотрении положение вещей оказывается не таким. В большом чиг ге разделов численного анализа основным объектом, с которым приходится работать, является таблица. Так, при решении краевых задач мы фактически всегда имеем дело с таблицами искомых функций и исходных данных. Но каждая таблица должна содержать не только код табулируемой функции, но и способ приближенного восстановления функции по ее коду.
А этот способ есть так называемый расшифроомоагощий алгоригпм. Поэтому лля построения теории табулирования необ- Глава й Постановка эадач численно»а анализа ходимо четкое понимание ситуации, .которая имеет место в общей тео- рии. й 4. Примеры алгоритмов; анализ алгоритмов 1. Алгоритм Евклида. 1(ак известно, развитие математики стимулировалось в большой степени необходимостью решения практических задач, и в древности математика была в значительной степени вычислительной. С давних времен известны способы решения многих задач, которые облечены в форму точных предписаний о выполнении в определенном порядке некоторой системы операций. Другими словами, мы имеом различные алгоритмы для решения разного рода задач, К такого рода алгоритмам относятся алгоритм Евклида„правила выполнения четырех арифметических операций в 6-инной системе счисления, алгоритм приближенного вычисления квадратного корня и т.
п. Рассмотрим вначале алгоритм Евклида (»Началагч книга 7, творемы 1, 2). Для отыскания наибольшего обшего делителя двух натуральных чисел т, и (НОД (т, п) или просто НОД) мы производим последовательно деление с остатком по следующей схеме: т =- пИ + тз, 㻠— гааз гз, з.—...
гэ .д з — 'г„..., гь 1 —. гады (1) Из этих формул сразу же получаем НОД (т., и) = гы так как, двигаясь по втой последовательности слева направо, замечаем, что общие делители чисел т, п одинаковы с делителями чисел г, гз, затем чисел гз, гл и т. д. и с делителями гы Алгоритм Евклида тесно связан с непрерывными дробями. В самом дело, при разложении рационального числа т~и в непрерывную дробь возникает последовательность (Ц., и мы имеем 1 аау ,'ф; й», ..., чь чг чйз+ 1 Яь Величины йд (э' = 1, 2, ..., к) называются неполнымн частныэнв,. Дроби вида (дз, '~уз....., й ~ (1' =-.
1. 2, ..., й) называются иодходлкйими дроблл»и. Нетрудно привести общую формулу для вычисления подходящих дробей. С втой целью введем многочлены Я„(хм ..., х„) от и переменных с целыми положительными коэффициентами. Эти многочлены определяются с помощью реку ррентной формулы ф(хм ..., х1) =- хЯ~ 1(хз, ..., х~) .- Я~ з(хз, ..., х~), 1 > 2, (2) и условий Яе = 1, Яз(хз) = хм Из формулы (2) следует, что ~В: 1з, П~ =Ма(Чм., Ча)(Ча- (Чз:, 1ь) 'о 4, Примера лзоритмоо; анализ олгоритмоо В салюм деле, очевидно, что 'Чз, ~ = Я~ (Чз ) Д2е, допУскаЯ, что фоРмУла (3) верна для непрерывной дроби длины меньше у, получаем ~Ч1 Чол ..: Чз'~ СЬ вЂ” т(Чз Чз) Чдз — 1(Чв: Чз) + 03 — в(Чъ; Чз) = Чз+ Оз 1(Ч2:, Чу) Яз — 1(Чх ° ° ° Чу) откуда и следует формула (3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
