Нормальный алгоритм - Большая Энциклопедия Нефти и Газа, статья, страница 2
Настоящая женщина должна спилить дерево, разрушить дом и вырастить дочь. Законы Мерфи (еще...)

Нормальный алгоритм

Cтраница 2


Понятие нормального алгоритма над алфавитом означает следующее. В ряде случаев не удается построить нормальный алгоритм, эквивалентный данному алгоритму в алфавите А, если ис-лользовать в подстановках алгоритма только буквы этого алфавита.  [16]

Запись нормального алгоритма можно превратить в слово, выписывая его формулы одну за другой и разделяя их буквами К. Теперь можно придумать некоторый прием кодирования, в результате которого полученное слово станет словом в А, конечно при условии, что алфавит А состоит не менее, чем из двух букв. Этот способ кодирования, например, может быть следующим.  [17]

Для нормальных алгоритмов Маркова А.  [18]

Записью нормального алгоритма в алфавите А называют столбец формул, левые и правые части которых являются словами в А. Выполнение нормального алгоритма применительно к исходному данному R, являющемуся словом в А, заключается в следующем.  [19]

Выполнение нормального алгоритма распадается на такты. Каждый такт включает в себя поиск первой по порядку применимой формулы подстановки и применение этой формулы. Первый такт начинается с проверки, является ли слово At частью входного слова. Иначе говоря, ищется вхождение слова Ai в исходное слово.  [20]

В нормальных алгоритмах в качестве элементарного оператора используется оператор подстановки, а в качестве элементарного распознавателя - распознаватель вхождения.  [21]

В нормальных алгоритмах используется только один тип элементарных операторов, называемых операторами подстановки, и один тип элементарных распознавателей, называемых распознавателями вхождения. Опишем эти распознаватели и операторы более подробно. Для этого познакомимся прежде всего с понятием вхождения одного слова в другое.  [22]

Внимательно рассматривая нормальные алгоритмы, мы видим, что они вполне соответствуют нашему пониманию алгоритма, но имеют очень частный характер. Большинство алгоритмов, встречающихся на практике, не являются нормальными алгоритмами. Но, безусловно, нормальные алгоритмы описаны с полной математической строгостью и точностью. Они вполне пригодны для тех целей, для которых были разработаны, а именно - для целей обоснования математики и исследования неразрешимости проблем.  [23]

Как определяются нормальные алгоритмы Маркова.  [24]

Необходимо построить нормальный алгоритм, который бы выполнял работу любого нормального алгоритма, если задана схема ( набор подстановок) этого последнего алгоритма.  [25]

Действительно, любой нормальный алгоритм А, в схеме которого нет ни одной заключительной подстановки, может окончить свою работу только тогда, когда ни одна из его подстановок далее неприменима.  [26]

Дайте определение нормального алгоритма Маркова.  [27]

Прежде чем применить нормальный алгоритм к начальной конфигурации в алфавите X, следует перед ней записать букву начального состояния. Так как на каждом шаге в конфигурации будет только одна буква из алфавита S, порядок подстановок в схеме алгоритма произвольный. На каждом шаге обработка слова нормальным алгоритмом совпадает с преобразованием машины Тьюринга.  [28]

Ассоциативные исчисления и нормальные алгоритмы Маркова.  [29]

Исходной информацией для нормального алгоритма служат слова - последовательности элементарных символов, называемых буквами некоторого алфавита. Алгоритм перерабатывает исходное слово в некоторое другое слово, которое является результатом действия алгоритма. В качестве элементарной операции преобразования слов принимается операция подстановки. Пусть дано некоторое слово X и слово А. Говорят, что слово А входит в слово X, если X представимо в виде X YAC. Для данных слов X и А такое представление может быть, конечно, неоднозначным. Вхождение слова А в слово X называется первым, если слово Y в представлении YAC X является наикратчайшим. Операция подстановки теперь определяется так: пусть дано слово X и подстановка Л - В.  [30]



Страницы:      1    2    3    4