1.7 Классификация алгоритмов.

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

1. Табличные алгоритмы имеют в своей основе таблицу (поле исходных значений) и правила поиска решений.

2. Численные алгоритмы задаются в виде формул и блок-схем. В их основе значительную роль играют арифметические операции (+,–, /, *).

3. Алгоритмы игр имеют в основе логические задачи.

4. Комбинационные алгоритмы представляют собой совокупность алгоритмов других классов.

II. По способу создания (источники) различают:

1. Эмпирические алгоритмы – алгоритмы, полученные в ходе эксперимента или имитационного моделирования.

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

3. Эвристические алгоритмы – алгоритмы, основанные на личном опыте, таланте и изобретательности разработчика.

III. По критерию реализуемости различают:

1. Простые алгоритмы – хорошо обусловленные алгоритмы.

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

3. Нереализуемые алгоритмы.

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

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

Примеры:

«Уходя, гасите свет» - примитивный алгоритм.

«Не курить» - непрерывный процесс, не являющийся алгоритмом.

2. Массовость. Алгоритм должен решать не одну конкретную задачу (ограниченное множество неизменных исходных данных), а серию однотипных задач. Т. е. множество различных исходных данных порождает различные результаты.

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

Нужно считать, что для каждого алгоритма существует некоторый класс объектов, допустимых в качестве исходных данных.

Массовость алгоритма – это допустимость всех объектов соответствующего класса, а не допустимость какого-либо их количества.

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

4. Потенциальная осуществимость алгоритма. Говорят, что алгоритм применим к допустимому исходному данному, если с его помощью можно получить искомый результат. Иначе, хотя исходное данное и допустимо, но алгоритм к нему не применим.

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

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

Примеры:

1) Бесконечный цикл:

i=0

while i<= 10 do

k=k+1;

2) Последовательность вычислений:

1. b=2*a

2. b=b+1

3. c=b mod 3

4. d=a/c

a=6d=6

a=7алгоритм не применим.

Кроме потенциальной осуществимости алгоритма на практике требуется и реальная осуществимость.

5. Понятность. Алгоритм понятен для исполнителя, если он знает, как его выполнять (know how). Возникает вопрос: что именно должен знать исполнитель?

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

Пример:

Любая операционная система – это алгоритм алгоритмов.

6. Корректность. Если алгоритм создан для решения определенной задачи (заданного набора исходных данных), то для любого исходного данного из этого набора должно формироваться правильное решение.

7. Эффективность. Данное свойство определяет быстродействие и связано с понятием вычислительной сложности алгоритма.

Эмпирические алгоритмы, как правило, не являются эффективными. Теоретические алгоритмы являются корректными и эффективными, но могут быть реально неосуществимы.