Марков нормалните алгоритми - studopediya

За да се формализира понятието алгоритъм български математик AA Марков предложи използването асоциативен смятане.

Помислете за някои от концепциите за асоциативен смятане. Да предположим, че е налице азбука (ограничен набор от различни знака). Неговите съставни символи, които наричаме букви. Всеки краен последователност от букви от азбуката (линейна поредица от тях) е дума в азбуката.

Помислете двете думи пит в някои азбука А. Ако N е част от М, а след това ние казваме, че N е включена в М.

Ние дефинираме в някои крайни система азбука N пермутации - М, S - Т, където М, М, S, T - дума в азбуката. Всяко заместване на N-М може да се прилага за някои дума да се извърши по следния начин: ако К има един или повече случаи на N, тогава всяка от тях може да бъде заместен с F, и обратно, ако има наличие на М, той може да бъде заменен от Н.

Например, азбука А = са думи N = аб, М = BCB, К = abcbcbab, замествайки дума на дума N към М, или получаване bcbcbcbab abcbcbbcb, и обратно, замествайки М до N, или получаване aabcbab absabab.

Смяна аб - BCB неприемлива начин БАКБ, тъй като нито аб, нито Б. Б не са включени в думата. Чрез получен от споменатия допустим замествания отново могат да се прилагат допустимите замествания и т.н. Множеството от всички думи в азбуката заедно с допустимото замествания система, наречена асоциативен смятане. За да зададете асоциативен смятане, е достатъчно да се определи азбуката и система от замествания.

Думите Р1 и Р2 в някои асоциативен смятане се наричат ​​съседни, ако един от тях може да се трансформира в друга единична допустима заместване приложение.

Последователността на думи P, Р1. Р2. M се нарича дедуктивно верига, водеща от дума на дума Р М, ако всяка от двете съседни думите на веригата - в непосредствена близост.

Р и М думи се наричат ​​еквивалентни, ако има верига от Р до М и обратно.

A, B, C, D, E> Al - Са, ABAC - abace

ABCDE и acbde дума - Deluxe (ж.к. смяна - CB). ABCDE думи - cadbe еквивалент.

специален вид асоциативен смятане, където заместването е ориентирана може да се счита: N → М (стрелка означава, че заместването е позволено само от ляво на дясно). За всеки асоциативен смятане съществува проблем: за всеки две думи, за да се определи дали те са равностойни или не.

Всеки процес изходни формули, математически изчисления и трансформации са също дедуктивно верига в някои асоциативен основа. Изграждане на асоциативен камъни е универсален метод за детерминиран обработка на информацията, и ви позволява да се формализира понятието алгоритъм.

Ние се въведе понятието алгоритъм, базиран на асоциативен смятане: алгоритъма в азбука А е разбираемо точната рецепта, определящ процес на думите на А и позволява всяка дума като източник. Алгоритъмът в азбука А се дава под формата на допустимите замествания системи, допълнени от прецизно предписание на реда, в който ще трябва да използвате допустимите замествания и при настъпване на стоп.

Азбука: В системата на замествания:

Предписание за използването на замествания: P в произволна дума трябва да бъде възможно да се направи смяна, като замени лявата ръка на замествания в дясно; повторете процеса с току-що полученото думата.

Така че, с помощта на система от замествания в горния пример на bsasabs думите babaac и получавате:

babaac → → bbcaaac спирка

bcacabc → → bcacbcac bcacccac → → bsasabs безкраен процес (без спиране), така че ние имаме оригиналната дума.

AA Марков предложи начин за изясняване на концепцията на алгоритъм, базиран на концепцията за нормална алгоритъм, който се определя както следва. Като се има предвид азбука А, и системата на пермутации V. За всяка дума P в замяна на избрания в същия ред, в който те се появяват в подходящ заместване на Б. Ако не, процесът спира. В противен случай, първият е взето от съответните замествания и се заменят дясната му страна на първата поява на лявата му страна да P. След това, всички действия, които се повтарят, за да получите дума Р1. Ако се спира на последната замяна на системата, използвана в процеса.

