Интуитивное и формальное определение алгоритма.

Алгоритм – эффективная процедура, однозначно приводящая к результату.

Основные требования к алгоритму:

· Каждый алгоритм должен иметь данные: входные, выходные, промежуточные

· Данные для своего размещения требуют памяти внутренней и внешней

· Алгоритм состоит из отдельных элементарных шагов, количество которых конечно

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

· Результативность – остановка после конечного числа шагов, с указанием того, что считать результатом

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

Основные типы алгоритмических моделей:

1. Рекурсивные функции – вычисление и числовые функции

2. Машина Тьюринга – в основе лежит представление об алгоритме как некотором детерминированном устройстве, способном выполнить в каждый отдельный момент времени лишь примитивные операции

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

Пример: Машина Тьюринга

Машина Тьюринга состоит из 3-х частей:

1) Устройство управления, которое может находиться в одном из следующих состояний: Q = {q₁, q₂, …, q_n}.

2) Лента, которая разбита на ячейки, в каждой из которых может быть записан один из символов конечного алфавита A = {a₁, a₂, …, a_n}.

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

Среди состояний устройства управлений выделяют начальное – q₁ (оно существует перед началом работы) и выделяется заключительное состояние – q_z, после этого состояния машина Тьюринга останавливается.

Три способа описания:

1. Система команд

2. Таблица переходов: строки таблицы – состояния, столбцы – входные символы

3. Блок – схемы (диаграмма переходов)

Дата добавления: 2015-09-01