1. Алгоритмы и вычисления

1.1. Что такое алгоритм?

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

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

Можно привести общие черты алгоритма:

• a. Дискретность информации. Каждый алгоритм имеет дело с данными: входной, промежуточными, выходными. Эти данные представляются в виде конечных слов некоторого алфавита.
• b. Дискретность работы алгоритма. Алгоритм выполняется по шагам и при этом на каждом шагу выполняется только одна операция.
• c. Детерминированность алгоритма. Система величин, получаемых в каждый (не начальный) момент времени, однозначно определяется системой величины, были получены в предыдущие моменты времени.
• d. Элементарность шагов алгоритма. Закон получения последующей системы величин с предыдущей должен быть простым и локальным.
• e. Выполнимость операций. В алгоритме не имеет быть не выполняемых операций. Например, нельзя в программе назначить значение переменной «бесконечность», такая операция была бы ни выполняемой. Каждая операция обрабатывает определенную участок в слове, которое обрабатывается.
• f. Конечность алгоритма. Описание алгоритма должен быть конечным.
• g. Направленность алгоритма. Если способ получения последующей величины с некоторой заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма.
• h. Массовость алгоритма. Начальная система величин может избираться с некоторой потенциально бесконечного множества. Рассмотрим для примера задачу сортировки последовательности чисел в возрастающем порядке. Эта задача часто возникает на практике и, фактически, будет центральной проблемой первого раздела данного курса. Задача сортировки определяется формально следующим образом.

Рассмотрим для примера задачу сортировки последовательности чисел в возрастающем порядке. Эта задача часто возникает на практике и, фактически, будет центральной проблемой первого раздела данного курса. Задача сортировки определяется формально следующим образом.

Вход: последовательность n чисел (a1,a2,...,an)

Выход: перестановка (aa1,aa2,...,aan) входной последовательности таким образом, что для всех ее членов выполняется соотношение aa1 ≤ aa2 ≤ ... ≤ aan

Например, если на вход подается последовательность (31, 41, 59, 26, 11, 58), то вывод алгоритма сортировки должен быть таким: (26, 31, 41, 41, 58, 59). Подобная исходная последовательность называется экземпляром задачи сортировки. Вообще, экземпляр задачи состоит из входа, который необходим для решения задачи и который удовлетворяет всем ограничением, которые присутствуют в постановке задачи.

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