2. Формальное определение алгоритма

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

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

Конструктивные объекты – это слова, числа, предложения, которые описывают исходные данные, промежуточные результаты и конечные данные.

Алгоритмический процесс состоит из конечного числа шагов, каждый из которых является простым и выполняется за конечное время. Число шагов алгоритмического процесса связано с количеством времени S(t), затрачиваемого на их выполнение, а в ряде случаев и расходом других ресурсов.

Операнд – это объект, над которым выполняется операция.

5. Алгоритмический процесс.

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

Конструктивные объекты – это слова, числа, предложения, которые описывают исходные данные, промежуточные результаты и конечные данные.

Алгоритмический процесс состоит из конечного числа шагов, каждый из которых является простым и выполняется за конечное время. Число шагов алгоритмического процесса связано с количеством времени S(t), затрачиваемого на их выполнение, а в ряде случаев и расходом других ресурсов.

6. Основные вопросы теории алгоритмов.

Основные вопросы теории алгоритмов можно сформулировать следующим образом:

1. Что может делать ЭВМ.

2. Каким образом ЭВМ решает задачи.

3. Существует ли для заданной задачи эффективный алгоритм решения.

4. Как сравнить различные алгоритмы решения одной и той же задачи.

1) Было строго доказано существование таких типов задач, для которых невозможен единый эффективный метод решения, т. е. алгоритм, решающий все задачи данного класса (неразрешимые задачи).

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

4) Для сравнения различных алгоритмов по быстродействию необходимо рассмотреть следующие параметры:

• временная функция T(N);

• функция сложности алгоритма O(g(N)), учитывающая зависимость скорости роста числа шагов алгоритма от объема исходных данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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