|
Читайте также: |
А.А. Марков (1903-1979 гг.) – советский математик, занимавшийся математической логикой и конструктивной математикой разработал так называемые нормальные алгорифмы (это название используется только применительно к модели Маркова), основанные на полусистемах Туэ (ассоциативное исчисление, разработанное шведским математиком Акселем Туэ). Задаётся конечный алфавит A и конечное множество подстановок P. Работа алгоритма состоит из выполнения двух операторов: распознавателя и подстановки [36].
Оператор-распознаватель находит вхождение левой части подстановки в слово I, а оператор-подстановка заменяет это вхождение правой частью подстановки.
Совокупность всех слов в данном алфавите вместе с системой подстановок – ассоциативное исчисление.
Нормальный алгорифм останавливает процесс в случаях:
1. Подходящая подстановка не найдена.
2. Применена последняя подстановка.
Пример. А={0,1}.
Система подстановок Р:
где Ñ – обозначает последнюю подстановку.
Пусть I=0100011.
Тогда с учетом первого вхождения левой части второй подстановки (00→1) в слово I, получаем: 011011. Далее, применяя подстановку (110→1), получим 0111. Наконец, применив подстановку (111→0 Ñ), получаем результат 00. Конец работы алгоритма.
По существу, это универсальная форма задания любого алгоритма. Такая модель послужила основой обработки символьной информации. Это одна из немногих моделей разработанных в нашей стране и получивших признание в мире.
По существу это последовательные преобразования входных слов, составленных из символов конечного алфавита.
Различные формализации понятия алгоритмы, предложенные разными авторами, оказались в точности эквивалентными.
Дата добавления: 2015-07-11; просмотров: 100 | Нарушение авторских прав