Алгоритмом называется свод правил и действий, которые в совокупности позволяют решить поставленную задачу. Алгоритм характеризуется разной степенью формализации. Строго формальный алгоритм задает однозначные правила для вычислительных действий в каждой ситуации, которая может возникнуть на промежуточных стадиях вычислений.
В нашей жизни мы постоянно сталкиваемся с неформальными алгоритмами, даже не задумываясь об этом. Алгоритмами, например, являются правила поведения в обществе, должностные инструкции, инструкции к бытовой технике и т.д. Примером вычислительного алгоритма являются правила сложения, вычитания, умножения и деления десятичных чисел. Более сложные алгоритмы задают процесс вычисления корней квадратного уравнения или процесс решения системы линейных уравнений.
Слово «алгоритм» принято связывать с именем средневекового арабского ученого Аль-Хорезми (т.е. «из Хорезма»), который одним из первых рассматривал алгоритмы при решении алгебраических задач (как раз алгоритм сложения). Однако по-настоящему теория алгоритмов начала развиваться только в начале ХХ века. Прежде всего были сформулированы основные свойства алгоритмов.
Вход и выход.Чтобы решать задачу без участия человека, необходимо понятно для машины сформулировать условие задачи (вход) и суметь расшифровать результат вычисления (выход). Действие машины заключается в преобразовании входа в выход.
Дискретность. Процесс преобразования состоит из отдельных шагов, каждый шаг представляет собой элементарную операцию. Все возможные типы элементарных операций заданы заранее.
Привязка к языку. Каждый конкретный алгоритм формулируется в рамках некоторого языка и оформляется с использованием средств, определенных в этом языке. Эти средства нужны для того, чтобы описать вход и выход задачи и указывать операции алгоритма решения задачи. Например, таким языком может быть язык программирования.
Конечность. Алгоритм должен давать решение задачи за конечное число шагов.
Детерминированность. В каждый момент времени действия алгоритма выбор очередной операции зависит от результатов предыдущих вычислений и определяется ходом предыдущих вычислений однозначно.
Массовость. Практически полезный алгоритм не должен быть предназначен для решения одной единственной задачи, а должен быть применим к целому классу сходных задач. Конкретизация задачи задается входными параметрами. Например, параметрами алгоритма решения квадратного уравнения являются коэффициенты этого уравнения.
Повторяемость.Алгоритм должен давать один и тот же результат при одних и тех же входных значениях.
В теории формальных алгоритмов каждая операция определена строго формально, то есть полностью заданы состояния исполнителя до и после операции. Если отвлечься от деталей, алгоритм выглядит так: сделать одну операцию, затем другую, затем третью и т.д. Иногда приходится делать выбор: при выполнении некоторого условия сделать одно действие, а иначе другое. Альтернатив может быть больше, чем две.
Один из фундаментальных подходов к определению алгоритма, который имел наибольшее значение для практики, рассматривал алгоритм в единстве с исполнителем алгоритма (вычислительной машиной) и системой инструкций (операций), который исполнитель алгоритма умеет выполнять. То, над чем производятся действия исполнителя, в теории обычно является символами некоторого алфавита. На практике это двоичные разряды 0 и 1. В 30-х годах ХХ века было предложено несколько абстрактных моделей вычислительных машин (машина Поста, машина Тьюринга). Создатели компьютера реализовали идеи, заложенные в этих абстрактных моделях. Для этих машин была доказана универсальность – доказано, что с их помощью можно решить любую вычислительную задачу.
Компьютер как абстрактная вычислительная машина представляет собой комбинацию памяти – устройства для хранения данных, и процессора – устройства для проведения вычислений. Однако то же самое можно сказать об обыкновенном калькуляторе. Компьютер отличается от калькулятора наличием программы, которая может организовать процесс вычислений таким образом, что они будут реализовывать заданный алгоритм. Текущее состояние компьютера определяется совокупностью данных, хранящихся в памяти компьютера, и текущим положением программы, выполняемой компьютером. Различается входная, промежуточная и выходная информация. Входная информация помещается в память перед началом программы, выходная информация остается в памяти после конца программы. Программа представляет собой упорядоченную совокупность команд. Выполнение команды программы приводит к изменению содержимого памяти.
Параллельно с теорией делались попытки создать практически работающие вычислительные устройства. В 1642г. Паскаль изобрел устройство, выполняющее сложение чисел, а в 1673г. Лейбниц сконструировал арифмометр, позволяющий выполнять четыре арифметических действия. В первой половине XIX в. английский математик Чарльз Бэббидж попытался построить универсальную машину, которая должна была выполнять любые вычисления без участия человека. Программы для нее вводилась с помощью перфокарт, которые уже тогда употреблялись в ткацких станках. Реально такая машина (но не механическая, а электронная) была построена в США в 1943г.