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


 

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

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

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

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

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

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

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

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

1. ;

2. ;

3. .

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

1) ;

2) ;

3) ;

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

Результат: .

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

 



Дата добавления: 2016-07-18; просмотров: 1882;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.006 сек.