Алгоритмы и исполнители. Свойства алгоритмов (дискретность, завершаемость, массовость и др.).

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

• Этимология слова алгоритм происходит от имени арабского математика Аль-Хорезми (точнее – латинизи-рованной формы его имени – Аlgorithmi), который еще в IX веке сформулировал правила выполнения четырех арифметических действий. Эти правила называли правилами Аль-Хорезми (algorithmi), а позднее просто стали называть алгоритмом.

• АЛГОРИТМ всегда связан с понятиями ИСПОЛНИТЕЛЯ и ДАННЫХ.

• Данные – исходные и промежуточные. Любые элементы какого-либо конечного множества (всё что представимо в цифровом виде). Сам Текст программы – это исходные данные для транслятора.

• Исполнитель – «обратная сторона» алгоритма. Субъект, который может воспринимать и выполнять определённый набор команд над определённым набором объектов. Система Исполнитель – Команды (действия) – Объекты (данные) – называют средой исполнителя.

• Конечный автомат – простейший исполнитель. Имеет конечное число различных внутренних состояний и переходов между ними (команд).

Свойства алгоритмов:

1. Дискретность – описываемый процесс должен быть разбит на последовательность отдельных простых шагов. Время выполнения каждого простого шага определенно и конечно во времени.

2. Элементарность – объём работы на каждом простом шаге ограничен сверху константой, которая зависит от исполнителя, но не зависит от входных данных.

3. Определенность – в каждый момент времени следующий шаг алгоритма однозначно следует из текущего состояния системы. Результат выполнения каждого шага (и алгоритма в целом) не зависит не от каких случайных факторов не предусмотренных алгоритмом.

4. Понятность – предписания алгоритма должны быть понятны конкретному исполнителю (соотносится с его системой команд).

5. Завершаемость – при конкретном наборе входных данных, алгоритм должен выдавать конкретный результат за конечное число шагов. Число шагов может зависеть от входных данных (не ограничено сверху).

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

ВОПРОС

Теория алгоритмов (задачи и примеры). Машина Тьюринга и машина Поста.

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

1. Определить (и доказать!) какие задачи являются алгоритмически разрешимыми, а какие таковыми не являются. Пример: алгоритм генерации простых чисел (без применения факторизации) – открытый и болезненный вопрос.

2. Асимптотический анализ алгоритмов – оценка того, как время выполнения алгоритма возрастает с увеличением объёма входных данных. Пример: сортировка методом пузырька VS сортировка Шелла.

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

Машина Тьюринга и машина Поста:

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

Тезис Чёрча-Тьюринга – математическая функция, которая описывает поведение любого физического устройства, может быть вычислена машиной Тьюринга.  

Физический смысл

1. Математический аппарат с конечным набором бесконечных лент (память неограничена), разделённых на ячейки

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

3. Головка для считывания записей (перемещается по управлением автомата).

Что дала модель Тьюринга?

1. Создала строгую математическую базу для исследования алгоритмов и исполнителей.

2. Указала направление развития вычислительной техники. Архитектура фон Неймана основана на машине Тьюринга.

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

4. Доказала, что любые алгоритмы (которые отвечают всем требованиям и облают всеми признаками), могут быть выполнены машиной Тьюринга.

5.  Машины, которые могут имитировать машину Тьюринга называют полными по Тьюрингу. Реальные машины не могут, поскольку имеют ограниченную память.

Машина Поста – альтернативная математическая модель. Создана в 1937 г. американским математиком Э. Постем. От машины Тьюринга отличается большей простотой (всего 6 команд).

Отличие от машины Тьюринга

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

в ячейку ленты машины Поста могут быть записаны только два значения – 0 и 1.

Утверждения (тезисы) Поста

1. Машины Тьюринга и Поста эквивалентны (доказано)

2. Машина Поста может выполнить любой алгоритм (не опровергнуто).

3. Машина Поста является простейшей абстрактной машиной полной по Тьюрингу (условно доказано).

ВОПРОС