Детерминированные и адаптивные алгоритмы

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

Рассмотрим особенности алгоритмов решения детерминированных и недетерминированных задач. Формализация детерминированных задач приводит к жестким моделям, а недетерминированных - к адаптивным.

Главной особенностью жестких моделей является их полная определенность. Поэтому алгоритмы решения детерминированных задач носят жесткий характер. Они допускают непосредственную программную реализацию на компьютере. Будем называть такие алгоритмы жесткими. Уточним смысл понятия "алгоритм".

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

Детерминированность означает, что правила, образующие алгоритм, должны быть строго определенными, однозначными и непротиворечивыми. Этим обеспечивается его независимость от исполнителя, будь то человек или компьютер.

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

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

Данная трактовка понятия "алгоритм" не претендует на математическую строгость. Однако она объясняет его содержательный смысл и интуитивно понятна каждому. Термин "алгоритм" роднит информатику и математику. Первоначально он зародился в математике. В эпоху средневековья алгоритмом называли правила выполнения арифметических действий над арабскими цифрами. Происхождение термина "алгоритм" связано с именем выдающегося математика древности Мухаммеда бен Мусы аль-Хорезми, который в IX в. предложил первые арифметические алгоритмы. В дальнейшем, по мере развития математики и информатики, это понятие многократно уточнялось и обобщалось.

Общая схема определения термина "алгоритм" была предложена советским математиком академиком А. Н. Колмогоровым. Она позволила, в частности, доказать эквивалентность ранее данных определении. В рамках этой схемы возможны различные уточнения и конструктивные определения понятия "алгоритм" с учетом особенности решаемых классов задач.

Одно из таких уточнений, играющих важную роль в компьютерной информатике, получило название машины Тьюринга. Схема такой машины, служащей для обработки информации, была предложена английским математиком А. Тьюрингом в конце 30-х гг. Она почти на 20 лет опередила фактическое появление компьютеров.

Что же представляет собой машина Тьюринга и каков алгоритм ее работы? Состоит она из трех систем: запоминающей, управляющей и исполнительной. Запоминающая система - это своеобразный склад информации. Ее можно представить как бесконечную ленту, на которой записывается закодированная информация, составленная из символов некоторого фиксированного алфавита. Часть ленты отводится для записи и хранения таблицы команд. Управляющая система считывает эти команды в том порядке, который предписывает заданный алгоритм обработки информации. Исполнительная система реализует выполнение как отдельных команд, так и алгоритма в целом. Работа машины Тьюринга сводится к изменению ее состояний в зависимости от того, каково состояние машины и какая информация подана на ее вход.

Один и тот же алгоритм может быть реализован различными способами. Каждому алгоритму можно поставить в соответствие его имитатор, который выполняет те же операции, что и данный алгоритм.

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

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

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

Однако для решения задач с неполной информацией зачастую нужны более гибкие алгоритмы. Их можно получить путем расширения понятия "алгоритм" за счет отказа от требования детерминированности. В этом случае алгоритмам можно придать адаптивный характер. Они обеспечивают решение задач за конечное время в заданном классе неопределенности. Будем называть такие алгоритмы адаптивными. Они отличаются большой гибкостью, способностью автоматически приспосабливаться (адаптироваться) к изменяющимся или не полностью определенным условиям задачи. В отличие от жестких алгоритмов они не обладают признаком детерминированности.