Игошин Математическая логика и теория алгоритмов (1019110), страница 78
Текст из файла (страница 78)
Изложение в них доводится до доказательства равносильность этих трех формализаций понятия алгоритма. в 35 посвящен ток называемой обшей теории алгоритмов,, т.е. теории алгоритмов, не привязьпаемой ни к какакой конкретной формализации понятия алгоритма, в 36 — неразрешимым алгоритмическием проблемам. Завершается глава основывающимся на теории алгоритмов доказательством теоремы Геделя о неполноте формальной арифметики (см. $ 37).
й 31. Интуитивное представление об алгоритмах Алгоритмы вокруг вас. Понятие алгоритма стихийно формировалось с древнейших времен. Современный человек понимает под алгоритмом четкую систему инструкций о выполнении в определенном порядке некоторых действий для решения всех задач какого-то данного класса. Многочисленные и разнообразные алгоритмы окружают нас буквально во всех сферах жизни и деятельности. Многие наши действия доведены до бессознательного автоматизма, мы порой и не осознаем„что они регламентированы определенным алгоритмом — четкой системой инструкций. Например, наши действия при входе в магазин «Универсам» (сдать свою сумку, получить корзину с номером, пройти в торговый зал, заполнить корзину продуктами, оплатить покупку в кассе, предъявить чек контролеру, взять свою сумку, переложить в нее продукты, сдать корзину, покинуть магазин). Второй пример — приготовление манной каши (500 мл молока довести до кипения, при тщательном помешива- 312 нии засыпать 100 г манной крупы, при помешивании довести до кипения и варить 10 минут).
Автоматизм выполнения этих и многих других действий не позволяет нам осознавать их алгоритмическую сущность. Но есть немало таких действий, выполняя которые, мы тщательно следуем той или иной инструкции. Это главным образом непривычные действия, профессионально не свойственные нам. Например, если вы фотографируете один-два раза в год, то, купив проявитель для пленки, будете весьма тщательно следовать инструкции (алгоритму) по его приготовлению; «Содержимое большого пакета растворить в 350 мл воды при температуре 18— 20 'С.
Там же растворить содержимое малого пакета. Объем раствора довести до 500 мл. Раствор профильтровать. Проявлять 3 — 4 роликовых фотопленки», Второй пример: если вы никогда раньше не пекли торт, то„получив рецепт (алгоритм) его приготовления, постараетесь выполнить в указанной последовательности все его предписания. Большое количество алгоритмов встречается при изучении математики буквально с первых классов школы. Это прежде всего алгоритмы выполнения четырех арифметических действий над различными числами — натуральными, целыми, дробными, комплексными. Вот пример такого алгоритма: «Чтобы из одной десятичной дроби вычесть другую, надо: 1) уравнять число знаков после запятой в уменьшаемом и вычитаемом; 2) записать вычитаемое под уменьшаемым так, чтобы запятая оказалась под запятой; 3) произвести вычитание так, как вычитают натуральные числа; 4) поставить в полученной разности запятую под запятыми в уменьшаемом и вычитаемом».
Вот пример алгоритма сложения приближенных чисел. Найти сумму чисел р, д и з, где р = 3,1416, д 2,718 и з = 7,45. 1. Вьщелим слагаемое с наименьшим числом десятичных знаков. Таким слагаемым является число 7,45 (два десятичных знака). 2. Округлим остальные слагаемые, оставляя в них столько десятичных знаков, сколько их имеется в вьщеленном слагаемом: 3, 1416 = = 3,14; 2,718 = 2,72. 3. Выполним сложение приближенных значений чисел: 3,!4+ + 2,72+ 7,45 = 13,31.
Итак, р+ д+ з = 13,31. Немало алгоритмов в геометрии: алгоритмы геометрических построений с помощью циркуля и линейки (деление пополам отрезка и угла, опускание и восстановление перпендикуляров, проведение параллельных прямых), алгоритмы вычисления площадей и объемов различных геометрических фигур и тел.
При изучении математики в вузе были освоены процедуры вычисления наибольшего общего делителя двух натуральных чисел (алгоритм Евклида), определителей различных порядков, рангов 313 матриц с рациональными элементами, интегралов от рациональных функций, приближенных значений корней уравнений и систем и т.д. Все эти процедуры являются не чем иным, как алгоритмами. Наконец, в изучаемом курсе математической логики были рассмотрены алгоритмы разрешимости формализованного исчисления высказываний (см.
5 16) и разрешимости в логике предикатов (5 23). Одним словом, алгоритмы широко распространены как в практике, так и в науке и требуют более внимательного к себе отношения и тщательного изучения методами математической науки. Неформальное понятие алгоритма. Прежде чем перейти к математическому изучению понятия алгоритма, постараемся внимательно проанализировать примеры алгоритмов, выявить их общие типичные черты и особенности. Каждый алгоритм предполагает наличие некоторых начальных, или исходных, данных, а в результате применения приводит к получению определенного искомого резулыпата.
Например, в алгоритме с проявителем начальные данные — содержимое большого и малого пакетов, вода. Искомый результат — готовый к употреблению проявитель для пленки. При вычислении ранга матрицы начальными данными служит прямоугольная таблица, составленная из т . п рациональных чисел, результат — натуральное число, являющееся рангом данной матрицы. Далее, применение каждого алгоритма осуществляется путем выполнения дискретной цепочки (последовательности) неких элементарных действий.
Эти действия называют шагами, а процесс их выполнения называют алгоритмическим процессом. Таким образом, отмечается свойство дискретности алгоритма. Существенной чертой алгоритма является его массовый характер, т.е. возможность применять его к обширному классу начальных данных, возможность достаточно широко эти начальные данные варьировать. Другими словами, каждый алгоритм призван решить ту или иную массовую проблему, т.е. решать класс однотипных задач. Например, задача нахождения наибольшего общего делителя чисел 4 и 6 есть единичная проблема (можно решить ее и без применения алгоритма Евклида), но задача нахождения наибольшего общего делителя произвольных натуральных чисел т и и — уже проблема массовая.
Суть алгоритма Евклида состоит в том, что он приводит к желаемому результату вне зависимости от выбора конкретной пары натуральных чисел, в то время как при решении указанной единичной проблемы можно предложить такой способ, который окажется неприменимым для другой пары натуральных чисел. Непременным условием, которому удовлетворяет алгоритм, является его детерминированность, или определенность. Это означает, что предписания алгоритма с равным успехом могут быть 314 выполнены любым другим человеком и в любое другое время, причем результат получится тот же самый. Другими словами, предписания алгоритма настолько точны и отчетливы, что не допускают никаких двусмысленных толкований и никакого произвола со стороны исполнителя. Они единственным и вполне определенным путем всякий раз приводят к искомому результату.
Это наводит на мысль, что выполнение тех или иных алгоритмов может быть поручено машине, что широко и делается на практике. Говоря о начальных данных для алгоритма, имеют в виду так называемые допустимые начальные данные, т.е. такие начальные данные, которые сформулированы в терминах данного алгоритма. Так, к числу допустимых начальных данных для алгоритма варки манной каши никак не отнесешь элементы множества натуральных чисел, а к числу начальных данных алгоритма Евклида— молоко и манную крупу (или даже комплексные числа). Среди допустимых начальных данных для алгоритма могут быть такие, к которым он применим, т.е. отправляясь от которых можно получить искомый результат, а могут быть и такие, к которым данный алгоритм неприменим, т.е. отправляясь от которых искомого результата получить нельзя.
Неприменимость алгоритма к допустимым начальным данным может заключаться либо в том, что алгоритмический процесс никогда не оканчивается (в этом случае говорят, что он бесконечен), либо в том, что его выполнение во время одного из шагов наталкивается на препятствие, заходит в тупик (в этом случае говорят, что он безрезультатно обрывается).
Проиллюстрируем на примерах оба случая. Пример 31.1. Приведем пример бесконечного алгоритмического процесса. Всем известен алгоритм деления десятичных дробей. Числа 5,1 и 3 являются для него допустимыми начальными данными, применение к которым алгоритма деления приводит к искомому результату 1,7.
Иная картина возникает для чисел 20 и 3, которые также представляют собой допустимые начальные данные. Для них получается алгоритмический процесс: 20 (3 18 ! 6,66... 20 18 20 Этот процесс не встречает препятствий и никогда не оканчивается, так что получить искомый результат для начальных данных 20 и 3 оказывается невозможно. Отметим, что обрыв процесса произвольным образом не предусматривается данным алгоритмом. 315 11рамер 31.2. Теперь приведем пример алгоритма, заходящего в. тупик, безрезультатно обрывающегося. Вот его предписания. 1.
Исходное число умножить на 2. Перейти к выполнению п. 2, 2. К полученному числу прибавить 1. Перейти к выполнению и. 3 3. Определить остаток у от деления полученной в п. 2 суммы на 3, Перейти к выполнению п, 4, 4. Разделить исходное число на у. Частное является искомым результатом. Конец. Пусть натуральные (целые положительные) числа будут допу- стимыми начальными данными для этого алгоритма. Для числа 6 алгоритмический процесс будет проходить так: 1-й шаг: 6 .
2 = 12; переходим к п. 2; 2-й шаг: 12+ 1 = 13; переходим к и. 3; 3-й шаг: у = 1, переходим к п. 4; 4-й шаг: 6: ! = 6. Конец. Искомый результат равен 6. Иначе будет протекать алгоритми- ческий процесс для исходного данного 7: 1-й шаг: 7 . 2 = 14; переходим к и. 2; 2-й шаг: 14+ 1 = 15; переходим к п. 3; 3-й шаг: у = 0; переходим к и. 4; 4-й шаг: 7: 0 — деление невозможно. Процесс зашел в тупик, натолкнулся на препятствие и безрезультатно оборвался. Итак, подводя итоги обсуждению характерных свойств и особенностей алгоритма, можем сформулировать следуюшее интуитивно описательное определение этого понятия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
