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

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

• Определенность На каждом шаге алгоритма у исполнителя должно быть достаточно информации, чтобы его выполнить. Кроме того, исполнителю нужно четко знать, каким образом он выполняется. Шаги инструкции должны быть достаточно простыми, элементарными, а исполнитель должен однозначно понимать смысл каждого шага последовательности действий, составляющих алгоритм (при вычислении площади прямоугольника любому исполнителю нужно уметь умножать и трактовать знак «x» именно как умножение). Поэтому вопрос о выборе формы представления алгоритма очень важен. Фактически речь идет о том, на каком языке записан алгоритм.

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

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

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

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

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

На протяжении многих веков понятие алгоритма связывалось с числами и относительно простыми действиями над ними, да и сама математика была, по большей части, наукой о вычислениях, наукой прикладной. Чаще всего алгоритмы представлялись в виде математических формул. Порядок элементарных шагов алгоритма задавался расстановкой скобок, а сами шаги заключались в выполнении арифметических операций и операций отношения (проверки равенства, неравенства и т.д.). Часто вычисления были громоздкими, а вычисления вручную – трудоемкими, но суть самого вычислительного процесса оставалась очевидной. У математиков не возникала потребность в осознании и строгом определении понятия алгоритма, в его обобщении. Но с развитием математики появлялись новые объекты, которыми приходилось оперировать: векторы, графы, матрицы, множества и др. Как определить для них однозначность или как установить конечность алгоритма, какие шаги считать элементарными? В 1920-х задача точного определения понятия алгоритма стала одной из центральных проблем математики. В то время существовало две точки зрения на математические проблемы: "Все проблемы алгоритмически разрешимы, но для некоторых алгоритм еще не найден, поскольку еще не развиты соответствующие разделы математики" и "Есть проблемы, для которых алгоритм вообще не может существовать".

Идея о существовании алгоритмически неразрешимых проблем оказалась верной, но для того, чтобы ее обосновать, необходимо было дать точное определение алгоритма. Попытки выработать такое определение привели к возникновению теории алгоритмов, в которую вошли труды многих известных математиков – К.Гедель, К.Черч, С.Клини, А.Тьюринг, Э.Пост, А.Марков, А.Колмогоров и многие другие. Точное определение понятия алгоритма дало возможность доказать алгоритмическую неразрешимость многих математических проблем.

Приведем классические алгоритмически неразрешимые задачи:

• Десятая проблема Гильберта. Докакзано что не существует алгоритма, который по многочлену от нескольких переменных с целыми коэффициентами определял, есть ли у него целочисленные корни.
• Неразрешимость элементарной теории арифметики. Не существует алгоритма, который по утверждению о натуральных числах выдавал ответ на вопрос: истино оно или ложно?

Для алгоритмов существует два основных критерия: Правильность и Сложность(трудоемкость).

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

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

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

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

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

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

Очевидно, что время работы процедуры будет зависеть от начальных данных. Условимся, что псевдокод будет написан на языке Delthi. изобразим условно код программы:

Где отступ от левого края указывает уровень вложенности, т.е. в цикле "for" содержится цикл "while". Отметим каждую сторку стоимостью(чистом операций): пусть i-ая строка имеет стоимость _i

Далее, отметим сколько раз повторяется каждая сторка:

• 1 строка повторяется n раз;
• 2 строкa повторяются n-1 раз;
• 3 строкa повторяются n-1 раз;
• 4 строкa повторяются n-1 раз;
• 5 сторка повторяется t_j;
• 6 строка повторяется (t_j-1);
• 7 строка повторяется (t_j-1);
• 8 строкa повторяются n-1 раз;

Где n это размер последовательности, а t_j это колличество повторений строки 5.

Строка стоимости числом повторений m дает вклад m в общее число операций.

Сложив вклады всех строк получаем функцию временной сложности алгоритма:

T(n)=₁n + ₂(n-1) + ₃(n-1) + ₄(n-1) + ₅t_j + ₆(t_j-1) + ₇(t_j-1) + ₃(n-1);

время работы процедуры булет зависеть не только конкретного значения n, но и от того какая последовательность подана на вход, если же последовательность подана отсортированная, то 5 строка будет повторяться единственный раз, т.е. t_j=1 и функция времени будет линейной функцией, а если же на вход будет подана отсортированная последовательность в обратном порядке, то t_j=jи функция времени будет квадратичная.

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

Порядком роста алгоритма или его ассимтотической сложностью называется О-оценка функции временной или емкостной сложности в худшем случае(при самых плохих исходных данных). Говорят, что функция f(n)=O(q(n)) если =C, где С>0. Таким образом порядок роста нашего алгоритма сортировки есть O(n 2 ).

Алгоритм с меньшим порядком роста времени обычно предпочтителен, если, скажем, один алгоритм имеет время работы О(n 2 ), а другой О(n 3 ), то первый более эффективен.

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