Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 29)

Состояния различных объектов взаимозависимы так,что для каждого объекта о заданы множество Я, непосредственно влияющих объектов и функция влияния Р„(оь...,о,), опре. деляющая состояние х, объекта и по состояниям х„обьектов з,~О.:х„=Р.(оь ..., и,), (пь ..., о„) =Я, (в частности, для некоторых и множества Я„пусты, тогда х,=г"„ где ㄠ— заданное состояние). В данном случае объекты ое-=*г' можно рассматривать' как вершины структурного графа определенной ранее системы соотношений между состояниями этих объектов.

Это ориентированный граф с ребрами (о', и"), и'«=О.. Иногда рассматриваются неоднозначные функции р„(оь ..., о,) и ищутся системы допустимых состояний объектов, удовлетворяющие каким-либо дополнительным условиям, чаще всего некоторым условиям оптимальности. ГЛАВА ПЯТАЯ ТЕОРИЯ АЛГОРИТМОВ 5.1. ПРЕДБАРНТЕЛЪНОЕ ОБСУЖДЕНИЕ Несколько вступительных слов.

С алгоритмами, т. е. эффективными процедурами, однозначно приводящими к результату, математика имела дело всегда. Школьные методы умножения «столбиком» и деления «углом», метод исключения неизвестных при решении системы линейных уравнений, правило дифференцирования сложной функции, способ построения треугольника по трем заданным сторонам — все это алгоритмы. Однако пока математика имела дело в основном с числами и вычислениями и понятие алгоритма отождествлялось с понятием метода вычисления, потребности в изучении самого этого понятия не возннкало. Традиции организации вычислений складывались веками и стали составной частью общей научной культуры 144 в той же степени, что и элементарные навыки логического мышления.

Все многообразие вычислений комбинировалось из 1Π— !5 четко определенных операций арифметики, тригонометрии и анализа. Поэтому понятие метода вычисления считалось изначально ясным и не нуждалось в специальных исследованиях. До середины Х1Х в. единственной областью математики, работавшей с нечисловымн объектами, была геометрия, и как раз она, не имея возможности опираться на вычислительную интуицию человека, резко отличалась от остальной математики повышенными требованиями к строгости своих рассуждений.

До сих пор любой современный шестиклассник, для которого математика — это мир вычислений (и в этом он мало чем отличается от типичного инженера), мучительно привыкает к понятиям доказательства и математического построения и никак не может понять, зачем доказывать равенство отрезков, когда их проще измерить, и зачем строить перпендикуляр с помощью циркуля и линейки, когда есть угольник с «готовым» прямым углом или транспортир, Такое же мучительное привыкание к новым, более жестким требованиям строгости началось в математике во второй половине Х!Х в. Оно стимулировалось в основном математикой нечисловых объектов — открытием неэвклидовых геометрий, появлением абстрактных алгебраических теорий типа теории групп и т.д. Одним из решающих обстоятельств, приведших к пересмотру оснований математики, т.

е. принципов, лежащих в основе математических рассуждений, явилось создание Кантором теории множеств. Довольно быстро стало ясно, что понятия теории множеств в силу своей общности лежат в основе всего здания математики. Однако почти столь же быстро было показано, что некоторые кажущиеся вполне естественными рассуждения в рамках этой теории приводят к неразрешимым противоречиям — парадоксам теории множеств (которые упоминались в гл. 1; более подробно см. [36) ). Все это потребовало точного изучения принципов математических рассуждений (до сих пор казавшихся интуитивно ясными) математическими же средствами.

Возникла особая отрасль математики — основания математики, или метаматематики. Опыт парадоксов теории множеств научил математику крайне осторожно обращаться с бесконечностью и по возможности даже о бесконечности рассуждать с помощью финитных методов (см.$3.4). Существо финитного подхода 145 заключается в том, что он допускает только конечные комплексы действий над конечным числом объектов. Выяснение того, какие объекты и действия над ними следует считать точно определенными, какими свойствами и возможностями обладают комбинации элементарных действий, что можно и чего нельзя сделать с их помощью,— все это стало предметом теории алгоритмов и формальных систем,, которая первоначально возникла в рамках метаматематики и стала важнейшей ее частью.

Главным внутриматематическим приложением теории алгоритмов явились доказательства невозможности алгоритмического (т.е. точного и однозначного) решения некоторых математических про. блем. Такие доказательства (да и точные формулировки доказываемых утверждений) неосуществимы без точного понятия алгоритма. Пока техника использовала чисто вычислительные методы, эти высокие проблемы чистой математики ее мало интересовали. В технику термин «алгоритм» пришел вместе с кибернетикой.

Если понятие метода вычисления не нуждалось в пояснениях, то понятие процесса управления пришлось вырабатывать практически заново. Понадобилось осознавать, каким требованиям должна удовлетворять последовательность действий (или ее описание), чтобы считаться конструктивно заданной, т.е.

иметь право называться алгоритмом. В этом осознании огромную помощь инженерной интуиции оказала практика использования вычислительных машин, сделавшая понятие алгоритма ощутимой реальностью. С точки зрения современной практики алгоритм †э программа, а критерием алгоритмичности процесса является возможность его запрограммировать.

Именно благодаря этой реальности алгоритма, а также потому, что подход инженера к математическим методам всегда был конструктивным, понятие алгоритма в технике за короткий срок стало необычайно популярным (быть может, даже больше, чем в самой математике). Однако у всякой популярности есть свои издержки. В повседневной практике слово «алгоритм» употребляется слишко широко, теряя зачастую свой точный смысл. Приблизительные описания понятия «алгоритм» (вроде того, которое приведено в первой фразе этого параграфа) часто принимаются за точные определения.

В результате за алгоритм зачастую выдается любая инструкция, разбитая на шаги. Появляются такие дикие словосочетания, как «алгоритм изобретения» (а ведь наличие «алгоритма изобре- 146 тения» означало бы конец изобретательства как творческой деятельности). Ясное представление о том, что такое алгоритм, важно, конечно, не только для правильного словоупотребления. Оно нужно и при разработке конкретных алгоритмов, особенно когда имеется в виду их последующее программирование. Однако оно еще важнее при наведении порядка в бурно растущем алгоритмическом хозяйстве. Чтобы ориентироваться в море алгоритмов, захлестнувшем техническую кибернетику, необходимо уметь сравнивать различные алгоритмы решения одних и тех же задач, причем не только по качеству решения, но и по характеристикам самих алгоритмов (числу действий, расходу памяти и т.д.), Такое сравнение невозможно без введения точного языка для обсуждения всех этих вопросов; иначе говоря, сами алгоритмы должны стать такими же предметами точного исследования, как и те объекты, для работы с которыми они предназначены.

Строгое исследование основных понятий теории алгоритмов начнется в следующем параграфе. Прежде чем приступить к нему, обсудим на неформальном уровне некоторые основные принципы, по которым строятся алгоритмы, и выясним, что же именно в понятии алгоритма нуждается в уточнении. Основные требования к алгоритмам. !. Первое, что следует отметить в любом алгоритме,— это то, что он применяется к исходным данным н выдает результаты. В привычных технических терминах это означает, что алгоритм имеет входы и выходы.

Кроме того, в ходе работы алгоритма появляются промежуточные результаты, которые используются в дальнейшем. Таким образом, каждый алгоритм имеет дело с данн»сии — входными, промежуточными и выходными. Поскольку мы собираемся уточнять понятие алгоритма, нужно уточнить и понятие данных, т.е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать. Ясно, что эти объекты должны быть четко определены и отличимы как друг от друга, так н от «необъектов».

Во многих важных случаях хорошо понятно, что это значит: к таким алгоритмическим объектам относятся числа, векторы, матрицы смежностей графов, формулы. Изображения (например, рисунок графа) представляются менее естественными в качестве алгоритмических объектов. Если говорить о графе, то дело даже не в том, что в рисунке 1Ок 147 больше несущественных деталей и два человека один и тот же граф изобразят по-разному (в конце концов, разные матрицы смежности тоже могут задавать один и тот же граф с точностью до изоморфизма), а в том, что матрица смежности легко разбивается на элементы, причем из элементов всего двух видов (нулей и единиц) состоят матрицы любых графов, тогда как разбить на элементы рисунок гораздо труднее. Наконец, с такими объектами, как'«хорошая книга» или «осмысленное утверждение», с которыми легко управляется любой человек (но каждый по-своему(), алгоритм работать откажется, пока они не будут описаны как данные с помощью других, более подходящих объектов.

Характеристики

Список файлов книги