Алгоритм и алгоритмические структуры

Интуитивное определение алгоритма

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

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

Существуют п другие интуитивные определения, например — сформулированные А. Н. Колмогоровым и А. А. Марковым.

Алгоритм (по А. Н. Колмогорову) — это всякая система вычислений, выполняемая по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

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

Интуитивное определение позволяет представить процесс решения задачи как преобразование некоторого набора исходных данных (входа) в некоторый результатный набор данных (выход), осуществляемое исполнителем алгоритма в соответствии с некоторыми инструкциями (рис. 1.1).

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

Рис. 1.1. Процесс решения задачи

менты), а выходом — число. Исполнителем алгоритма может выступать любой субъект, который способен воспринять и исполнить инструкции алгоритма, например человек, группа людей, компьютер, абстрактная машина.

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

• • правильность — при любых допустимых входных данных результат выполнения алгоритма должен удовлетворять требованиям задачи (результат должен быть правильным). Проверка этого свойства производится, например, серией тестовых данных с известными входными значениями и правильными выходными;
• • дискретность — алгоритм должен представлять собой последовательность отдельных операций (предписаний, действий, инструкций);
• • конечность — алгоритм должен записываться в виде конечного числа операций;
• • элементарность операций — каждое действие не должно допускать неоднозначного толкования;
• • определенность — после выполнения каждой операции однозначно известно, какое действие будет выполняться следующим;
• • результативность — после завершения выполнения алгоритма известен результат, который может быть интерпретирован и записан в терминах решения задачи. Результатом считается также и выявление того факта, что решение задачи невозможно;
• • однозначность — применение алгоритма к одним и тем же входным данным дает один и тот же результат.

Кроме указанных свойств, часто к алгоритму предъявляются требования, важные с практической точки зрения:

• • универсальность (массовость) — алгоритм должен решать не конкретную задачу, а целый класс схожих задач. Другими словами, алгоритм должен быть единым для различных данных из допустимого множества входных данных. Это требование не является обязательным, оно отражает, скорее, качество самого алгоритма;
• • разумное время исполнения. Если время исполнения алгоритма велико, то его практическая ценность мала. Например, многие алгоритмы, использующие полный перебор вариантов, даже при современной скорости обработки данных должны выполняться сотни миллиардов лет, что сводит на нет их практическое значение;
• • разумная ресурсоемкость. Технические характеристики (например, объем оперативной памяти, тактовая частота процессора) компьютерной техники должны быть достаточны для выполняемого алгоритма.

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