Формализация понятия алгоритма

 

Формализация понятия алгоритма

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

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

Рассмотрим взаимосвязь между функцией и алгоритмом. Сразу отметим, что основные свойства этой взаимосвязи мы будем здесь приводить без доказательства. Тому есть как минимум две причины. Первая - у читателя не предполагается знания необходимого математического аппарата; вторая - это увело бы нас в сторону от основной цели - формализации понятия алгоритма.

Определение 2.1. Говорят, что алгоритм А вычисляет функцию f(x), если:

Существует взаимно однозначное соответствие j между областью определения f(х) и областью применимости А;

Для любого х из области определения f верно: f(x)= А(j(x))

В этом случае функция f(x) называется вычислимой функцией.

Определение 2.2. Говорят, что Алгоритм А разрешает множество М относительно множества Х, где МÌХ, если:

Для любого х из множества М верно, что А(х) = “истина”;

Для любого у из Х, но у не принадлежит М, А(у) =“ложь”.

В этом случае говорят, что множество М разрешимое.

Примеры разрешающих алгоритмов - признаки делимости на 2, на 3, на 5. Эти алгоритмы разрешают множество натуральных чисел, кратных 2 (соответственно 3 либо 5), относительно всего множества натуральных чисел.

Определение 2.3. Говорят, что алгоритм А перечисляет множество В если область применимости А есть множество натуральных чисел N, а совокупность результатов есть множество В.

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

Изучение свойств вычислимой функции, а стало быть и алгоритма, показало, что:

Область применимости любого алгоритма - перечислимое множество; Следствие: алгоритмы не могут работать на множестве вещественных чисел.

Функция f(x) вычислима тогда и только тогда, когда перечислим ее график, т.е. множество {(x, f(x))} перечислимо.

Множество MÌX разрешимо относительно множества X, когда M и XM перечислимы.

Отсюда видно, что понятие алгоритма не сводимо к понятию функции. Множество функций мощнее множества алгоритмов.

Самое важное различие между этими понятиями для нас состоит в том, что алгоритм определяет некоторый процесс, который мы называем вычислительным. Понятие функции не предполагает и не определяет никакого процесса. Функция представляется в виде “черного ящика”, на вход которого подали аргументы и на выходе получили результат. Как этот результат был получен - умалчивается. Понятие алгоритма наоборот прежде всего сфокусировано на процессе вычисления результата. Алгоритм определяет именно то, как по аргументам вычислить результат. Итак, понятие функции, как оно есть в математике, нам не подходит, нужно строить формализацию, специально для алгоритма.

Всякое уточнение понятия алгоритма характеризуется следующими семью параметрами:

Совокупность возможных исходных данных (алфавит исходных данных).

Совокупность возможных результатов (алфавит результатов)

Совокупность возможных промежуточных результатов (алфавит  промежуточных результатов).

Множество действий.

Правило начала.

Правило окончания.

Правило определения расположения результата.

Здесь в качестве примеров уточнения понятия алгоритма мы рассмотрим Машину Тьюринга и Нормальные алгоритмы Маркова.

Машина Тьюринга.

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

В качестве исполнителя алгоритмов им был предложен автомат, состоящий из:

бесконечной ленты, разбитой на ячейки;

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

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

считать символ из ячейки, над которой она находится;

записать символ в ячейку, над которой она находится;

переместиться либо влево, либо вправо на следующую ячейку, либо остаться на месте.

изменять свое внутреннее состояние.

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

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

Совокупность возможных исходных данных - алфавит D;

Совокупность возможных результатов - алфавит D;

Совокупность возможных промежуточных результатов - алфавит D;

Множество действий:

множество правил вида ap®bqw, где a,bÎ D;  p,qÎ Q;  wÎ {Л, П, Н}.

D - алфавит символов, которые могут появляться на ленте;

Q - множество символов, обозначающих состояния каретки.

Л, П, Н - символы, обозначающие передвижение каретки налево, направо или наместе соответственно.

Смысл правила  ap®bqw  состоит в следующем. Если каретка находится над ячейкой, в которой записан символ а, и каретка находится в состоянии p, то каретка должна:

записать в эту ячейку символ b (символ а при этом стирается),

из состояния p перейти в состояние q,

переместиться на следующую ячейку влево если w=Л, - вправо если w=П или остаться на месте если w=Н.

Правило начала: каретка всегда размещается над последним, считая слева направо, символом слова на ленте и находится в специальном начальном состоянии qo;

Правило окончания: есть специальное состояние, мы его будем обозначать символом ! из алфавита Q. Как только каретка переходит в состояние ! , она останавливается.

Например, если правило имеет вид  ap®b!w , то после его выполнения вычисление считается законченным.

Правило расположения результата: справа от каретки до первого символа пустоты.

Дело в том, что пустота - это тоже символ, который мы будем обозначать символом L.

Пример 1. Построить Машину Тьюринга, вычисляющую функцию

U(n)=n+1  , где  nÎ {0,1,2,3,4,5,6,7.8.9}.

Машина Тьюринга с алфавитом D={0,1,2,3,4,5,6,7.8.9} и Q={qo, qs, !},

где qo  - начальное состояние, а  ! - конечное.

Нижеприведенная последовательность команд, реализует требуемую функцию.

№ команды


Формализация понятия алгоритма Для глубокого, строгого изучения свойств алгоритма и его организации необходима формализация, хотя бы для того, чтобы иметь в

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