Такъв набор от инструкции, заедно с азбука А и Б се определи набор от пермутации на нормалния алгоритъм. Процесът е прекъснат само в два случая: 1), когато не е намерен подходящ заместване; 2), когато последният се прилага заместването на техния комплект. Различни нормалните алгоритми се различават едни от други азбуки и пренаписват системи.

Ето един пример на нормалната алгоритъм, който описва естествени числа присъединителни (представители комплекта единици).

Азбука: В системата на замествания:

А = (а + 1) + 1 → + 1

Word F: 11 + 11 + 111

Последователна обработка на P използване на нормални Марков алгоритъм преминава през следните етапи:

Р = 11 + 11 + 111 + Р5 = 1 + 111 111

Р1 = 111 + 1 + 111 P6 = ++ 1111111

= Р2 + 1111 + 111 + P7 = 1111111

P3 = + 111 + 1111 = 1111111 P8

Р4 = 11 + 11 111 + R9 = 1111111

Нормално алгоритъм Марков може да се разглежда като универсална форма конфигурация всеки алгоритъм. Универсалността на нормалните алгоритми обявен принципа на нормализиране: за всеки алгоритъм в произволен краен азбука А, може да се изгради еквивалентно нормално алгоритъм над азбука А,

Обяснете последното изявление. В някои случаи, не може да се изгради нормална алгоритъм еквивалентна на тази в азбука А, ако се използва в алгоритъм замествания само букви от азбуката. Въпреки това, може да се изгради желаната нормално алгоритъм, производство удължаване на азбука А (като добавят към нея много нови букви). В този случай казваме, че конструираната алгоритъм е един алгоритъм над азбука А, въпреки че ще се прилага само за думи в оригиналната азбука А.

Ако алгоритъм N е разположен в продължение на азбука, а след това ние казваме, че N е нормална алгоритъм над азбука А.

Ние сме съгласни да се обадя конкретен алгоритъм normalizable ако някой може да се изгради еквивалентно нормално алгоритъм и nenormalizuemym друго. Принципът на нормализиране сега може да се изрази в променен вид: всички алгоритми нормализират.

| Този принцип не могат да бъдат строго доказано, тъй като идеята за произволен алгоритъм, който не е добре дефинирана и въз основа на факта, че всички известни досега алгоритми са нормализирани, както и начини rompozitsii алгоритми, което позволява да се изградят нови алгоритми от вече известни, не излиза извън границите на нормализирана клас алгоритми. По-долу са методи за формулиране нормални алгоритми.

I. Алгоритмите наслагване. При наслагване на две алгоритми А и В изходящ се счита като първи алгоритъм втората алгоритъм вход дума В. В резултат на наслагване С могат да бъдат представени като С (п) = В (А (п)),

II. Комбинирането на алгоритми. Асоциацията алгоритми А и Б в една и съща азбука, наречена алгоритъм C в една и съща азбука, стр превръща всяка дума, която се съдържа в пресечната точка на домейните на алгоритмите на А и Б в записания следващата дума (P) и B (P).

III. Разклонение алгоритми. Разклонение алгоритми е състав D три алгоритми А, В и С, където областта определяне алгоритъм D е пресечната точка на домените на трите алгоритми А, В и С, а = А (Р) за всяка дума стр в този пресичане D (п), ако C (п) = е, D (п) = В (р), ако С (п) = д, където д - празен низ.

IV. Итериране алгоритми. Итерация (повторение) е състав на два С алгоритми А и Б, че за всеки вход дума, съответстваща дума г (п), получен чрез последователно повторно приложение на алгоритъм за толкова дълго, докато дума трябва да се преобразува алгоритъм Б.

Марков нормалните алгоритми са не само средство за теоретични конструкции, но също така и чрез специализиран програмен език, използван като език на символични трансформации в развитието на системите с изкуствен интелект. Това е един от малкото езици, които се развиват в България и са придобили известност по цял свят.

Има сериозни доказателства, че способността да конвертирате нормални Марков алгоритми са еквивалентни на Тюринг машини.