13. Элементы тэорыі алгарытмаў

Алгоритм – строго определенная последовательность действий, описывающий процесс преобразования объекта из начального состояния в конечное, записывается с помощью понятных исполнительных команд; последовательность команд управления каким- либо исполнителем. Основные свойства алгоритмов:

• детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;

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

• массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;

• Связность. (не должно быть действий, приводящих к тупиковому результату)

• дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

• Формальность

• Конечность

• Эффективность

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

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

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

При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:

• линейный;

• ветвящийся;

• циклический.

Линейным называется такой вычислительный процесс, при котором все этапы решения задачи выполняются в естественном порядке следования записи этих этапов.

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

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

Алгоритмы состоят из определ команд, которые выполняются в определ последовательности. Весь процесс редактирования текста должен быть разбит на отдельн операции, записанные в виде отдельных команд использования.

Возможные операции в процессе редактирования текста: копирование, удаление, перемещение ли замена его фрагментов. Исполнитель (исп-ль) редактирования должен быть в состоянии выполнить все операции.

Система команд, запись алгоритма д/б такова,чтобы выполнить очередную команду, исп-ль точно знал – какую команду надо испольнить следующей. Д/б определены начальное состояние объекта и его конечное состояние.

Порядок выполения алгоритма:

• Действие в алгоритме выполняется в порядке их записи

• Нельзя менять действия местами

• Нельзя переходить к следующему действию, не окончив предыдущего.

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

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

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

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

Эта гипотеза называется тезисом Тьюринга. Её нельзя доказать, т.к. она связывает нестрогое определение понятия алгоритма со строгим определением понятия машины Тьюринга. Эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.

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

Формула подстановки служит для замены подслов в преобразуемом слове. Заменяемое и замещающееся подслова в формуле разделяются одной из стрелок → или • →. Продукция вида называется простой, а продукция – заключительной. В левой и правой частях формулы подстановки могут содержаться пустые слова. Для записи алгоритмов Маркова не требуется специального обозначения пустого слова, так как в этой конструкции носитель информации не зафиксирован, а преобразуемое слово свободно раздвигается и сдвигается. Заметим, что первое вхождение пустого слова находится слева от преобразуемого слова. Процесс выполнения алгоритма заканчивается в двух случаях: – либо все формулы оказались неприменимыми, – либо на последнем шаге была применена завершающая формула, в которой левое и правое подслова разделяет стрелка →.

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

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

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