AOP_Tom1 (1021736), страница 7
Текст из файла (страница 7)
и.), но хорошо известно, что ему не хватает определенности. Инструкции из кулинарных рецептов очень часто бывают неопределенными, например; "Добавьте ° щепотку соли". "Щепотка" определяется как количество, "меньшее '/в чайной ложки", и что такое соль, вероятно, тоже известно всем. Но куда именно нужно добавить соль — сверху? сбоку? Инструкции "Слегка потрясите, пока смесь не станет рассыпчатой" и "Подогрейте коньяк в маленькой кастрюльке" будут вполне понятны опытному повару, но они не годятся для алгоритма. Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер. Тем не менее программист может многому научиться, прочитав хорошую поваренную книгу. (Честно говоря, автор едва устоял перед искушением назвать настоящий том "Поваренная книга программиста"'.
Но, может, когда-нибудь он попытается написать книгу под названиеке "Алгоритмы для кухни".) Следует отметитги что для практических целей ограничение, состоящее в конечности алгоритма, в сущности, является недостаточно жестким. Используемый на практике алгоритм должен иметь не просто конечное, а достаточно ограниченное, разумное число шагов. Наприлеер, существует алгоритм определения того, люжет ли игра в шахматы всегда быть выиграна белыми при условии, что не было сделано нн одной ошибки (см. упр, 2.2.3 — 28). Этот алгоритм позволил бы решить проблему, представляющую огромный интерес для тысяч людей, но можно биться об заклад, что окончательный ответ на данный вопрос мы не узнаем никогда.
Все дело в том, что для выполнения указанного алгоритма требуется невероятно болыпой промежуток времени, хотя сам алгоритм и является конечныль В главе 8 будут обсуждаться конечные числе, которые велики настолько, что, в сущности, находятся за пределами нашего понимания*. На практике нам нужны не просто алгоритмы, а хорошие алгоритмы в широком смысле этого слова.
Одним из критериев качества алгоритма является время, необходимое для его выполнения; данную характеристику можно оценить по тому, сколько раз выполпяетгя каждый шаг. Другими критериями являются адаптируемость алгоритма к различным компьютерам, его простота, изящество и т. д. Часто решить одну и ту же проблему можно с помощью нескольких алгоритмов и нужно выбрать наилучший из них. Таким образом, мы попадаел~ в чрезвычайно * 1дава Ь не входит в данное трехтонное издание.-- Прим.
ред. интересную и крайне важную область анализа алгоритмов. Предмет этой области состоит в том, чтобы для заданного алгоритма определить рабочие характеристики. В качестве примера давайте исследуем с этой точки зрения алгоритм Евклида. Предположим, нам нужно решить следующую задачу: "Пусть задано значение и, а т может быть любым целым положительным числом. Тогда чему равно среднее число Т„выполнений шага Е1 алгоритма Е?".
Прежде всего необходимо убедиться в том, что задача имеет смысл, поскольку нам предстоит найти среднее при бесконечно большом количестве значений тп. Но совершенно очевидно, что после первого выполнения шага Е1 значение будет иметь только остаток от деления т на и. Поэтому все, что мы должны сделать для нахождения значения Т„,— это испытать алгоритм для т = 1, т = 2, ..., т = п, подсчитать суммарное число выполнений шага Е1 и разделить его на и. А теперь рассмотрим еще один важный вопрос, касающийся поведения Т„как функции от и: можно ли ее аппроксимировать, например, функцией -,'и или игй? На самом деле это чрезвычайно сложная и интересная математическая проблема, которая еще не решена окончательно; более подробно она будет рассмотрена в разделе 4.5.3.
Можно доказать, что при больших значениях п Т„ведет себя, как функция (12(!п2)/х~) !пп, т. е. она пропорциональна натуральному логарифму п. Заметим, что коэффициент пропорциональности нельзя просто взять и угадать; чтобы определить его, нужно затратить определенные усилия. Более подробно об алгоритме Евклида, а также о других способах вычисления наибольшего общего делителя будет говориться в разделе 4.5.2, Для обозначения области подобных исследований автор использует термин анализ алгоритмов.
Основная идея заключается в том, чтобы взять конкретный алгоритм и определить его количественные характеристики. Время от времени мы будем также выяснять, является ли алгоритм оптимальным в некотором смысле. Теория алгоритмов — это совершенно другая область, в которой, в первую очередь, рассматриваются вопросы существования или не существования эффективных алгоритмов вычисления определенных величин. До сих пор наше обсуждение алгоритмов носило достаточно общий характер, и, вероятно, "математически настроенный" читатель утвердился в мысли, что все предыдущие комментарии представляют собой очень шаткий фундамент для построения какой-либо теории алгоритмов, Поэтому давайте подведем итог данного раздела, кратко описав метод, с помощью которого понятие алгоритма можно строго обосновать в терминах математической теории множеств.
Формально определим метод вычислений как четверку Я,1, й,1), где Я вЂ” это множество, содержащее подмножества 1 н й, а 1- — функция, переводящая множество ~'„> в себя. Кроме того, 1 оставляет неподвижными точки множества Й, т. е. 1(у) равно я для всех элементов д из множества й. Эти четыре элемента, Я, 1, й, 1", представляют соответственно состояния вычисления, ввод, вывод и правило вычислений. Каждое входное значение х из множества 1 определяет вычисляемую последовательность хо, хг,хг,... следующим образом: хо — — х и хьэг — — 1(хь) для к. > О.
(1) Говорят, что вычисляемая последовательность заканчиваепгся через к шагов, если к — это наименьшее целое число, для которого хь принадлежит Й, и что она дает выходное значение хь для заданного х. (Заметим, что если хь принадлежит й, то и хь+~ принадлежит й, так как в этом случае хьы — — хь.) Некоторые вычисляемые последовательности могут никогда не заканчиваться, но алгоритм — это метод вычислений, который заканчивается через конечное число шагов для всех х из 1. Например, алгоритм Е в этих терминах можно формализовать следующим образом. Пусть элементами множества Я будут все величины (п), все упорядоченные пары (т,п) и все упорядоченные четверки (т,и,г,1), (т,и,г,2) и (т,п,р,З), где т, и и р — зто целые положительные числа, а г — неотрицательное целое число.
Пусть 1 — это подмножество всех пар (т, и), а й — подмножество всех величин (п). Определим функцию 1 следующим образом: 1 ((т, и)) = (т, п, О, 1); 1((п)) = (п); 1((т,и, г, 1)) = (т, и, остаток от деления т на и, 2); (2) 1((т,п,г,2)) = (п), если г = О, (ти,и,г,З) в противном случае; 1((т,п,р, 3)) = (п,р,р, 1). Соответствие между данной записью и алгоритмом Е очевидно.
В этой формулировке понятия "алгоритм" не содержится ограничение, касающееся эффективности, о котором упоминалось ранее. Например, Я может быть множеством бесконечных последовательностей, которые нельзя вычислить с помощью карандаша и бумаги, а 1 может включать операции, которые простой смертный сможет выполнить не всегда. Если мы хотим ограничить понятие "алгоритм" таким образом, чтобы в нем могли содержаться только элементарные операции, то введем ограничения на элементы Я, 1, й и 1, например, следующим образом. Пусть А— это ограниченное множество букв, а А* — множество всех строк, определенных на множестве А (т. е. множество всех упорядоченных последовательностей хатха... х„, где и > 0 и х, принадлежит А для 1 < 1 < п).
Идея заключается в следующем; закодировать состояния вычисления таким образом, чтобы они были представлены строками из множества А'. Теперь пусть Х вЂ” целое неотрицательное число, а Я— множество всех пар (а,у), где и принадлежит А, а у — целое число, 0 < 1 < Х. Пусть 1 — подмножество пар из Ч', для которых 1 = О, а й — подмножество пар из с1, для которых 1 = Х. Если В и и — строки из А', то мы будем говорить, что В входит в а, если и имеет вид оВы, где и и ы — некоторые строки. И в завершение определим функцию 1 с помощью строк В, ф и целых чисел а„, 6„0 < 1 < Х следующим образом: 1(а, у') = (а, ау), если В; не входит в и; 1(т,1) = (оф ы, Ь ), если и является самой короткой строкой, для которой а = од ах 1(а, Х) = (а, Х).
Метод вычислений, удовлетворяющкй этому определению, беэусловно, является эффективным. Кроме того, опыт показывает, что в таком виде можно представить любую задачу, которая решается с помощью карандаша и бумаги. Существует также много других по сути эквивалентных способов формулировки понятия эффективного метода вычислений (например, с помощью машины Тьюринга). Приведенная выше формулировка практически совпадает с той, которую дал Л. А. Марков (Маг)сон) в своей книге Теория алгорнфмов [Труды АН СССР, Ин-т математики. — 1954. — 42.— 376 с.], а впоследствии исправил и расширил Н.
М. Нагорный (Хабогпу) (Мл Наука, 1984). УПРАЖНЕНИЯ 1. [10] В тексте показано, как взаимно заменить значения переменных т и и с помощью символа замены, а именно — полагая Ф е- т, т е- и, и е- ь Покажите, как в результате ряда замен можно преобразовать чегаверку переменных (а,б,с,4) в (6,с,4,а). Другими словами, новое значение переменной а должно стать равным первоначальному значению Ь и т. д. Постарайтесь выполнить преобразование с помощью минимального числа замен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
