Понятие алгоритма. Существует два основных понятия алгоритма:

Существует два основных понятия алгоритма:

1 – интуитивное определение;

2 – формальное определение.

1. Алгоритм в интуитивном смысле – это точное предписание о

выполнении в определенном порядке некоторой последовательности

операций для решения всех задач некоторого заданного типа.

Содержание алгоритма, удобного для решения какой-либо задачи,

позволяет использовать его даже человеку-непрофессионалу. Кроме того, его

можно техническим устройством, выполняющим алгоритм автоматически

(ЭВМ по заданной программе).

Формализация понятия алгоритма не должна учитывать ограниченность

ресурсов, необходимых для его реализации, но требовать конечности этих

ресурсов, т. е. возможной реализации как таковой.

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

математических методов и основывается либо на других понятиях, имеющих

математическое определение, либо на понятиях-аксиомах, не требующих

доказательства.

На основе свойств алгоритма можно сформулировать формальное

определение. Алгоритм – это правило, сформулированное на некотором

языке и определяющее процесс преобразования исходных данных в искомые

результаты (алгоритмический процесс). При этом допустимые исходные

данные представлены как предложения на языке исходных данных.

Алгоритм характеризуется:

 понятностью для исполнителя;

 массовостью, то есть допустимостью для него всех предложений на

языке описания исходных данных;

 детерминированностью и другими свойствами.

Неточность интуитивного понятия заключается в неточности тех

терминов, через которые оно выражается, а именно:

 язык;

 понятность;

 точность

интуитивные понятия,

смысл которых ясен, а научные

определения не составлены.

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

Алгоритмический процесс – это процесс последовательного

преобразования конструктивных объектов, происходящий дискретно.

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

описывают исходные данные, промежуточные результаты и конечные

данные.

Алгоритмический процесс состоит из конечного числа шагов, каждый из

которых является простым и выполняется за конечное время. Число шагов

алгоритмического процесса связано с количеством времени S(t),

затрачиваемого на их выполнение, а в ряде случаев и расходом других

ресурсов.

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

Основные вопросы теории алгоритмов можно сформулировать

следующим образом:

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

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

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

решения.

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

1) Анализ вычислительных процессов, протекающих в соответствии с

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

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

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

класса (неразрешимые задачи).

Более того, ряд задач невозможно решить на современном уровне

развития ЭВМ (задачи искусственного интеллекта). Поэтому одной из главных

целей теории алгоритмов является исследование различных типов задач по

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

решения.

2) Ответ на второй вопрос требует рассмотрения принципов работы ЭВМ

и организации вычислительных процессов для различных структур ЭВМ в

рамках их классификации, а также оценки качества алгоритмов, реализуемых

в различных ЭВМ.

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

быстродействием.

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

рассмотреть следующие параметры:

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

 функция сложности алгоритма O(g(N)), учитывающая зависимость

скорости роста числа шагов алгоритма от объема исходных данных.