Основы алгоритмизации вычислительных процессов: основные понятия теории алгоритмов

Теория алгоритмов - это раздел математики, который изучает общие свойства алгоритмов.

Понятие «алгоритм» сформировалось в математике в 20-х гг. XX века. Началом систематической теории алгоритмов стала работа А. А. Черча 1936 г.

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

В основе понятия «алгоритм» лежит идея построения алгоритмической модели, которая должна состоять из набора конкретных элементарных шагов, способных определить следующие шаги.

Т. о. от модели требуется универсальность, чтобы эта модель позволила описать любой алгоритм.

Основой теоретических исследований послужили 3 основных арифметических модели:

1. Арифметизация алгоритмов

- любые данные можно закодировать числами, всякое их преобразование становится арифметическим вычислениям.

2. Абстрактная машина Тьюрена.

-каждый шаг элементарный, значит его должна выполнять машина.

3. Нормативные алгоритмы Маркова.

- каждый алгоритм задается своим алфавитом, над которым работает конечное множество допустимых подстановок и порядок их пременения.

Вывод: в теории алгоритмов строго доказано, что по своим возможностям преобразование нормального алгоритма эквивалентно машине Тьюринга. Это дало возможность сформировать понятие алгоритмически неразрешимой задачи.

Задача называется алгоритмически неразрешимой, если не существует абстрактной машины Тьюринга, нормального алгоритма Маркова, рекурсивной функции.

Определение алгоритма:

1. алгоритм- это конечная последовательность однозначных предписаний, использование которых позволяет с помощью конечного числа шагов получить решение задачи, однозначно определяемое исходными данными. (М. В. Семенов)

2. алгоритм- это система правил, которая сформирована на языке, понятном исполнителю, определяет процесс перехода от допустимых исходных данных к некоторому результату.

Алгоритмический процесс - процесс последовательного преобразования конструктивных объектов (слов, чисел, пар слов), происходящий дискретными шагами. Каждый шаг состоит в смене одного конструктивного объекта другим.