Элементы теории алгоритмов.

Здесь будет изложен подход к теории алгоритмов как к теории абстрактной вычислительной машины (абстрактной машины Тьюринга). Тьюринг (1912 - 54 г) – английский математик и инженер, один из создателей первой английской ЭВМ. Теория алгоритмов представляет собой теоретические основы прикладной математики, особенно ее компьютерной части, т.к. она дает ответы на вопросы: «Что значит вычислить?», «Всегда ли возможно решить задачу?», «Что значит задача?» и т. д.

Абстрактная машина Тьюринга может рассматриваться как простейшая и в тоже время всеохватывающая модель любой реальной ЭВМ.

Алгоритм – первичное, неопределяемое понятие. Вспомним, например, алгоритм нахождения наибольшего общего делителя двух натуральных чисел a и b.

1. Разложить a на простые множители.

2. Повторить п. 1 для b и перейти к п. 3.

3. Составить произведение общих простых множителей разложений a и b с показателями, равными наименьшим из показателей вхождения в разложения.

Общие понятия.

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

2. Пусть Х – множество исходных данных алгоритма А. Применим А к Х. При этом возможны три исхода.

а) Применение А к Х закончится в конечное число шагов, и А даст результат.

b) Применение А к Х закончится, но безрезультатно.

с) Применение А к Х вовсе не закончится, т.е. алгоритм будет работать бесконечно.

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

Понятие автомата.

Понятие алгоритма вводилось до сих пор чисто интуитивно. Понятие автомата позволяет уточнить понятие алгоритма. А это, в свою очередь, позволяет решить вопрос об алгоритмической разрешимости той или иной проблемы. В частности с помощью машины Тьюринга американским ученым Черчем (1903-1992) был получен результат при решении проблемы распознавания выводимости в математической логике: для любых заданных формул R и S в логическом исчислении определить существует ли дедуктивная цепочка, ведущая от R к S или нет.

Теорема Черча.

Проблема распознавания выводимости алгоритмически неразрешима.

Автоматы, изучаемые в последующих разделах, можно рассматривать как механизмы, состоящие из блока управления, который может пребывать в различных состояниях (внутренние состояния автомата), а также входного и выходного каналов. Входной канал воспринимает (считывает) сигналы из внешней среды, а выходной канал выдает сигналы во внешнюю среду. Природа состояний и сигналов безразлична, их можно рассматривать как некоторые символы (буквы), образующие соответственно алфавит состояний (или внутренний алфавит) – Q, входной алфавит – X, и выходной алфавит – Y. Каждая команда может быть записана в виде

(*)

где q_i , q_j – внутренние состояния автомата, x_r – входной символ, у_s – выходной символ.

Пусть на некотором такте t₀ блок управления установлен в состояние q_i, и входной канал воспринимает символ x_r. Если в программе имеется команда (*), то в этом же такте выходной канал выдает символ x_r, а к следующему такту t₀ + 1 блок управления перейдет в состояние q_j . Если такой команды нет, то автомат блокируется. В этом и заключается функционирование автомата. Множество внутренних состояний автомата является его внутренней памятью.

Таким образом, автомат – это пятерка (Q, X, Y, Ψ, Φ), где Q, X, Y – алфавиты, Ψ – функция переходов отображение Q X в Q, Φ – функция выходов (отображение Q X в Y). Пусть зафиксировано некоторое состояние автомата. Тогда рекуррентные соотношения

где q(t), q(t + 1) Q, x(t) X, y(t) Y, дополненные начальным условием q(1) = q₀, задают оператор T, который преобразует всякую конечную последовательность входящих символов

x = x(1) x(2) ...x(r) в некоторую последовательность выходных символов

y = Tx = y(1) y(2) .... y(r) .