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