Исходные понятия теории алгоритмов.

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

Примеры:

«Проезд запрещен», «Не курить» - не алгоритмы;

«Придерживайтесь правой стороны», «Место для курения», «Вход» - не алгоритмы;

Сложение (умножение, вычитание, деление) двух чисел (т.е. N²N) столбиком – алгоритм.

Пример:

Упорядочить в порядке возрастания конечное множество М положительных чисел. Описание решения этой задачи в интуитивном смысле может быть:

Шаг 1: В М ищется наименьшее число

Шаг 2: Найденное число приписывается справа к возрастающей последовательности чисел R (в начальный момент R пусто) и вычеркивается из М;

Шаг 3: Если в М не осталось чисел, то перейти к шагу 4, в противном случае перейти к шагу 1;

Шаг 4: Конец. Результатом считать последовательность R, построенную к данному моменту.

Это описание, которое кажется вполне ясным, далеко от алгоритма. Действительно, если М=⁹5, ⁶2, (1/3)^/2, то в предложенном варианте решения поставленной задачи не указано, как искать наименьшее число.

Этот пример показывает, что понятие алгоритма в интуитивном смысле требует уточнения понятия данных (т.е. указать каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать), памяти, дискретности, элементарности, конечности числа шагов, направленности, детерминированности, результативности, массовости.

Конструктивный объект – объект формальной системы F.S = <L, D> = <A, S, A_x, R>, где L – формальный язык, D – дедуктивные средства конструктивного процесса построения конструктивных объектов, A_x – аксиомы(исходные данные), A_x принадлежит L, R – отношения на множестве объектов(продукции, правила вывода, правила построения объектов) исходных объектов.

Пример:

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

Так, натуральные числа, рассматриваемые как слова в алфавите A={0, 1} начинающиеся с нуля и не содержащие других вхождений нуля, т.е. как слова 0, 01, 011, 0111…

Очевидно, что рациональные числа также являются конструктивными объектами в алфавите{0, 1, -, /}.

Пример:

Формальный язык – конструктивный объект, лексемы которого строятся из букв заданного алфавита с привлечением заданной формальной грамматики.

Замечание:

Формальная система F.S., обладающая свойствами элементарности и дискретности шагов построения конструктивных объектов, может служить формальной моделью алгоритма в интуитивном смысле.

Детерминированная формальная система F.S. является формальной моделью алгоритма в абстрактной теории алгоритмов.

Пример:

Машина Тьюринга <A, Q, >, как модель алгоритма, есть детерминированная формальная система, порождающая множество своих конфигураций (машинных слов – конструктивных объект, построенных из букв алфавита А ленты и алфавита Q внутренних состояний блока управления головкой):,

Здесь детерминированность означает, что к каждой конфигурации Машины только одной команды из программы .

Примечание:

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