Интуитивное понятие алгоритма, операции

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

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

О п р е д е л е н и е. Алгоритм — это предписание, ведущее от исходных данных к искомому результату и обладающее свойствами: 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.

Делинеаризацией называется процесс восстановления конструкции по слову, имеющему соответствующую структуру, коротко говоря, — являющемуся ее описанием.

Для конструкции класса (А,В,Е) называются одинаковыми, если они при одинаковом А’ дают один и тот же результат линеаризации.

Лекция 1: Понятие алгоритма. Классификация алгоритмических моделей


Похожие статьи.

Понравилась статья? Поделиться с друзьями: