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

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

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

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

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

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

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

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

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

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

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

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

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

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