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