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

Алгоритмы как формальные системы

Алгоритмы обладают двумя характерными особенностями:

- Наличие чёткого описания. Алгоритм всегда описывается настолько чётко, что на основе описания можно действовать механически не вникая в смысл.

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

По Хартли Роджерсу характеристика понятия «алгоритма» должна включать в себя следующие аспекты:

1. конечность,

2. наличие исполнителя,

3. результативность,

4. дискретность,

5. детерминированность.

Неформально и схематически алгоритм представляется в виде чёрного ящика. Алгоритм есть процедура (или способ вычисления), осуществляемая чёрным ящиком для получения выхода из входа.

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

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

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

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

Первый тип трактует алгоритм как некоторое детерминированное устройство, способное выполнять в каждый момент лишь строго фиксированное множество операций. Основной теоретической моделью такого типа является машина Тьюринга, предложенная им в 30-х годах и оказавшая существенное влияние на понимание логической природы разрабатываемых ЭВМ. Другой теоретической моделью данного типа является машина произвольного доступа (МПД) – введенная достаточно недавно (в 70-х годах) с целью моделирования реальных вычислительных машин и получения оценок сложности вычислений.

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

Третий тип алгоритмических моделей – это преобразования слов в произвольных алфавитах, в которых операциями являются замены кусков слов другим словом. Основной теоретической моделью этого типа являются нормальные алгоритмы Маркова.

Теория алгоритмов оказала существенное влияние на развитие ЭВМ и практику программирования. В теории алгоритмов были предугаданы основные концепции, заложенные в аппаратуру и языки программирования ЭВМ. Упоминаемые выше главные алгоритмические модели математически эквивалентны; но на практике они существенно различаются сложностными эффектами, возникающими при реализации алгоритмов, и породили разные направления в программировании. Так, микропрограммирование строится на идеях машин Тьюринга, структурное программирование заимствовало свои конструкции из теории рекурсивных функций, языки символьной обработки информации (РЕФАЛ, ПРОЛОГ) берут начало от нормальных алгоритмов Маркова и систем Поста.

Для того, чтобы построить строгое формальное определение алгоритма необходимо формально определить:

- объекты, над которыми выполняются действия, указанные в описании алгоритма;

- понятие действия;

- порядок выполнения действий.

Начнём с формализации понятия объекта.

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

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

Например, числа являются абстрактными объектами и доступны только в виде изображений. 256, 458 - это изображения натуральных чисел в десятичной системе счисления.

Алгоритм сложения двух чисел: последовательность символов "256 + 458" переводит в последовательность символов "714".

Алгоритм игры в шашки: последовательность символов "Белые: а1, с1, d4", "Чёрные: a7, b6, b8", ход может быть записан "a1-b2".

Таким образом, изображением можно считать последовательность символов (слов) в некотором алфавите.

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

Таким образом, объекты, к которым применяются алгоритмы, можно формально описывать как слова в некотором алфавите.

Пусть А – алфавит А= {а₁, а₂, …, а_n}, состоящий из букв а_i, i=1,n, тогда А^*= U А_i = А⁰ U А¹ U … U Аⁿ - множество слов над алфавитом А, где

А⁰ ={e} пустая цепочка

А¹ = А – цепочки, состоящие из одного элемента

А² = А*А – слова, состоящие из двух букв и т.д.

Если jÎА^*, то j называется цепочкой или словом над алфавитом А.

Пусть b - несобственная буква, т.е. bÏА. Тогда расширением алфавита А называется алфавит Ā =АU{b}.

Если ψÎĀ^*, то y называется несобственным словом над алфавитом Ā.

Например:

Алфавит {0, 1}

А^*={ε, 0, 1, 00, 01, 10, 11} – множество всех слов над алфавитом А.

Ā={ β, 0, 1}– расширение алфавита А.

Ā^*={ β, ε, 0, 1, β0, β1, 00, 01, ββ, …, β11}– множество всех символов над алфавитом Ā.

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

Алгоритм задаётся как предложение формального языка.

Алгоритмический язык – это формальный язык для однозначной записи алгоритмов.

Алгоритм считают правильным (correct), если на любом допустимом (для данной задачи) входе он заканчивает работу и выдаёт результат, удовлетворяющий требованиям задачи. В этом случае говорят, что алгоритм решает (solves) данную задачу. Неправильный алгоритм может (для некорректного входа) вовсе не остановиться или дать неправильный результат.

Вычислимая функция – функция f(x), для которой существует алгоритм оценки для любого элемента x в области определения f(x).

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

Описание эффективного процесса – это описание, содержащее следующие условия: допустимость заданного элемента для данного процесса, описание преобразования и его результата, условие достижения цели.

Эффективная процедура – алгоритм, удовлетворяющий следующим требованиям:

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

2. при задании на вход алгоритма набора значений x из области определения f(x) вычисления должны закончиться после конечного числа шагов и выдать соответствующее значение f(x), а если набор значений x не принадлежит области определения f(x), то вычисления не приводят ни к какому результату.

Дата добавления: 2015-06-27