Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

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

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

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

Думата е всяка крайна последователност от букви.

Броят на символите в дадена дума се нарича дължина.

Думата, чиято дължина е нула, се нарича празна.

Думата s се нарича подслова на думата q, ако q може да бъде представена под формата на q - rst, където rut са всякакви думи в една и съща азбука (включително празни).

Сега можете да дефинирате концепцията на алгоритъм (който не е строг):

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

В алгоритмите на Марков, заместването на една дума вместо друга се приема като елементарна стъпка на алгоритъма. Да предположим, че в азбуката А е конструирана началната дума Р, която съдържа подслова P r общия случай може да има няколко такива думи в изходната дума), а има и определена дума P k същата азбука.

Замяната е заместването на първата подредба по ред P r на оригиналната дума P с думата P k . Означава се със заместването R r → P k .

Алгоритъмът в тази форма на представяне се определя от пермутационна система, която е последователност (списък) на пермутациите. Ако има замествания в този списък с леви части, които са включени в P , тогава първият се прилага към P , в резултат на което преминава към друга дума P 1 . Към нея отново се прилага модел на заместване и т.н. Процесът се прекратява в два случая: или не е имало заместване в списъка с лявата част, включена в P n , или когато се получава Pn, последната замяна се прилага.

Вижте също:

Вероятността на който и да е от двата резултата от независими и несъвместими събития е равна на сумата на техните вероятности.

Начини за настройка на държавната машина

Пример 8.2

Унифицирано буквено двоично кодиране. Код за байт

Пример 5.2

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru