Понятие об алгоритме
С дискретной точки зрения произвольное преобразование информации – это отображение множества слов в некотором конечном алфавите в множестве слов в том же самом или любом другом конечном алфавите. Будем называть такие отображения алфавитнымиоператорами.
Каковы способы задания алфавитных операторов?
Алфавитные операторы, задаваемые с помощью конечных систем правил, называются алгоритмами.
Примеры: сложение двух чисел – алгоритм состоит из правила поразрядного сложения, правила сложения цифр (таблица сложения) и правила переноса.
Недостаток определения алгоритма – отсутствие математической точности.
В качестве способа точного задания произвольного алгоритма можно привести нормальныеалгоритмыА.А. Маркова, который преобразует слова, заданные в любом конечном алфавите в слова в том же самом алфавите, причем, обычно, алгоритм задает лишь частичное отображение.
Нормальный алгоритм задается конечной таблицейподстановок слов в данном алфавите.
Пример: существует алфавит ; таблица подстановок:
1. ;
2. ;
3. .
Пусть задано слово . Алгоритм преобразования:
1) ;
2) ;
3) ;
4) далее не применима ни одна формула.
Результат: .
Установлено, что любой алгоритм эквивалентен некоторому нормальному алгоритму.
Дата добавления: 2016-07-18; просмотров: 1882;