Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 4 стр.

      1.2. Основные требования к алгоритмам
    Каждый алгоритм имеет дело с данными - входными, промежуточными и выходными.
Данные как объекты, с которыми могут работать алгоритмы, должны быть четко определены
и отличимы как друг от друга, так и от другой информации.
    Данные для своего размещения требуют памяти. Память обычно считается однородной
и дискретной. Единицы измерения объема данных и памяти согласованы, при этом память
может быть бесконечной.
    Если выполнение алгоритма заканчивается получением результатов, то говорят, что он
применим к рассматриваемой совокупности исходных данных. Любой применимый
алгоритм имеет следующие основные свойства, раскрывающие его определение.
    1. Дискретность. Это свойство состоит в том, что алгоритм должен представлять
процесс решения задачи как последовательное выполнение простых (или ранее
определенных) шагов. При этом для выполнения каждого шага алгоритма требуется
некоторый конечный отрезок времени, то есть преобразование исходных данных в результат
осуществляется во времени дискретно.
    2. Определенность (или детерминированность). Это свойство состоит в том, что каждое
правило алгоритма должно быть четким и однозначным. Благодаря этому свойству
выполнение алгоритма носит механический характер и не требует никаких дополнительных
указаний или сведений о решаемой задаче.
    3. Результативность (или конечность). Это свойство состоит в том, что алгоритм
должен приводить к решению задачи за конечное число шагов.
    4. Массовость. Это свойство состоит в том, что алгоритм решения задачи
разрабатывается в общем виде и должен быть применим для некоторого класса задач,
различающихся лишь исходными данными.
    Для задания алгоритма необходимо выделить и описать следующие его элементы:
    • набор объектов, составляющих совокупность данных: исходных, промежуточных и
    конечных;
    • правило начала;
    • правила непосредственной переработки информации;
    • правило окончания;
    • правило извлечения результатов.
    Алгоритм всегда рассчитан на конкретного исполнителя. Если исполнителем является
компьютер, то алгоритм должен быть записан на языке программирования.


      1.3. Математическое определение алгоритма
       Интуитивное определение алгоритма не позволяет рассматривать свойства
алгоритмов как свойства формальных объектов. Поэтому математическое определение
алгоритма необходимо по следующим причинам:
    1) только при наличии формального определения алгоритма можно сделать вывод о
разрешимости или неразрешимости каких-либо проблем;
    2) это дает возможность для сравнения алгоритмов, предназначенных для решения
одинаковых задач;
    3) это дает возможность для сравнения различных проблем по сложности алгоритмов их
решения.
    Одна из причин расплывчатости интуитивного определения алгоритма состоит в том,
что объектом алгоритма может оказаться все, что угодно. Поэтому естественно было начать
с формализации понятия объекта. В вычислительных алгоритмах объектами работы
являются числа, в алгоритме шахматной игры - фигуры и позиции, при алгоритмизации
производственных процессов объектами служат, например, показания приборов. Однако
алгоритмы оперируют не с объектами реального мира, а с изображениями этих объектов.