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

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

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

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

1.5 Алгоритмы и языки.

Как уже отмечалось, алгоритм – это правило, а любое правило должно быть четко сформулировано на каком-либо языке (1). Это возможно лишь при условии, что исходные данные и искомые результаты могут быть описаны в полном объеме на каком-либо другом языке (2). Т. е. каждому исходному данному, промежуточному и конечному результатам соответствует некоторое предложение на этом языке. Смысл предложения должен быть однозначным.

Язык (1) – это язык описания алгоритмов.

Язык (2) – это язык описания данных (язык операндов).

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

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

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

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

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

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

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

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

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

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

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

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

3) Эффективным считается алгоритм, обладающий наибольшим быстродействием.

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

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

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