книги из ГПНТБ / Алферова З.В. Теория алгоритмов учеб. пособие

3.В. АЛФЕРОВА

ТЕ О Р И Я

АЛ Г О Р И Т М О В

«СТАТИСТИКА» 1973 М о с к в а

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

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

' © ИЗДАТЕЛЬСТВО •СТАТИСТИКА* 1973

В В Е Д Е Н И Е

Понятие алгоритма является одним из основных понятий со­ временной математики. Еще на самых ранних ступенях развития математики (Древний Египет, Вавилон, Греция) в ней стали возни­ кать различные вычислительные процессы чисто механического ха­ рактера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике по­ лучили название алгоритмов (алгорифмов).

Термин алгоритм происходит от имени средневекового узбекско­ го математика Аль-Хорезми, который еще в IX в. (825 г.) дал пра­ вила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом.

С 1747 г. вместо слова алгоризм стали употреблять алгорисмус, смысл которого состоял в комбинировании четырех операций ариф­ метического исчисления — сложения, вычитания, умножения, деле­ ния.

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

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

Положение существенно изменилось, когда на первый план вы­ двинулись такие алгоритмические проблемы, положительное реше­ ние которых было сомнительным. Действительно, одно дело дока­ зать существование алгоритма, другое — доказать отсутствие алго­ ритма. Первое можно сделать путем фактического описания про-

3

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

В двадцатых годах нашего века задача такого определения по­ нятия алгоритма стала одной из центральных математических проб­ лем. Решение ее было получено в середине 30-х годов в работах из­ вестных математиков Гильберта, Гёделя, Черча, Клини, Поста и Тьюринга в двух формах. Первое решение было основано на поня­ тии особого класса арифметических функций, получивших назва­ ние рекурсивных функций, второе — на описании точно очерченно­ го класса процессов. Впоследствии в работах Маркова, Калужнина появилось другое толкование теории алгоритмов, поставившее в ос­ нову определение алгоритма как особого соответствия между сло­ вами в том или ином абстрактном алфавите.

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

Другая ее область возникла в 40-х годах в связи с созданием быстродействующих электронных вычислительных и управляющих машин. Появление ЭВМ способствовало развитию теории алгорит­ мов, вызвало к жизни разделы этой теории, имеющие ярко выра­ женную прикладную направленность. Это прежде всего алгоритми­ ческие системы и алгоритмические языки, являющиеся основой со­ временной теории программирования для универсальных ЭВМ, и способы точного описания отображений, реализуемых цифровыми автоматами.

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

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

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

4

Г л а в а 1

АЛГОРИТМИЧЕСКИЕ СИСТЕМЫ

1.1. Основные понятия теории алгоритмов

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

Первоначально для записи алгоритмов пользовались средствами обычного языка. И поэтому изучение теории алгоритмов целесооб­ разно начать со словесного представления алгоритмов.

Уточним понятие словесного алгоритма на примере умноже-

2.Полагаем I равным единице и переходим к следующему ука­ занию.

3.Полагаем с равным с-а* и переходим к следующему указа­

нию.

4.Проверяем, равно ли i числу п. Если i — п, то вычисления

словесный алгоритм данного примера, детально рассмотрим сам процесс поиска минимального числа. Будем считать, что процесс поиска осуществляется следующим образом. Первоначально в ка­ честве числа х принимается а\, т. е. полагаем х = ai, после чего х

равное наименьшему числу из массива (i — текущий номер числа из массива). Этот процесс может быть записан в виде следующей системы последовательных указаний:

6

если cii < х (иначе), переходим ко 2 указанию.

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

алгоритмы поиска минимального числа, поиска пути на графе, по­ иска пути в лабиринте и др.

Рассмотрим более сложный пример логического алгоритма — процесс поиска пути из вершины Хо в вершину хп для графа типа дерева.

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

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

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

7

где P°(xi) — число ребер с характеристикой Н = 0; Pi(xi) —число ребер с характеристикой Я = 1; Р2(хг) —число ребер с характеристикой Н = 2.

В исходном состоянии каждое ребро щ любой вершины х{ име^- ет характеристику Н = 0, степень каждой вершины х%

Алгоритмами в современной математике принято называть кон­ структивно задаваемые соответствия между словами в абстракт­ ных алфавитах.

Чтобы перейти к определению алгоритма, прежде всего следует определить понятия абстрактного алфавита и слов в этих алфави­ тах.

Абстрактным алфавитом называется любая конечная совокуп­ ность объектов, называемых буквами или символами данного ал­ фавита. При этом природа этих объектов нас совершенно не инте­ ресует. Символом абстрактных алфавитов можно считать, напри­ мер, буквы алфавита какого-либо языка, цифры, любые значки, ри­ сунки и даже слова некоторого конкретного языка. Важно лишь, чтобы рассматриваемый алфавит был конечным.

Можно сказать, что алфавит — конечное множество различи­ мых символов. Слово «абстрактный» для краткости будем опускать. Алфавит, как любое множество, задается перечислением его эле­ ментов, т. е. символов.

8

Примеры алфавитов: А = {а, |3, у, н } , В = {х, у}.

Под словом или строкой алфавита будем понимать любую ко­ нечную упорядоченную последовательность символов.

Так, например, в алфавите А словами следует считать любые последовательности a, ay, yfi, ^' - 'Р, РР и т. п., в алфавите В— х, у, ху, ух, хх, уу и т. п.

Число символов в слове называется длиной этого слова. Так, слова из алфавита А, приведенные в примере, имеют длину соот­ ветственно 1, 2, 2, 3, 2, . . .

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

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

При расширении алфавита, т. е. при включении в его состав но­ вых символов, понятие слова может претерпеть существенное из­

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

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

Иначе говоря, алфавитный оператор — функция, задающая со­ ответствие между словами входного алфавита и словами этого же или другого выходного алфавита.

Пусть нам заданы слова в алфавитах Л и В и заданы соответ­ ствия между этими словами (рис. 1).

Если а — слово в алфавите А, а р — слово в алфавите В, то ал­ фавитный оператор Га = р «перерабатывает» входное слово а в вы­ ходное слово р.

Буква Г в алфавитном операторе означает отображение. Различают однозначные и многозначные алфавитные операторы.

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

9