Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 10
Понятие алгоритма принадлежит к числу основных понятий математики. Под алгоритмом понимают точное предписание о выполнении в определенном порядке системы операций для решения всех задач некоторого данного типа.
Простейшими алгоритмами являются правила, по которым выполняется та или другая из четырех арифметических операций в десятичной системе счисления.
Рассмотрим правила сложения целых чисел в десятичной системе счисления. Этот алгоритм перерабатывает выражение, записанное с использованием цифр 0,1,...,9. Результатом является выражение, записанное с помощью цифр 0,1,…,9. Таким образом, мы имеем процедуру преобразования некоторых символьных входов (цифр, означающих слагаемые) в определенные символьные выходы (цифры, означающие сумму). Аналогичная ситуация имеет место и для остальных арифметических операций. В общем случае понятно, что алгоритм есть преобразование каких-то входов, записанных с помощью некоторых символов, в выходы, записанные тоже с помощью символов. Грубо говоря, алгоритм - это детерминированная процедура, которую можно применять к любому элементу некоторого класса символьных входов и которая для каждого такого входа дает через конечное число действий (шагов) соответствующий
Существенными чертами неформального понятия алгоритма оказываются следующие:
1 - алгоритм задается как набор инструкций конечных размеров, т. е. его можно описать конечным набором слов и специальных символов;
2 - имеется вычислитель, обычно человек, который умеет обращаться с инструкциями и производить вычисления;
3 – алгоритм имеет некоторое число входных данных;
4 - имеется возможность для выделения, запоминания и повторения шагов вычисления;
5 - для каждого данного входа вычисление (преобразование входа) производится по данным инструкциям;
6 – с помощью алгоритма получается одно или несколько выходных данных.
Легко заметить аналогию с цифровыми вычислительными машинами.
Отметим, что алгоритм обладает также свойством массовости, т.е. он применяется для решения множества однотипных задач, а не одной задачи. Например, правила сложения чисел позволяют производить сложение любых действительных чисел.
Особо отметим, что задание алгоритма предполагает, что процесс применения алгоритма к входам (решение задачи с помощью алгоритма) является механическим, т.е. процедура преобразования входов не требует для своего осуществления никакой изобретательности.
Эти рассуждения выявляют некоторые свойства алгоритма, но не дают достаточно точного определения алгоритма.
Алфавитом называется всякое непустое множество символов, а сами символы алфавита называются буквами.
Примером алфавита может служить конечное множество символов или, например, русский алфавит.
Словом в данном алфавите А называется всякая конечная последовательность букв алфавита А.
Пустая последовательность букв называется пустым словом и обозначается через Λ.
Если Р обозначает слово аbb и Q обозначает слово bb, то пусть РQ обозначает слово аbbbb, аналогично для любых слов Р и Q запись РQ обозначает слово, полученное из слов Р и Q, если сразу за Р записать слово Q.
Ясно, что для любого слова Р имеем РΛ=ΛР=Р.
Алфавит А называется расширением алфавита В, если . Если алфавит А есть расширение алфавита В, то, очевидно, всякое слово в алфавите В является также словом и в алфавите А, обратное верно не всегда.
Будем говорить, что слово Р входит в слово Q, если Q=R1PR2, где R1 и R2 любые, может быть и пустые слова. Слово Р может входить в слово Q несколько раз, первым вхождением будем считать самое левое вхождение.
Под алгоритмом в алфавите А понимается алгоритм, входами и выходами которого являются слова в алфавите А. Таким образом, алгоритм в алфавите А представляет собой потенциально осуществимое преобразование слов в данном алфавите А.
Алгоритмы обозначаются заглавными полужирными буквами (A, B, С,...).
Пусть Р слово в алфавите А. Говорят, что алгоритм A применим к слову Р, если применение его к слову Р приводит через конечное число шагов к некоторому слову Q. При этом слово Q обозначается через A(Р). Если процесс переработки (преобразования) слова Р бесконечен, то считается, что алгоритм не применим к этому слову.
Два алгоритма A и B в одном и том же алфавите С называются вполне эквивалентными в алфавите D , если для любого слова Р в алфавите D либо оба алгоритма не применимы к Р, либо применимы и их результаты совпадают: A(Р) = B(Р). То, что алгоритмы A и B вполне эквивалентны в алфавите D, обозначается следующим образом:
3. Нормальный алгоритм (алгоритм А. А. Маркова)
Опыт изучения и применения математики показывает, что все известные алгоритмы можно разбить на простейшие шаги - элементарные операции. В качестве элементарной операции, на базе которой будут строиться нормальные алгоритмы, выделим подстановку одного слова вместо другого.
Пусть задан алфавит А, не содержащий в качестве букв символов "•" и "→", и пусть Р и Q слова в алфавите А. Тогда выражения Р→Q, P→•Q называются формулами подстановки в алфавите А.
Формула подстановки Р→Q называется простой подстановкой и означает, что вместо Р нужно подставить слово Q и перейти к следующей подстановке.
Формула подстановки Р→•Q называется заключительной подстановкой и означает, что вместо Р нужно подставить Q и закончить процесс преобразования.
Пусть Р→(•)Q означает любую из формул подстановки Р→Q или Р→•Q.
Нормальный алгоритм в алфавите А считается заданным, если задана конечная таблица (схема) формул подстановок слов алфавита А:
n ≥ 1, Pi и Qi, (1≤i≤n) слова в А, причем согласно этой таблице (схеме) формул подстановок можно осуществлять преобразование слов алфавита А следующим образом.
Пусть Ro слово в алфавите А. Если ни одно из Р1,Р2,...,Рn не входит в Ro, то процесс применения В к Ro заканчивается и его результатом считается слово Ro. Если хотя бы одно из Р1,Р2,...,Рn входит в Ro, то отыскиваем самую первую (в порядке следования в таблице) формулу подстановки, такую, что Рk входит в Ro. Совершаем подстановку слова Qk вместо самого левого вхождения слова Рk в слово Ro. Пусть R1 - результат такой подстановки. Если использованная подстановка Рk→(•)Qk - заключительная, то работа алгоритма заканчивается и его результатом считается R1. Если Рk→(•)Qk - простая формула подстановки, то применим к R1 тот же поиск, который был только что применен к Ro, и так далее. В случае, когда через конечное число шагов процесс преобразования закончится, то полученное слово Ri и является результатом. Если же процесс переработки слова Ro бесконечен (никогда не заканчивается), то считаем, что алгоритм не применим к слову Ro.
Нормальный алгоритм над алфавитом А отличается от нормального алгоритма в алфавите А только тем, что в словах Рi и Qi (1≤i≤n) могут использоваться не только буквы из алфавита А, но и буквы, не принадлежащие алфавиту А.
Рассмотрим несколько примеров нормальных алгоритмов.
1. Пусть А={a,b,c}. Таблица формул подстановок
задает некоторый нормальный алгоритм В в алфавите А. Если взять слово Ro=bb, то В преобразует его сначала с помощью подстановки (3) в слово сb, затем, вновь применяя подстановку (3) получим сс. Далее, по заключительной подстановке (2), получим с. Это слово и будет В(Ro).
Если исходное слово Ro будет содержать букву а, то В не применим к Ro, ибо подстановка (1) будет применяться безостановочно.
2. Пусть А={a,b,c}. Рассмотрим таблицу формул подстановок
Это таблица, очевидно, задает нормальный алгоритм над алфавитом А, ибо β ∉ А. Если взять произвольное слово Ro в А, то к нему сначала подстановки (1),(2) и (3) не применимы, так как слов βа, βb и βс в слове Ro быть не может. Подставив вместо самого левого пустого слова (Λ) в Ro слово β по (5), имеем βRo. Если первой в Ro стоит буква а, то применяем подстановку (1), если же первая буква - b, то применяем подстановку (2), а если первая с, то применяем (3) и перемещаем β за первую букву в слове Ro. Повторяя этот процесс столько раз, сколько букв в слове Ro, получим Roβ. По подстановке (4) окончательно имеем Roa, т.е. этот алгоритм приписывает к произвольному слову Ro в алфавите А справа от Ro букву а.
В рассмотренном алгоритме В подстановки (1),(2) и (3) служат для перестановки местами β и а или β и b или β и с, т.е. для перестановки β с любой буквой алфавита А. Тогда можно ввести для нашего алгоритма В более краткую форму записи:
Здесь запись (1*): βx → xβ применена для обозначения подстановок (1)-(3) в В.
Пусть А={a1,a2,...,an}, P, Q и R слова в алфавите А. Договоримся, что запись вида РхQ → (•)R обозначает таблицу подстановок:
3. Пусть заданы алфавиты А и В, буква α не входит в А и в В, и пусть a1,a2,...,ak - фиксированные буквы из алфавита А, а Q1,Q2,...,Qk - фиксированные слова в алфавите В. Рассмотрим нормальный алгоритм в алфавите , задаваемый таблицей
Этот алгоритм в любом слове Р (алфавита А) все встречающиеся там буквы a1,a2,...,ak - заменяет на слова Q1,Q2,...,Qk соответственно. Если же в Р букв a1,a2,...,ak нет, то оставляет его без изменения.
Пусть М={1,*}. Любое неотрицательное целое (натуральное) число можно записать (обозначить) в алфавите М словом, состоящим из n+1 букв 1:
число 0 обозначим словом 0=1,
число 1 обозначим словом 1=11,
.............................
число n обозначим словом
Слова будем называть цифрами. Поставим теперь в соответствие всякому вектору (n1,n2,...,nk), где n1,n2,...,nk - натуральные числа, слово в алфавите М, которое обозначим через . Так, например, (1,2,3 обозначает слово 11*111*1111.
4. Нормальный алгоритм
как легко убедиться, применим только к тем словам в алфавите М, которые суть цифры, и переводит любое слово в , т.е. для любого натурального n. Заметим, что алгоритм A0 не применим к пустому слову.
5. Нормальный алгоритм
очевидно, тоже применим только к тем словам в алфавите М, которые суть цифры, и преобразует любое слово в слово , т.е. для любого натурального n. Алгоритм A1, как и A0, не применим к пустому слову.
4. Функции частично вычислимые и вычислимые по Маркову
Функция f(x) называется частично определенной на множестве M, если значения этой функции определены не для всех х из M.
Функция f называется арифметической, если ее значения и значения её аргументов являются целыми неотрицательными числами, т.е. область определения аргументов и область значений функции есть множество натуральных чисел.
Положим, как и раньше, алфавит М={1,*}.
Пусть ϕ частично определенная арифметическая функция от n аргументов. Положим, что существует некоторый алгоритм (не обязательно нормальный) Aϕ в алфавите М, позволяющий вычислять значения этой функции всякий раз, когда значение функции существует, т.е. тогда и только тогда, когда хотя бы одна из частей этого равенства определена. При этом считаем, что алгоритм Aϕ не применим к словам, отличным от слов вида . Назовем функцию ϕ частично вычислимой по Маркову функцией, если существует нормальный алгоритм B над М, вполне эквивалентный Aϕ относительно алфавита М.
Иными словами, n-аргументная функция ϕ частично вычислима по Маркову тогда и только тогда, когда существует нормальный алгоритм, позволяющий вычислить значение ϕ(k1,k2,...,kn) для любых совокупностей значений х1=k1, х2=k2,..., xn = kn, при которых ϕ(k1,k2,...,kn) существует.
Если функция определена всюду, т.е. определена для любой совокупности значений своих аргументов, и является частично вычислимой по Маркову, то назовем ее вычислимой по Маркову. Таким образом, n-аргументная функция ϕ вычислима по Маркову тогда и только тогда, когда существует нормальный алгоритм, позволяющий вычислить значение ϕ(x1,x2,...,xn) для любых совокупностей значений x1,x2,...,xn.
Ранее показано, что для всюду определенных арифметических функций
существуют нормальные алгоритмы, вычисляющие их значения (примеры 4, 5). Следовательно, эти функции являются вычислимыми по Маркову.
5. Замыкание, распространение нормального алгоритма
Пусть A - произвольный нормальный алгоритм в алфавите А:
Замыканием алгоритма A называется алгоритм А•, полученный из A добавлением формулы подстановки Λ→•Λ в качестве последней подстановки, т.е.
Любой нормальный алгоритм заканчивает процесс переработки слова либо после применения заключительной подстановки, либо если все слова Р1,Р2,Р3,..., Рn не содержатся в слове, полученном при предыдущем шаге. Подстановка Λ→•Λ применима к любому слову. Следовательно, алгоритм А• заканчивает переработку слов всегда по заключительной подстановке, которая есть либо некоторая из подстановок Pi→(•)Qi (1≤ i≤ n) либо Λ→•Λ.
Отметим, что подстановка Λ→•Λ, добавленная к A для получения А•, стоит последней. Поэтому эта подстановка будет применяться только тогда, когда не применимы все подстановки алгоритма A, причем применение Λ→•Λ к любому слову не изменяет этого слова. Следовательно, результаты применения алгоритмов A и А• к любому слову в А будут совпадать, т.е. алгоритмы A и А• вполне эквивалентны.
Пусть A - нормальный алгоритм в алфавите А1, а алфавит А2 является расширением А1, т.е. . Тогда можно рассмотреть нормальный алгоритм A# в алфавите А2 с той же самой схемой, что и A . Очевидно,
, (1)
т.е. A и A#вполне эквиваленты относительно А1. Нормальный алгоритм A# будем называть естественным распространением A на алфавит А2.
В некоторых случаях удобнее, чтобы алгоритм A#, удовлетворяющий (1), был не применим к тем словам в А2, которые не являются словами в А1. Этого легко достигнуть, приписав к схеме A сверху формулу вида x→x, где x - любая буква из А2\ А1. Получившийся нормальный алгоритм называют формальным распространением A на алфавит А2. Очевидно, что формальное распространение алгоритма A вполне эквивалентно алгоритму A относительно А1 и не применимо к тем словам в А2, которые не являются словами в А1.
Использование возможности распространения нормального алгоритма на более широкий алфавит позволяет во многих случаях опускать без особого ущерба точности упоминание об алфавитах, в которых строятся конкретные нормальные алгоритмы.
6. Операции над нормальными алгоритмами
Композиция алгоритмов. Пусть A и B два алгоритма в алфавите А. Композицией алгоритмов A и B в алфавите А называют алгоритм C такой, что
Таким образом, композиция алгоритмов A и B представляет собой алгоритм, получающийся в результате последовательного применения алгоритмов к заданному слову Р, что можно продемонстрировать следующей блок-схемой
Композиция алгоритмов A и B обозначается как:
Пусть A1,A2,...,An - алгоритмы в алфавите А, тогда под An°An-1° ... °A1 будем понимать следующее: An°(An-1°(...°(A3°(A2°A1))...)).
Теорема 1. Композиция нормальных алгоритмов A1,A2,...,An в алфавите А есть снова нормальный алгоритм (над алфавитом А).
Теорема 2. Пусть A1,A2,...,An - нормальные алгоритмы в алфавитах A1,A2,...,An соответственно и пусть А - объединение этих алфавитов. Тогда существует нормальный алгоритм B над А, называемый соединением алгоритмов A1,A2,...,An, такой, что
где есть естественное распространение Ai на А.
Разветвление алгоритмов. Пусть заданы алгоритмы A и B в алфавите А и задано некоторое условие U. Тогда можно задать предписание следующего типа: для данного слова Р в алфавите А проверить, удовлетворяет ли оно условию U, если удовлетворяет, то к Р применить алгоритм A , в противном случае применить к Р алгоритм B.
Будем считать, что условие U всегда задано с помощью какого-то алгоритма C в алфавите А в следующем виде:
условие U для слова Р выполнено, если C(Р)=Λ,
условие U для слова Р не выполнено, если C(Р)≠Λ.
При таком задании условия U описанное выше предписание будем считать разветвлением алгоритмов в алфавите А. Точнее, пусть A, B и C-алгоритмы в алфавите А. Разветвлением алгоритмов A и B называется алгоритм V в А, не применимый к Р, если не применим к Р алгоритм С и такой, что`
.
Будем говорить, что это разветвление алгоритмов управляется алгоритмом C .
Теорема 3. Разветвление нормальных алгоритмов, управляемое нормальным алгоритмом, является нормальным алгоритмом.
Повторение алгоритмов. Во многих случаях требуется повторить одну и ту же процедуру многократно, каждый раз применяя ее к результату, полученному на предыдущем шаге. Процедуру повторяем до выполнения некоторого условия U. Будем считать, что условие U задается с помощью алгоритма, как и выше. Такая процедура будет задавать повторение алгоритма. Более точно: пусть A и C - алгоритмы в алфавите А и пусть Ро - произвольное слово в А. Применим к Ро алгоритм A. Получим некоторое слово Р1=A(Ро), если С(Р1)=Λ, то процесс заканчивается. Если C(Р1)≠Λ, то к Р1 применяем A, получаем Р2=A(Р1)=A(A(Ро)). Если C(Р2)=Λ, то процесс заканчиваем. Если C(Р2)≠Λ, то к Р2 применяем A, и т.д. Определенный таким образом алгоритм называется повторением алгоритма A, управляемым алгоритмом C.
Повторение алгоритма можно представить следующей блок схемой
Теорема 4. Повторение нормального алгоритма, управляемое нормальным алгоритмом, есть нормальный алгоритм.
Основным и важнейшим результатом является то, что различные операции (комбинации) над нормальными алгоритмами снова приводят к нормальному алгоритму.