Основни понятия от теорията на алгоритмите - studopediya
Задавани алгоритми, наречени конструктивен кореспонденция между думите в абстрактни азбуки.
Резюме азбука - всяко крайно множество от обекти, наречени букви или символи на азбуката. Всяка азбука е даден списък на неговите символи: A =.
Думата или низ от азбука дефинира като всеки краен азбука на подредена последователност: аа, ABC, ABB.
Дължина на Word е броят на знаците на думата.
Празен дума - дума на нулева дължина.
Word P - под-дума дума дума Q ако Q може да бъде представен под формата: Q = PR. Азбучен оператор (картографиране) е кореспонденцията се комбинират думи азбука Дума с една и съща или различна азбука. В този случай, първата азбука, известна като входа и на изхода на втория оператор.
Азбучен оператор - функция определяне на отношението хектар = С.
Азбучен оператор се изчислява по формулата:
Фигура 1 - Създаване на азбучен оператора графично.
Разграничаване недвусмислени и мулти-ценен азбучни оператори.
Под ясно азбучен оператора отнася до оператор че всеки вход дума се подлага не повече от един изходящ (Фигура 2).
Използвани multivalued азбучен оператор разбира оператор, така че всеки вход дума е поставен под един или повече изходни думи (фиг.1).
Фигура 2 - уникален азбучен оператора.
Азбучен оператора не се свързани с определена дума азбука Гай не изходящ Bj включително празен, недефинирана при Гай дума.
Събирането на всички думи, която се определя азбучен оператор се нарича областта на дефиниция.
Картографиране всеки вход знак по знак азбука герой в изходна азбука думи, наречени кодиране картографиране.
Метод обратен кодиращ - декодиращ.
Декодиране оператор T -1 B = а.
aabacd → kkklkmlll
За обратимостта на кодиране трябва да бъдат изпълнени две условия:
1. Входни кодове различни герои азбука трябва да са различни;
2. Код на всеки вход азбука характер не трябва да съвпада с някой от началните думи под-други кодове знаци.
Кодиране на стоките, при което всички използвани кодове са със същата дължина, казва, че е нормално.
Най-често като входен кодирането на азбуката, като се използва бинарна система.
За да се определи дължината на кодовата дума се използва формула:
m - брой символи в изходната азбука;
L - дължина на кодовата дума,
п - броят на въведените символи с азбуката.
Азбучен оператори, дадени от краен система от правила, наречени алгоритми.
Две алгоритми се считат за равни, ако те са равни на съответните буквени операторите и съща система от правила, която определя действията на алгоритъма.
Две азбучен оператор се считат за равни, ако имат същия домейн и в сравнение с всички въвеждане на думи идентични резултати.
Двете твърдения са еквивалентни, ако те имат същите азбучни оператори, но не е същото като на правилата на системата.
Алгоритми, базирани на една цифра азбучен оператора наричат детерминирани.
Алгоритъм нарича масата, ако това е приложимо към множество входни думи.
Ако алгоритъмът предвижда резултат след краен брой стъпки, то се нарича ефективна.
Въз основа на въздействието на имота следва концепцията на домейна на алгоритъма.
Обхватът на прилагане на алгоритъма - множество входни редове, за които rezultativen алгоритъм. След това, два алгоритъма се смятат за еквивалентни, ако същия диапазон на приложимост и обработка на резултатите от всички думи от тази област.
Алгоритмите се наричат случайни, ако системата за правила дава възможност за случайна извадка от входните думи или разпоредби за преход.
Алгоритъмът се нарича самостоятелно модифициране, ако не само обработва входните думи, но и на промените в процеса.
Всеки начин да се определи алгоритми, наречени алгоритмична система.
Алгоритмичните системи се разделят на:
Алгебрични система е конструирана в определена символика в която алгоритмите представени под формата на линейни текстове:
Ø рекурсивни функции;
Ø Тюринг машина;
Ø оператор Wang Hao система;
Ø Еньовден логическа схема.
В геометрична система на алгоритми, построени под формата на комплекти, между които влязоха комуникация с картите на характера или бинарни отношения. Алгоритми са представени като графика схеми:
Ø държавни машини;
Ø Марков нормална алгоритъм;