Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

Светлой памяти

Эта книга, являющаяся введением в теорию алгоритмов, посвящена разъяснению одного из самых' основных поня­ тий математики — цонятия алгоритма; в ней рассматрива­ ется круг вопросов, лежащих на грани между математи­

Книга состоит из трех почти равных по объему частей. Первая часть, «Алгоритмы» (§ 1—6), еще не относится к тео­ рии алгоритмов, хотя в ней сплошь и рядом идет речь об ал­ горитмах. Дело в том, что здесь слово «алгоритм» понима­ ется в интуитивном смысле; теория же начинается лишь там, где термин обозначает уже точно определяемое мате­ матическое понятие. Тем не менее материал этой части, но­ сящий подготовительный характер, весьма важен и полезен для понимания содержательных стимулов в пользу теории.

Вторая часть, «Машины Тьюринга» (§ 7—13), вводит уже непосредственно в круг основных понятий теории ал­ горитмов.

Третья часть, «Алгоритмические проблемы» (§ 14—23), является кульминационной. В ней излагается ряд фунда­ ментальных результатов теории, которые, к счастью, под­

ее популяризации. Это случилось более 20 лет назад, когда автор выступил на эту тему перед своими коллегами — математиками Пензенского педагогического института. Та­ кие идеи и результаты теории алгоритмов, как формализа­ ция вычислительного процесса, существование неразре­ шимых алгоритмических проблем выглядели тогда не только непривычными, но и отпугивающими.

Написание популярной статьи или небольшой книги, в которой читатель кратчайшим путем мог бы дойти до теорем об алгоритмической неразрешимости, представлялось тогда автору неотложным делом.

3

В результате этого появилась статья «Алгоритмы и ма­ шинное решение задач» («Математика в школе», 1956, № 4— 5); ее расширенные варианты были изданы дважды (Гос-

Параграфы 1—9 и 13—16 настоящей книги целиком включают содержание упомянутых выше публикаций, ко­ торые подверглись тщательному просмотру и переработке.

Кроме того, книга содержит довольно обширный новый материал, а именно § 10—12 и § 17—24, в основу которых легли лекции, прочитанные автором студентам отделения математической лингвистики и слушателям факультета повышения квалификации Новосибирского университета. Этот материал представляет, как нам кажется, большой интерес для понимания таких разделов теории алгорит­ мов, которые уже не связаны непосредственно с явлением алгоритмической неразрешимости. Здесь имеются в виду главным образом следующие три проблемы: програм\щрсь-__ вание (§ 10—12), качество aлjroгJит^ю_в_($ 17—20)""й~автома-

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

этой книги.

Его моральная поддержка и постоянное внимание име­

ческой кибернетики. Автор рассматривает эту книгу как скромную дань памяти Алексея Андреевича.

Новосибирск, Академгородок, ноябрь, 1973 г.

Б. Трахтенброт

ВВЕДЕНИЕ

Понятие алгоритма • принадлежит к числу основных понятий математики. Под алгоритмом понимают точное предписание о выполнений в определенном порядке некото­ рой системы операций для решения всех задач некоторого данного типа.

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

Простейшими алгоритмами являются правила, по кото­ рым выполняется то или иное из четырех арифметических действий в десятичной системе счисления. Термин «алго­ ритм» происходит от имени средневекового узбекского ма­ тематика Аль-Хорезми, который еще в IX веке предложил такие правила. В математике серия задач определенного типа считается решенной, когда для ее решения установлен алгоритм. Например, в алгебре установлены алгоритмы, которые по заданным коэффициентам алгебраического урав­ нения позволяют совершенно автоматически определить, сколько различных корней (и какой кратности) имеет дан­ ное уравнение, и вычислить эти корни с любой наперед заданной точностью*'. Нахождение алгоритмов является естественной целью математики.

Однако не только в математике, но и в других разно­ образных областях человеческой деятельности встречаются процессы, протекающие по строго определенному формаль­ ному предписанию, т. е. алгоритму. Например, в бухгал­ терском и плановом деле анализ поступающих данных,

*) Необходимо различать решение конкретной задачи и решение серии задач. Например, конкретная задача может состоять в нахож­ дении корней-данного алгебраического уравнения. Ее решение — найденные значения корней. Серия задач формулируется чаще всего как проблема — например, найти метод, позволяющий по любому алгебраическому уравнению определить его корни. Поэтому решение серии задач — это единое предписание (метод, алгоритм), позволяю­ щее решить любую конкретную задачу данной серии задач, коль скоро известны конкретные значения пеоеменных параметров, фигурирующих в этой задаче.

5

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

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

Автоматические вычислительные машины получили большое развитие в последнее двадцатилетие и применяются для решения самых разнообразных задач. Характерная особенность этих машин, отличающая их от прежних вы­ числительных машин, заключается в том, что начиная с то­ го момента, как в них введены начальные данные (условия задачи) и программа (решающий алгоритм), они работают без всякого вмешательства человека вплоть до выдачи окон­ чательного результата. Производительность современных электронных автоматических машин огромна; они способны в одну секунду выполнять миллионы арифметических операций. Область их применения продолжает расти:

6

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

тические вычислительные машины представляют собой мощные орудия, способные не только облегчить труд чело­ века, но зачастую полностью освободить его от некоторых

ронных автоматических вычислительных машин и состав­ ления программ, т. е. алгоритмов, приспособленных для реализации в таких машинах.

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

леннее)*». Иначе говоря, возникновение вычислительных машин нового типа нельзя рассматривать как результат развития только инженерного изобретательства и элект­ ронной техники. Еще за несколько лет до появления первых действующих образцов вычислительных машин с автомати­

7