Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Нормальные алгорифмы А.А. Маркова



Читайте также:
  1. В которой пьют чай как ненормальные
  2. Виртуальные машины Тьюринга. Нормальные алгорифмы Маркова.
  3. Дарья Маркова (4)
  4. Как выйти из штопора? Ну, почему нормальные люди не понимают друг друга?
  5. Нормальные алгорифмы Маркова
  6. НОРМАЛЬНЫЕ ВЕЛИЧИНЫ ОСНОВНЫХ ЛАБОРАТОРНЫХ ПОКАЗАТЕЛЕЙ

А.А. Марков (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 | Нарушение авторских прав






mybiblioteka.su - 2015-2024 год. (0.006 сек.)