КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Нормални алгоритми Марков




Тюринг теза

(Основната хипотеза на теорията на алгоритмите)

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

Всяка функция, за които е налице изчисление

всеки алгоритъм условие изчислима от машина на Тюринг. Това доведе Тюринг предположение, наречено основната хипотеза на теорията на алгоритмите, и Тюринг теза:

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

Тази теза е аксиома. Тази теза не може да бъде доказано с помощта на математиката, защото тя не представлява вътрешна математически характер (от едната страна в тезата - понятието алгоритъм - не точна математическа концепция). Въпреки това, този аргумент може да бъде опровергана, ако функцията е установено, който е изчислима с помощта на някакъв алгоритъм, но не изчислима от машина на Тюринг.

Теорията на нормалните алгоритми е разработен от руски математик AA Марков в края на 1940 - началото на 1950. Двадесети век. Тези алгоритми са някои от правилата за обработка на думите във всяка азбука, така че входните и изходните думи са в някаква азбука.

Марков смяна. Азбука е всеки не-празен набор от знаци. Елементите на този набор се наричат ​​буквите и последователности от букви - думи в дадена азбука. Наличие на празни думи, т.е., думи, които не съдържат една буква. Празната дума се обозначава , ако и две азбуки, както и, азбуката Тя се нарича разширяване на азбуката ,

Думите са обозначени с латински букви: (Или от същите букви с индекси). Една дума може да бъде част от друга дума. След това, първата дума се нарича subword на втората дума или влизането в секунда. Например, ако - Руската азбука, тогава можем да считаме тези думи: = Параграф = Граф, = P. дума Това е фактор на думите и - Фактор и , И по- тя се появява два пъти. От особен интерес е първата поява.



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

път , Ако първата поява с една дума не (и, следователно, не съдържа никаква влизане в ), Тогава

Смята се, че замяната на Марков не се прилага за думата ,

Особени случаи на Марков замествания са заместване с празни думи: , , ,

Примери на Марков замествания

резултат
логика (Linda, ) влезте файл
(85 789, 00)
олелия (Ара, ) трамвай
ливада (Long Т) не е приложимо

За отбелязване на заместване Марков употребяван рекорд , Final смяна означен ,

Поръчано ограничен списък на заместване формули

в азбуката Той нарече схемата за нормална алгоритъм ,

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

последователността въпросната все още не е приключила. Ако алгоритъм е в нормалната схема са формули чиито лявата страни да бъдат включени след това Приема се, че и процеса на конструиране на последователност се счита за завършена. Ако веригата има формула с ляво страни на, входящи , Както резултатът е взето Марков заместване от дясната страна на първата от тези формули вместо на първата поява на лявата си страна с една дума ; Процесът на изграждане на последователност се счита за завършена, ако на този етап е била приложена крайната формула заместване, както и продължаващият - друго. Ако в процеса на изграждане на посочената последователност е отрязана, а след това

Той казва, че нормалната алгоритъм е приложим за думата ,

Последният план последователността се нарича резултат от нормалното прилагане на алгоритъма на думата , Тя се казва, че Нормалните процеси алгоритъм в ,

функция Определя се по някакъв набор от думи от азбуката , Обикновено се нарича изчислима, ако има разширение от азбуката ( ) И нормално алгоритъм Че всяка дума (В азбуката ) От областта на функцията този алгоритъм обработва думата ,

Помислете примерите на нормалните алгоритми.

Пример 1. Let - Азбука. Да разгледаме следния алгоритъм за нормалния режим :

Всяка дума в азбуката Съдържащ поне един

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

, , , , ,

2. Пример за дадена функция

където - Броят на единиците в думата 11 ... 1.

Нека разгледаме нормалната алгоритъм в чарта азбука ,

Докато броят на буквите в думата 1 е не по-малко от 3, последователно алгоритъм изтрива три букви. Ако броят е по-малко от 3 знака, но по-голяма от 0, останалите букви на 1 или 11 е окончателно изтрити; ако думата е празна, а след това е окончателно преведена дума 1. Например:

1111111 1111 1 ,

111111111 111111 111 1.

Пример 3 В азбуката Тя е продължение на азбуката Размислете нормалната алгоритъм, дефинират схеми (Прочетена от колони).

Ние прилагаме този алгоритъм за думата 3000.

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

,

Сега един от заместителите се задейства третата колона (в този случай - на първия) писмото на действително се променя буквата : , Накрая, една от предпоставките за първата колона пермутация. Ако го превръща думата завършва с номер, различен от 0, след което работи за един от най-крайните замествания, последната цифра е била заменена с цифрата, една по-малко, и алгоритъмът ще свършите работата си. В този случай, думата завършва с номер 0. Следователно, първата колона пермутация се задейства: , Тъй като и предпоследния цифра в преработения е равен на 0, алгоритъмът отново използва първия заместване, смяна и и подмяна 0 от 9. Това ще се случи, докато лявата писмото няма да разбера, различна от 0: , Сега, един от крайните произведения на замествания: ,

AA Марков излага хипотеза, наречена "Принцип на Марков нормализация". Съгласно този принцип, за да се приеме от стойностите, посочени в някои азбука, ако и само ако съществува някакъв алгоритъм, функцията нормално изчислима.

The формулиран принципът, както и резюмета на Тюринг и Църква, е vnematimatichesky и не може да бъде строго доказано. Той бе номиниран на базата на математически и практически опит.

Горните три теории (класа на всички частични изчислимите функции, класа на функции изчислимите от Тюринг, класа на изчислимите функционира нормално), изясняване на понятието за алгоритъма трябва да бъде еквивалентно на всеки друг. Това се потвърждава от следната теорема

Класът на следните функции (дефинирани по естествени числа и като положителни цели числа) са едни и същи:

а) категорията на всички частични рекурсивни функции;

б) класа на всички функции изчислимите по Тюринг;

в) класа на всички изчислимите функционира нормално.

Тази теорема е косвен потвърждение на адекватността на тези теории с компютъра, собствения капитал на всяка една от тезите на Тюринг, църковни и Марков. Ако един от тези класове се оказа по-широк, отколкото всеки друг клас, съответното тезата Тюринг, църква или Марков биха били опровергани. Например, ако класа на изчислимите функции обикновено се оказа по-широк от класа на рекурсивни функции, тогава щеше обикновено изчислимо, но не рекурсивна функция. По силата на своето нормално изчислимост би било алгоритмично изчислима в интуитивно разбиране на алгоритъм, и предположението, че ще опровергае тезата nonrecursiveness Църква. Но Тюринг класове, Църква и Марков са едни и същи, и такива функции не съществуват. Това е още един косвен потвърждение на тезата на Тюринг, църквата и Марков.

Контролни въпроси и упражнения

Задача 1