Алгоритм и примеры задач, решаемых с помощью алгоритмов

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

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

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

Вход: последовательность из N чисел ( ).

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

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

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

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

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

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

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