Понятие алгоритма

Лекция 6.

ТЕОРИЯ АЛГОРИТМОВ

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

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

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

Существенными чертами неформального понятия алгоритма оказываются следующие:

1 - алгоритм задается как набор инструкций конечных размеров, т. е. его можно описать конечным набором слов и специальных символов;

2 - имеется вычислитель, обычно человек, который умеет обращаться с инструкциями и производить вычисления;

3 – алгоритм имеет некоторое число входных данных;

4 - имеется возможность для выделения, запоминания и повторения шагов вычисления;

5 - для каждого данного входа вычисление (преобразование входа) производится по данным инструкциям;

6 – с помощью алгоритма получается одно или несколько выходных данных.

Легко заметить аналогию с цифровыми вычислительными машинами.

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

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

Эти рассуждения выявляют некоторые свойства алгоритма, но не дают достаточно точного определения алгоритма.

Дата добавления: 2014-01-07