Теория алгоритмов возникла в математической логике как вспомогательная дисциплина, предназначенная для внутренних потребностей математики. Основными задачами, которые стояли перед ней, были: исследование феномена неразрешимости и обоснование математики. Практические применения теории алгоритмов первоначально основывались на интуитивном понятии алгоритма, поскольку математическое понятие алгоритма было разработано только для некоторых частных случаев, далеких от того, с чем приходится иметь дело на практике. Аналитическая теория алгоритмов, изучающая все их многообразие, возникла лишь в последнее десятилетие.
Интуитивное понятие алгоритма. Интуитивное понятие алгоритма рисует нам его как строго сформулированное правило, следуя которому можно осуществить процесс решения задачи, причем осуществить механически, максимально экономя усилия.
О п р е д е л е н и е. Алгоритм — это предписание, ведущее от исходных данных к искомому результату и обладающее свойствами: 1) определенности (общепонятности и точности); 2) массовости; 3) результативности.
Такое представление об алгоритме еще очень неясно, но его нетрудно уточнить. Такое уточнение нужно делать, во-первых, конкретизируя сказанное только что и, во-вторых, анализируя классические теории алгоритмов.
Алгоритм задается как предложение формального языка (это запись алгоритма) и определяет дискретный процесс преобразования исходного данного, запись которого является тоже предложением (другого) формального языка, в искомый результат (тоже предложение формального языка). Понятность алгоритма заключается в том, что для его выполнения должен быть задан другой алгоритм, называемый алгоритмом выполнения (или интерпретации), для которого исходным данным является совокупность записи алгоритма и записи операнда (объединяющая их символьная конструкция). От особенностей алгоритма выполнения зависит процесс, определяемый алгоритмом. Для некоторых вариантов исходных данных этот процесс содержит конечное число шагов (это — результативность алгоритма), но возможны и такие исходные данные, для которых алгоритмический процесс безрезультативно обрывается или никогда не заканчивается. В первом случае говорят, что алгоритм применим к исходному данному, а в двух последних — что неприменим.
Алгоритмический процесс состоит из шагов, каждый из которых представляет собой выполнение достаточно простых операций. Существует набор простейших операций, называемых натуральными, все же остальные операции — это отображения, индуцируемые алгоритмами. При определении нового класса алгоритмов достаточно простыми считаются операции, которые уже получены.
Такое понимание алгоритма неминуемо ведет к тому, что его определение принимают вид рекурсивного определения (новые алгоритмы строятся с помощью уже имеющихся). Процесс рекурсивного определения должен начинаться с определения каких-то алгоритмов, не опирающегося на понятие алгоритма, иначе все определение в целом являлось бы так называемым порочным кругом. В соответствии с вышесказанным широкое формальное определение алгоритма начинается с того, что вводится понятие первичных алгоритмов. Однако, поскольку понятие первичных алгоритмов связано с понятием операции, остановимся вначале на этом понятии.
Операции.
О п р е д е л е н и е. Операциями называются: 1) натуральные операции (см. ниже); 2) линеаризация и делинеаризация (см. ниже); 3) двухместная операция соединения слов (конкатенация); 4) всякое объявленное операцией отображение, осуществляемое алгоритмом.
Определим натуральные операции. Предварительно определим одну частную символьную конструкцию, которая нам при этом потребуется.
Введем в рассмотрение связь первого ранга и первого жанра, неодинаковую с начинающей связью следования, и назовем ее выделяющей связью.
О п р е д е л е н и е. Конструкция, которая получится, если в непустом слове одну из букв выделить с помощью выделяющей связи (т.е. связать ее этой связью), называется квазисловом. Началом квазислова называется его буква, связанная начинающей связью следования, а его концом — связанная заканчивающей связью следования.
В качестве натуральных операций выбраны операции, умение выполнять которые при построении теории алгоритмов обычно постулируют, считая, что каждый человек умеет выполнять эти операции. Некоторые натуральные операции являются в действительности классами операций, причем для выделения индивидуальной операции должна быть указана буква языка операндов, которую мы будем в описаниях обозначать метасимволом a (см. табл.3.1).
Натуральные операции делятся на натуральные действия и натуральные условия. В свою очередь, натуральные действия делятся на четыре группы. В группу I входят преобразования слов в слова; в группу II — преобразования слов в квазислова; в группу III — преобразования квазислов в квазислова; наконец, в группу IV — преобразования квазислов в слова. V группу натуральных операций образуют условия, выполнение которых не изменяет операнда, но ставит ему в соответствие логическое значение (истина, если условие выполнено, или ложь, если не выполнено). Прежде чем приступить к разъяснению операций линеаризации и делинеаризации, рассмотрим проблему получения всевозможных нумераций произвольной совокупности предметов, если известна какая-нибудь их нумерация.
Таблица 3.1.
Перечень натуральных операций
Номер группы Название операции | Описание | |
I | a — генерация | Преобразование пустого слова в однобуквенное слово состоящее из буквы a |
Аннигиляция | Преобразование однобуквенного слова в пустое слово | |
II | Нахождение начала слова | Преобразование непустого слова в квазислова путем выделения его начала |
III | Продвижение вперед | Перенос в квазислове выделяющей связи на одну букву правее |
Продвижение назад | Перенос в квазислове выделяющей связи на одну букву левее | |
Удлинение вперед (без продолжения) | Преобразование квазислова с выделенным концом путем присоединения буквы, одинаковой с выделенной | |
Отбрасывание конца | Преобразование квазислова в новое путем отбрасывания букв, следующих за выделенной, которая при этом становится выделенной | |
IV | Отключение | Квазислово преобразуется в непустое слово путем отбрасывания выделяющей связи |
V | Натуральные условия: Условие непустоты | Проверяется предикат «рассматриваемое слово непусто» |
Условие начала | Проверяется предикат «в рассматриваемом квазислове выделена первая буква» | |
Условие конца | Проверяется предикат «в рассматриваемом квазислове выделена последняя буква» | |
Условие тождества букв | Проверяется предикат «в рассматриваемом квазислове выделена буква, одинаковая с a» |
Итак, предположим, что некоторая конечная совокупность предметов перенумерована числами
1,2,…,n, n1.
Такая совокупность упорядочена. В ней всегда можно просмотреть все ее предметы, выбрав сперва 1-й, а затем, переходя от одного к другому, в порядке их номеров. Существует алгоритмический процесс получения всех возможных нумераций по заданной нумерации, а значит, и алгоритм в интуитивном смысле для выполнения этой операции. Он заключается в следующем.
1) Составим строку s из одного элемента 1; перейдем к п.2.
2) Параметру j присвоим (временно) значение 1; перейдем к п.3.
3) Если j=n, то перейдем к п.4, иначе — к п.6.
4) Припишем в конце каждой из имеющихся последовательностей s число j+1. Нами получены новые последовательности, обменивая в каждой из них элемент j+1 столько раз, сколько возможно, с предыдущим элементом, из каждой новой последовательности получим еще j новых последовательностей. Каждую из новых последовательностей будем называть именем s (старых последовательностей уже нет). Перейдем к п. 5.
5) Увеличим значение j на 1 и перейдем к п. 3.
6) Образуем пары из полученных последовательностей, в каждой из которых 1-v членом является последовательность 1,2,…,n. Всего таких пар будет v=n!-1. Считаем, что в каждой паре элементы (числа), одинаково расположенные в ее членах, взаимно-однозначно соответствуют друг другу. Таким образом, получено v целочисленных функций, каждая из которых позволяет преобразовать исходную нумерацию в некоторую новую. Перейдем к п. 7.
7) Последовательно применяя полученные функции к исходной нумерации, получаем из нее (и кроме нее) еще v новых нумераций. Процесс окончен.
Существенной чертой описанного процесса является то обстоятельство, что кроме описания его и исходной нумерации для получения всех возможных нумераций никаких дополнительных данных не нужно. Полученные нами функции мы строим тогда, когда они могут потребоваться. Иметь их в запасе не нужно. Это важно потому, что такой запас, пригодный на любой случай, был бы бесконечен, а процедура получения всех возможных нумераций не была бы эффективной. При n=1 заданная нумерация есть единственно возможная.
Линеаризацией называется операция, с помощью которой произвольная конструкция класса (А,В,Е) преобразуется в слово определенного специального вида в специальном расширении алфавита А. Прежде всего опишем нужное нам расширение алфавита А.
Возьмем произвольный алфавит букв С, не пересекающийся ни с А, ни с В, и имеющее число букв, равное определенному нами максимальному рангу связей, перечисленных в В. Наконец, возьмем алфавит D, не пересекающийся ни с А, ни с В, ни с С, число букв которого равно 3. Для определенности буквами в D будем считать символы (,) и 1, которые будем называть скобками и единицей (цифрой 1). В качестве расширения алфавита А возьмем А’=ВEАE СED. Слова, образованные из единиц, мы будем при выполнении нумераций применять как записи целых чисел в единичной системе счисления.
В дальнейшем, если некоторая буква предшествует в алфавите другой букве, будем говорить, что она младше этой второй буквы.
Ниже, при описании процесса линеаризации, мы будем произвольно нумеровать те или другие элементы конструкции, а затем учитывать все возможные результаты произвольной нумерации. Для этого будем репродуцировать обрабатываемую конструкцию n!-1 раз (где n — наибольший из произвольных номеров) и производить преобразование произвольных номеров (представленных как строки вида 1…1) способом, описанным выше. После каждого такого шага число обрабатываемых конструкций будет увеличиваться. Дальнейшие действия будут применяться к каждой из n! полученных конструкций в предположении, что каждая из них имеет то же имя, что и исходная.
Линеаризация состоит из следующих этапов.
Этап I. Преобразуемую конструкцию К заключают в оболочку.
Этап II. Находят в К для каждой буквы bi (i=1,2,…) алфавита В’ все связи, отвечающие этой букве. Производят их произвольную нумерацию и помечают словами 1,11, и т.д. Если произвольная нумерация привела к наибольшему номеру, который ³2, то определяют все возможные нумерации, увеличивая число экземпляров обрабатываемой конструкции и преобразуя вышеописанным способом номера. Считают, что каждая из полученных конструкций имеет имя К. Далее, переходя от связи к связи в каждой К, в порядке, который задают приписанные связям номера, упорядочивают ветви каждой связи аналогично тому, как это делалось для связей, с той лишь разницей, что вместо алфавита В используют алфавит С, считая, что ветвям i-ого жанра отвечает i-ая буква этого алфавита. Число конструкций снова возрастает (после каждой произвольной нумерации), а имя К закрепляется за каждой из полученных конструкций (это позволяет, говоря о К, иметь в виду каждую из них).
После окончания этого этапа все связи и ветви связей в некотором числе конструкций, каждая из которых называется К, помечены буквами и номерами.
Описанием каждой ветви любой связи называют слово, в начале которого стоит буква в В, затем несколько букв 1, затем — буква в С и, наконец, опять несколько единиц, Считают, что связи распались на отдельные ветви.
Этап III. В преобразуемой конструкции находят оболочку, внутри которой нет других оболочек. Пусть К’ — заключенная в ней конструкция. Выписывают все конструктивные элементы, из которых образована К’, в произвольном порядке, а перед каждым из них в лексикографическом порядке выписывают описания ветвей связей, для которых данный конструктивный элемент является связуемым объектом. Конструктивным элементом может быть (при повторных выполнениях этапа IV) либо буква в А, либо слово в А’, заключенное в скобки. Конструктивный элемент со всеми предшествующими ему описаниями ветвей назовем фрагментом. Каждый фрагмент является словом в А’. Все выписанные фрагменты в лексикографическом порядке объединим в одно слово и заключим в скобки. Полученным результатом в К заменим К’ вместе с содержащей ее оболочкой. Все ветви связей, которые прежде связывали оболочку, объемлющую К’, теперь отнесем к открывающей скобке. Заметим, что если К’ является пустой, то и слово, составленное из фрагментов, будет пустым.
Слово, которое будет получено после многократного выполнения данного этапа над каждой К и после отбрасывания содержащих его открывающей и закрывающей скобок, является одним из предварительных результатов, совокупность которых будет конечна.
Этап IV. Из всех предварительных результатов выбирают один, который лексикографически не старше остальных. Это и есть результат линеаризации.
Несмотря на ряд актов произвола, которые были произведены при линеаризации, ее результат однозначен, конечно, при заданных алфавитах В, С и D.
Делинеаризацией называется процесс восстановления конструкции по слову, имеющему соответствующую структуру, коротко говоря, — являющемуся ее описанием.
Для конструкции класса (А,В,Е) называются одинаковыми, если они при одинаковом А’ дают один и тот же результат линеаризации.