|
Теория алгоритмов — раздел математики, изучающий общие свойства алгоритмов. Понятие «алгоритм» сформировалось в математике в 20-х годах XX в. Началом систематической разработки теории алгоритмов можно считать 1936 г. и связывают это начало с публикацией работы А.А. Черча.
Под алгоритмом всегда (и до возникновения строгой теории) понималась процедура, которая позволяла путем выполнения последовательности элементарных шагов получать однозначный результат (независящий от того, кто именно выполнял эти шаги) или за конечное число шагов прийти к выводу о том, что решения не существует.
Конечно же это нестрогое определение понятия алгоритма и именно попытки сформулировать такое понятие привели к возникновению теории алгоритмов. Причиной развития этой теории были внутренние проблемы математики и лишь с возникновением и развитием вычислительной техники и смежных наук выяснилось, что в основе этих наук должна лежать теория алгоритмов. Так стало очевидным прикладное значение новой науки.
В основе формализации понятия «алгоритм» лежит идея построения алгоритмической модели. Составляющими такой модели должны быть конкретный набор элементарных шагов, способы определения следующего шага и т.д. От модели также требуется простота и универсальность. Требование простоты важно для того, чтобы выделить действительно необходимые элементы и свойства алгоритма и облегчить доказательства общих утверждений об свойствах. Универсальность необходима для того, чтобы моде позволяла описать любой алгоритм.
Результатами теоретических исследований явились три основных класса арифметических моделей.
Первый класс моделей основан на арифметизации алгоритмов. Предполагается, что любые данные можно закодировать числами, как следствие - всякое их преобразование становится в этом случае арифметическим вычислением, алгоритмом в таких моделях ее вычисление значения некоторой числовой функции, а его элемент» тарные шаги - арифметические операции. Последовательность шагов определяется двумя способами. Первый способ - суперпозиция, т.е. подстановка функции в функцию, а второй - рекурсия, т.е. определение значения функции через «ранее» вычисленные значения этой же функции. Функции, которые можно построить из целых чисел и арифметических операций с помощью суперпозиций рекурсивных определений, называются рекурсивными функциями. Простейшим примером рекурсивной функции является факториал.
Второй класс моделей порожден следующей идеей. Для тог чтобы алгоритм понимался однозначно, а его каждый шаг считался элементарным и выполнимым, он должен быть представлен чтобы его могла выполнять машина, к которой предъявляются уже упомянутые требования простоты и универсальности. Одной из машин явилась абстрактная машина Тьюринга. Машина Тьюринга состоит из трех частей ленты, головки и управляющего устройства (УУ). Лента бесконечна в обе стороны и разбита на ячейки. Элементарный шаг машины Тьюринга состоит из следующих действий:
головка считывает символ, записанный в ячейке, над которой она находится;
считанный символ и текущее состояние головки однозначно определяют новое состояние, новый записываемый символ и перемещение головки (которое может иметь значение на ячейку влево, на ячейку вправо, остаться на месте).
Устройство управления хранит и выполняет команды машины.
Третий класс моделей алгоритмов очень близок к предыдущему, но не оперирует конкретными машинными механизмами. Наиболее известная алгоритмическая модель этого типа - нормальные алгоритмы Маркова.
Для нормального алгоритма задается алфавит, над которым он работает, конечное множество допустимых подстановок и порядок их применения. Если в качестве алфавита взять алфавит русского языка, а в качестве множества подстановок то, используя правила 1—3:
1) проверить возможность подстановок в порядке возрастания их номеров, и если она возможна (левая часть подстановки обнаружена в исходном слове), произвести подстановку (заменив левую часть на правую);
2) если в примененной подстановке имеется символ «!», то преобразования прекращаются, а если нет, то текущее состояние становится исходным и весь процесс начинается заново;
3) если ни одна подстановка не применима, то процесс преобразования завершен, можно обнаружить, что по заданному алгоритму исходное слово.
В теории алгоритмов строго доказано, что по своим возможностям преобразования нормальные алгоритмы эквивалентные машине Тьюринга и другим моделям, уточняющим понятия алгоритма.
Появление точного понятия алгоритма позволило сформулировать алгоритмически не разрешимые проблемы, т.е. задачи, для; решения которых невозможно построить алгоритм. Задача называется алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции, или нормального алгоритме Маркова), которая ее решает. Например, неразрешимой оказалась проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который по любым двум алгоритмам (программам) выяснял бы, вычисляют они одну и ту же функцию или нет. Знание основных неразрешимостей теории алгоритмов необходимо для специалиста по информатике. Оно предостережет его от увлечения глобальными прожектами всеобщей алгоритмизации точно так как знание основных законов физики предостерегает от попыток создания вечного двигателя.
| 
