Знайте, Intuit, лекция, нормалните алгоритми на Марков

Анотация: Определяне на нормалната алгоритъм Марков и нейното прилагане. Възможности нормално Марков и Марков алгоритми теза. Методи за развитие на нормалните алгоритми Марков.

Определяне на нормалната алгоритъм и неговото прилагане

В средата на миналия век, виден български математик AA Марков представи концепцията за нормална алгоритъм (алгоритъм), за да се изясни понятието "алгоритъм", която ни позволява да се реши проблема за определяне на алгоритмично нерешими проблеми. По-късно тази концепция се нарича Марков нормално алгоритъм (САЩ). САЩ език. От една страна, умишлено лошо, е необходимо за целите на въвеждането на концепцията "алгоритъм". Въпреки това, от друга страна, ние имаме идеи като основа за по-голяма група от езици за програмиране, известни като езици за програмиране логика. които са предмет на настоящото ръководство.

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

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

В взела никакво не е празен низ от знаци, като алгоритъм за данни. Нашата работа се състои от серия от много подобни стъпки. Етап алгоритъм може да бъде описан, както следва:

1. В подредена последователност от замествания търсите за първи заместване, наляво една дума, която е част от редица от данни.
2. Линията на данни търси първите (ляво) за влизане намерени чрез заместване на ляво думи.
3. Този пост в низ от данни се заменя с подходящата дума намери заместване (преобразуване на данните).

Стъпка на алгоритъма се повтаря дотогава, докато

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

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

Така че, както е определено по-горе в примера на нормалния алгоритъм Марков превежда дума по дума, както следва (по-горе превръщането стрелка пишем номера се използва като смяна в низ подчертае ляво използва замяната на думата.)

и при конвертиране думи abbc същия алгоритъм ще продължи неопределено време, тъй като има цикличен повторение на данните:

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

Възможността за нормалните алгоритми и теза Марков

На първо място, да обмислят възможността за прилагане на аритметични операции с помощта на Марков нормалните алгоритми. На първо място, обърнете внимание на едно обстоятелство, свързани с работата на който и да е в САЩ. необходимо или да се въведе допълнително правило спиране на нормалния алгоритъм (в противен случай в пример 1, за да се увеличи броят на алгоритъма ще продължи да работи и ще се увеличи отново резултата до 1, и така неограничен брой пъти), или добавя към входния низ специална преди нормалната работа на алгоритъма знаци. различен от другите герои в низа, които се отчитат по пермутации на алгоритъма в началото на работата си, и които са премахнати в края на алгоритъма. Ние ще се придържа към втория метод, като един от най-успешните приложения на Марков нормалните алгоритми в език за програмиране рефал. Като вземем символа "@" като допълнителен характер.

Пример 1. Помислете за една проста операция за увеличаване на броя десетични от 1. В този случай това е почти винаги е необходимо да се увеличи последната цифра е 1, а последната цифра е различна с това, че става въпрос след символа "@". Затова първите замествания трябва да са тип заместване

Но ако това е номер 9, след което той трябва да бъде заменен от 0 и увеличение с 1 се връща на предишната цифра. Това съответства на заместването

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

и ако не, след това в края на символите @ да изтрие алгоритъм, който изпълнява заместването

По този начин, ние се следното САЩ за увеличаване на броя на десетичните 1:

Тук работа конструиран алгоритъм за номера 79 и 99:

По същия начин, разработен нормално Марков алгоритъм, за да се намали броят от 1 (вж. Упражнение 1.3.1).

Ние показваме на алгоритъма за броя 10:

За да се построи добавянето на две числа на алгоритъма може да използвате идеята за намаляване на броя по един, последвана от друга увеличение в броя от един и повтаря това, докато броят на умаляемо изчезва, след като става равен на 0. Но това е възможно да се използват по-сложни допълнение идея побитовото 1 с цифра за прехвърляне от ляво. Изграждането на тези алгоритми, както и изваждане алгоритми. умножение и деление разпределени за отделна операция в упражнения 2 - (. виж 1.3) 9.

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

Въпреки това, в последния строителство алгоритъм по-горе пример показва следното развитие техника на САЩ:

Решаване на проблеми с реализацията на всяка част. В този пример следните въпроси:

1. съхраняване на копие на изпълнението - ниво 1 се съхранява като символ "а", и изпълнението 0 - като символ "б";
2. пространство за съхранение копирани разряд - марката все още не е копиран символ допълнителен символ "!" с който го заменя с "?" когато се движат изхвърлянето на копие, и да се обърне, след като движението за подмяна.

Ако част от изпълнението е сложна, тя също подлежи на разлагане.

Монтаж на изпълнението на един алгоритъм.

упражнения

1. Определяне на нормалната алгоритъм. която намалява броя по един.
2. Определяне на нормална алгоритъм на добавяне на два двоични числа чрез намаляване на броя 1 и увеличението на другия номер 1, докато броят на Умаляемо става равно на 0.
3. Определяне на нормалната алгоритъм логично допълнение на две двоични числа.
4. Определяне на нормалната алгоритъм логично размножаването на две двоични числа.
5. Определяне на нормалната алгоритъм модул 2 на две двоични числа.
6. Определяне на нормалната алгоритъм е побитовото добавяне на две двоични числа.
7. Определяне на нормалната алгоритъм за изваждане на двоични числа.
8. Определяне на нормалната алгоритъм за умножение на две двоични числа колона.
9. Определяне на нормална алгоритъм за разделяне на две двоични числа с определението на частното и остатъка.
10. Определяне на нормалната алгоритъм за изчисляване на най-голям общ делител на две двоични числа.
11. Определяне на нормалната алгоритъм за изчисляване на най-малкото общо кратно на две двоични числа.