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

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

Каковы способы задания алфавитных операторов?

Алфавитные операторы, задаваемые с помощью конечных систем правил, называются алгоритмами.

Примеры: сложение двух чисел – алгоритм состоит из правила поразрядного сложения, правила сложения цифр (таблица сложения) и правила переноса.

Недостаток определения алгоритма – отсутствие математической точности.

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

Нормальный алгоритм задается конечной таблицейподстановок слов в данном алфавите.

Пример: существует алфавит ; таблица подстановок:

1. ;

2. ;

3. .

Пусть задано слово . Алгоритм преобразования:

1) ;

2) ;

3) ;

4) далее не применима ни одна формула.

Результат: .

Установлено, что любой алгоритм эквивалентен некоторому нормальному алгоритму.