Лекция 13 основные понятия теории алгоритмов

1. Определение алгоритма и понятие его исполнителя

22. Классы моделей алгоритмов

23. Формы записи алгоритмов

1 Определение алгоритма и понятие его исполнителя

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

Название «алгоритм» произошло от латинской формы имени среднеазиатского математика аль-Хорезми – Algorithmi.

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

Основные свойства алгоритмов следующие:

• Понятность– исполнитель алгоритма должен знать, как надо действовать для выполнения этого алгоритма.

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

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

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

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

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

Исполнитель алгоритма – это некоторая абстрактная или реальная (технически, биологически или биотехническая) система, способная выполнять действия, предписываемые алгоритмом.

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

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

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

Исполнителя характеризует:

• среда;

• система команд;

• элементарные действия;

• отказы.

Среда (или обстановка) – это «место обитания» исполнителя, которое характеризуется состоянием среды.

Каждый исполнитель может выполнять команды только из некоторого строго заданного списка – системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды.

После вызова команды исполнитель совершает соответствующие элементарные действия.

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

Наиболее распространенными и привычными являются алгоритмы работы с величинами – числовыми, символьными, логическими и т.д., а универсальным исполнителем алгоритмов является компьютер.