Информатика -продвинутый курс
НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА
Для формализации понятия алгоритма российский математик А.А.Марков предложил использовать ассоциативные исчисления.
Рассмотрим некоторые понятия ассоциативного исчисления. Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите.
Рассмотрим два слова N
и М в некотором алфавите А. Если N
является частью М, то говорят, что N входит в М.
Зададим в некотором алфавите конечную систему подстановок N - М, S - Т,..., где N, М, S, Т,... - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М,
и, наоборот, если имеется вхождение М,
то его можно заменить словом N.
Например, в алфавите А = {а, b, с} имеются слова N
= ab, М = bcb, К = abcbcbab, Заменив в слове К слово N
на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab
или аbсаbаb.
Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb
не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок.
Слова P1 и Р2 в некотором ассоциативном исчислении называются смежными, если одно из них может быть преобразовано в другое однократным применением допустимой подстановки.
Последовательность слов Р, P1, Р2, ..., М называется дедуктивной цепочкой, ведущей от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки - смежное.
Слова Р
и М называют эквивалентными, если существует цепочка от Р к М и обратно.
Пример
Алфавит Подстановки
{а, b, с, d, е} ас - сa, abac - abace
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий