5. Дерево бінарного пошуку (binary search tree, bst):

ключ кожного вузла дерева має значення більше чи рівне значенню ключів його лівого під-дерева і менше або ж рівне – правого під-дерева. Рекурсивна реалізація пошуку для додавання вузла в дерево робить новий елемент зовнішнім вузлом («листочком» - бяднягою без посилань на діток); якщо значення ключа нового елемента відповідає якомусь ключу існуючого вузла, то новий вузол стає правим під-деревом цього вузла. BST – це вже відсортований набір даних.

Існує інший метод вставки, коли новий елемент стає коренем, тобто, всі останні вставленні вузли знаходяться поблизу вершини. Його реалізація:

а) якщо значення ключа нового вузла більше значення ключа кореня, то тоді старий корінь стає лівим під-деревом нового вузла, а праве під-дерево старого кореня – правим під-деревом нового;р

б) якщо значення ключа нового вузла менше значення ключа кореня, тоді старий корінь стає правим під-деревом нового вузла, а ліве під-дерево старого кореня – лівим під-деревом нового вузла.

в) ротація – перетворення дерева, основане на обміні кореня з його дочірнім вузлом із збереженням порядку слідування ключів у вузлах BST-дерева:

1. Ротація вправо – місцями міняються корінь та його лівий вузол = старий корінь стає правим під-деревом нового кореня + праве під-дерево нового кореня стає лівим під-деревом старого кореня;

2. Ротація вліво – місцями міняються корінь та його правий вузол = старий корінь стає лівим під-деревом нового кореня + ліве під-дерево нового кореня стає правим старого.

Одначе, пошук на BST-деревах працює з гарантованою продуктивністю лише за умови збалансованості дерева, тобто, коли всі зовнішні вузли знаходяться на одному рівні (висоті) або останньому чи передостанньому рівнях.

Методи його збалансування:

1. Рандомізація використовується під час побудови дерева в операції вставки нового вузла – його позиція обирається випадковим чином у процесі її пошуку: або в корінь дерева, або в корінь деякого під-дерева;

2. Амортизація використовується під час побудови дерева в операції вставки нового вузла – при переміщені доданого вузла у корінь виконується подвійна ротація, оскільки виконується оцінка двох зв’язків нового вузла з батьківським (дві ротації на одній ітерації);

3. Оптимізація полягає у використанні вузлів з декількома ключами і зв’язками: низхідні 2-3-4 дерева:

1. 2-вузол (один ключ і два посилання);

2. 3-вузол (два ключі і три посилання, тобто, ліве посилання на вузол із значенням ключа, меншим за поточний, праве – більшим за поточні, середнє – між значеннями поточного вузла);

3. 4-вузол (три ключі і чотири посилання, тобто, посилання визначають вузли за інтервалами ключів поточного вузла);

6. Порозрядний пошук:

Під час пошуку елементу значення ключа оцінюється порціями, а не повністю. Найпростіший порозрядний пошук оснований на використанні дерев цифрового пошуку (digital search trees, DST), яке є ефективним для дуже великих наборів даних з невеликими значеннями ключів, оскільки час пошуку обмежується лише довжиною ключа. Продуктивність можна істотно підвищити якщо одночасно розглядати більше одного розряду (основа системи числення не рівна двом). Наприклад, багато-шляхові дерева – значення ключів зберігаються у зовнішніх вузлах і кожен вузол має R-посилання (R - основа системи числення).

Якщо значенням ключа є рядок символів, тоді для порозрядного пошуку можна використовувати дерево тернарного пошуку (ternary search trees, TST) – дерево, кожен вузол якого містить один символ і три посилання (зв’язки), що відповідають ключам, поточні символи яких менші, рівні або більше символу вузла.

7. Зовнішній пошук.

Аналіз алгоритмів

- спосіб передбачення потрібних ресурсів для виконання алгоритму (оцінка його ефективності), де ресурси - час виконання і об’єм пам’яті. Застосовується аналіз алгоритмів як на етапі їх розробки, так і на етапі реалізації. Методи, що розглядаються, застосовуються до різних алгоритмів, що розв’язують одну і ту саму задачу.

1. Емпіричний (експериментальний) – обчислення часу виконання шляхом запуску на виконання реалізації алгоритмів. Допущення:

1 категорія - реалізація

1. алгоритми реалізовані на тій же самій мові програмування;

2. реалізація алгоритмів виконується з однаковою ретельністю;

3. виконуваний код (програма) алгоритмів має бути отриманий з використанням одного і того ж середовища програмування;

4. виконання алгоритмів виконується на одній і тій самій машині.

2 категорія – вхідні дані

1. використання реальних даних (точне вимірювання часу виконання);

2. використання випадкових даних (гарантія аналізу самого алгоритму, вимірювання середнього часу виконання);

3. використання незвичайних даних (вимірювання найгіршого випадку).

Приклад емпіричного аналізу алгоритмів послідовного і бінарного пошуків:

• пошук виконується в масиві цілих значень (невпорядкована структура);

• розмірність масиву у діапазоні від до

• кількість операцій пошуку елемента у діапазоні від до ;

• набір даних і пошук елементів один і той самий;

• масив ініціалізується випадковими значеннями.

а) Невдалий послідовний пошук – у найгіршому і середньому випадках треба перевіряти усі N елементів; успішний - в середньому перевіряється N/2 елементів.

Послідовний пошук у впорядкованому масиві:

невдалий – N/2 елементів у середньому і N елементів у найгіршому випадку; вдалий пошук – N/2 елементів у середньому (час виконання пропорційний кількості елементів).

б) При використанні бінарного пошуку перевіряється не більше елементів: N = 100 -> 50 -> 25 -> 12 -> 6 -> 3 -> 1.

N	M=1000
	Послідовний	Бінарний
250	63	13
500	119	14
2500	570	16
12500	3073	17

2. Математичний (аналітичний) – обчислення відносного часу виконання шляхом побудови математичного виразу. Застосовується якщо:

1. відсутня реалізація алгоритму;

2. необхідно передбачити час виконання алгоритму у новому середовищі;

3. порівнюються різні алгоритми, що мають використовуватися для вирішення одної задачі. Під час виконання аналітичного аналізу важливо пам’ятати, що алгоритми мають параметри, які впливають на час їх виконання (типи абстрактних операцій). Необхідно виділити один головний, який частіше всього пропорційний величині набору даних, що опрацьовується, тобто розмірності набору даних.

Залежність часу виконання можна виразити через головний параметр з використанням простих математичних формул, що називаються ріст функціями:

1. 1- постійний час виконання (майже всі операції виконуються один раз або декілька); наприклад – пошук індексуванням за ключем;

2. N- лінійний час виконання (якщо кожний елемент обробляється); наприклад – послідовний пошук;

3. logN- логарифмічний час виконання (задача розбивається на набір під-задач, із зменшенням розміру задачі на кожному кроці на деякий постійний коефіцієнт, і розв’язок визначається в одній із під-задач); наприклад – бінарний пошук.

4. NlogN- час виконання пропорційний NlogN (задача розбивається на під-задачі, розв’язки яких потім об’єднуються); наприклад, низхідне сортування злиттям;

5. - квадратичний час виконання (коли опрацьовуються усі пари елементів – подвійні цикли); наприклад, сортування алгоритмом вставки у найгіршому випадку;

6. - кубічний час виконання (потрійні цикли); наприклад, сортування двовимірного масиву за значеннями одного рядка алгоритмом бульбашки;

7. - експоненціальний час виконання (прямий розв’язок задачі); наприклад, розклад числа на прості множники (ряди).

Для побудови аналітичного виразу, яким обчислюється час виконання, треба визначити всі операції, їх кількість та час виконання, і отриманий вираз можна перетворити, виразивши його через ріст функції. Для приблизної оцінки часу виконання алгоритму при більших значеннях N можна спростити математичний вираз, відкинувши додатки «нижчих порядків». Оцінка порядку росту часу виконання алгоритму при великих об’ємах набору даних називається асимптотичною ефективністю. Її математичний запис називається «тета-нотацією» T(n)= (g(n)), де (g(n)) - множина функцій, для яких справедливе висловлювання:

f(n) is (g(n)), якщо існують константи c(1) c(2) і n(0), такі що 0<=c(1)g(n)<=f(n)<=c(2)g(n) для всіх n>=n(0).

Визначення асимптотичної верхньої межі – О-нотація;

f(n) is O(g(n)), якщо існують c і n(0), такі що 0<=f(n)<=cg(n) для всіх n>=n(0).

Нижньої межі – омега-нотація:

-||- 0<=cg(n)<=f(n) -||-.

Через О-нотацію описується найгірший випадок – наприклад, сортування за зростанням алгоритмом вставки масиву, який уже відсортовано за спаданням. Через омегу описується найкращий випадок – наприклад, масив даних уже впорядковано. Приклад розрахунку асимптотичної оцінки для алгоритму сортування вставкою: N=m.length; c1 -> N; c2 -> N-1; c3; c4 -> sum(j=1 to N-1)k(j); c5 -> .. k(j)-1; c6; c7 -> N-1. T(N)=уся оця байда додається))

1. найкращий випадок (масив відсортовано у потрібному порядку):

c1N; c2…c4, c7 … all*(N-1) = (c1…)N + (c2..c7)=aN+b;

2. найгірший випадок (масив відсортовано у оберненому порядку):

sum(j=1 to N-1)k(j)= sum(j=1 to N-1)j=(N*(N+1)/2)-1; ….

Математичні алгоритми

• це алгоритм, що використовується для вирішення задач, опис яких представлений у вигляді математичних записів.

Генератори випадкових чисел – це програми, які виробляють деяке числове значення з незалежних випадкових чисел із врахуванням закону їх розподілу.

Випадкове число – це значення, отримане довільним чином з деякої послідовності чисел, без врахування зв’язку з іншими членами цієї послідовності і з певною ймовірністю в будь-якому заданому інтервалі.

Причини використання:

1. моделювання (ядерна фізика, системний аналіз);

2. вибірка (немає можливості перевіряти усі варіанти, випадкова вибірка дозволяє отримати відповідь);

3. числовий аналіз (для вирішення складних математичних задач, спеціальна технологія на випадкових числах);

4. аналіз алгоритмів (оцінка ефективності алгоритмів);

5. прийняття рішення (випадково обраний вибір (варіант)).

Методи отримання випадкових значень:

1. вибір із статичної таблиці;

2. обчислення «середини квадрату»: попереднє (вихідне) число підводиться у степінь двійки і з результату вилучаються середні цифри (тобто, ігноруються декілька перших і останніх чисел). Недолік – послідовності випадкових чисел мають тенденцію перетворюватися в короткі цикли елементів, що повторюються.

3. лінійний конгруентний метод: обчислюється дійсне значення, рівномірно розподілене між нулем і одиницею U(i)=X(i)m; ціле число у діапазоні від нуля до m – значення на одиницю більше максимального числа встановленої розрядності (наприклад, розрядність представлення цілого числа 16 біт -> 2(^16)=65536).

Ціле значення обчислюється за наступним відношенням: X(i+1)=(aX(i)+c)mod m, i>=0, початкове значення (0) більше чи ріне нулю, а – коефіцієнт (те ж), с – зсув (зміщення), му – модуль, що більший за початкове значення, а і с.

Цикл, що повторюється, називається періодом. Коли с=0 – мультиплікативний конгруентний метод, якщо с не дорівнює 0 – змішаний.

Вибір модулю.

Умови:

1. значення му має бути достатньо великим. Щоб період був великим;

2. швидкість вироблення числа має бути як можна меншою.

Перший варіант:

вибрати значення му як 2(с)=омега +1 (омега – максимальне значення с із розрядністю е), тоді дорого вартісну операцію ділення можна не використовувати (скорочується час обчислення).

Другий варіант:

Вибір у якості му найбільшого простого числа, меншого за омегу.

Вибір коефіцієнта

Впливає на довжину періоду і випадковість вибірки.

Необхідна максимальна довжина періоду, тоді с і му – взаємно прості числв; бе = а-1 кратне р (тобто, всім простим дільникам му); бе кратне 4. Якщо і модуль кратний 4.

Значення а має бути таким, щоб а мод 8 = 5 (для двійкової СЧ);

а мод 200 = 21 (для десяткової СЧ);

корінь із му менше за а і менше за му-корінь з му.

Вибір зміщення

1. значення с має бути непарним і не кратним 5 (для десятинної СЧ);

2. відношення с поділити на му приблизно дорівнює 0.21113248654051871;

4. адитивний метод:

це по суті змінений конгруентний метод, де наступне значення обчислюється у залежності від двох попередніх X(i+1)=(X(i)+X(i-k))mod m, k – деяке велике значення. Заздалегідь створюється послідовність X(0)…X(k), X(i)=X(k).

5. комбінований метод:

за двома заданими методами обчислюються дві послідовності <X(n)> I <Y(n)>, отримані двома незалежними способами, при цьому періоди цих послідовностей – взаємно прості числа. Використовується додатковий масив розмірності k, де воно дорівнює 100, котрий заповнюється першими кА елементами із послідовності Х(ен). Шукана послідовність випадкових значень формується за алгоритмом:

1. вичислюється j=kY(i)/m, when 0<=j<k, 0<=i<n;

2. з масиву обирається V(j);

3. елемент перевизначається V(j)=X(i).

Розв’язок системи лінійних рівнянь

Система лінійних рівнянь із ен невідомих:

а(11)х(1)+… a(1n)x(n)=b1;

-||-

Or

Matrix

Введемо позначення A=(a(ij), x=(x(i))), b=(b(i)),

Then Ax=b -> x=A(^-1)b.

Метод LUP-розкладу (L – unit lower-triangalar matrix, U – upper, P - permutation) або Метод НВП-матриця (Н – одинична нижньо-трикутна матриця, В – верхнє, П – матриця перестановки (у кожному рядку і стовпці може бути лише одна одиниця)).

1. Необхідно помножити обидві частини рівності на матрицю перестановки: RAx=Pb;

2. Оскільки PA=LU, LUx=Pb;

3. Замінивши y=Ux отримаємо Ly=Pb.

4. Використовуючи «пряму підстановку» (y(1)=b(Pi)[1]; l(21)y(1)+y(2)=b(Pi)[2]; … l(n1)y()1)+ l(n2)y(2)+… + y(n)=b(Pi)[n]; meaning y(i)=b(Pi)[i]-Sum (j=1 to i-1)l(ij)y(j)), розв’язуємо останню рівність відносно ігрика.

5. Використовуючи «обернену підстановку» (x(i)=(y(i)- Sum(j=i+1 to n)u(ij)x(j))/u(ii)), знаходимо розв’язок вихідної системи рівностей х.

Для визначення (побудови) LU-розкладу використовується метод виключення Гауса:

1. Перша змінна видаляється із усіх рівностей шляхом віднімання з них першого та множення на відповідний коефіцієнт;

2. Ці дії повторюються для всі рівностей шляхом послідовного виключення всіх змінних.

В результаті отримаємо верхньо-трикутну матрицю і одиничну нижньо-трикутну матрицю х коефіцієнтів, що приймали участь у процес виключення.

Алгоритм Штрассена для перемноження матриць, результуюча представляється у вигляді:

…

Елементи, на які у процесі розкладу ділять, називаються (вести).

Вибір ведучого елементу U[i][i]=A[i][i];

Формування вектора-стовпця та вектора-рядка

For (int j=i+1; j<n; j++)

{L[j][i]=A[j][i]…

Формування матриці на порядок менше вихідної))))

Матриця перестановки використовується для того, щоб уникнути ділення на нуль. Цей процес називається вибором ведучого елемента.

Зазвичай ведучий елемент обирається як найбільший за модулем у першому стовпці матриці, яку розкладають.

Кодидидидидидиидидидидидиддидддддддддддддддддддд)))

Перестановка рядків в матриці коефіцієнтів, формування елементів матриць L i U

Численні методи

- це методи приблизного розв’язку математичних задач. Реалізація цих методів дозволяє отримати частковий розв’язок задачі, на відміну від аналітичних методів (загальний розв’язок).

Класифікація:

1) інтегральні рівності: метод трапеції, прямокутників та парабол;

2) алгебраїчні рівності: метод хорд, дотичних та половинного ділення;

3) диференціальні рівняння: метод Ейлера та Рунге-Кутта (2-го, 3-го і 4-го порядку).

Розв’язок інтегральних рівнянь:

1. Метод прямокутників

Приблизне значення інтегралу визначається як сума площ прямокутників, сторонами яких є довжина відрізка інтегрування (крок) і значення функції на і-тому кроці. (рисуночок)

У залежності від вибору початкового значення функції у діапазоні [a; b] виділяють ліві прямокутники, праві та серединні.

2. Метод трапеції

Приблизне значення інтегралу визначається як сума площ трапецій, сторонами яких є крок і значення функції на і-тому кроці.

3. Метод парабол

Приблизне значення інтегралу визначається як сума площ фігури під параболою на і-тому кроці.

Розв’язок алгебраїчних рівнянь:

В загальному випадку алгебраїчне рівняння має вигляд f(x)=0; його розв’язок – його корені (кв. двочлен=0; + графік – вершина унизу).

1. Метод половинного ділення

Обирається відрізок зміни значення x[a,b] такий, щоб функція була неперервною і мала значення на кінцях відрізка з різними знаками. Тоді таке рівняння має хоча б один корінь, який можна вирахувати з заданною точністю:

- відрізки діляться навпіл;

- обчислюється значення функції для середнього і визначається знак;

- якщо функція не дорівнює нулю, то відбувається ділення тієї частини відрізка, де знаки функції на кінцях відрізка і його середині відмінні;

- процес повторюється поки функція не стане рівна нулю або менше деякого епсілон (заданої точності).

2. Метод дотичних

Обирається відрізок зміни значення x[a,b] такий, щоб функція була неперервною і мала значення на кінцях відрізка з різними знаками, а також значення першої та другої похідних не рівні нулю. Тоді приблизне значення кореня знаходиться як абсциса точки перетину дотичної до функції з віссю ОХ;

- перша дотична проводиться для точки (a, f(a)) або (b,f(b)), у якої значення першої та другої похідних більше нуля;

- наступна проводиться для нової точки (x, f(x)) і визначається наступне приблизне значення х;

- процес повторюється до тих пір, поки функція не стане рівна нулю або менше епсілону.

x(i+1)=x(i)-f(x(i))/f’(x(i)), i=0,1,2,3…

3. Метод хорд (лінійне інтерполювання)

Обирається відрізок …… теж саме)))

Тоді приблизне значення кореня знаходиться як абсциса точки перетину хорди, що проходить через деякі точки на кривій, з віссю ОХ;

- перша абсциса точки перетину з віссю ОХ х(1) визначається хордою, що проходить через точки (оті а і бе);

- поки функція більша за епсілон, визначається наступна абсциса точки перетину з віссю ОХ хорди, що проходить через точки (а і х(і)), якшо f(a)*f(x(і))<0 або точки бе і х(і), коли ф(бе)ф(хи) менше.

x(i)=a-[(b-a)f(a)]/[f(b)-f(a)]

*хорррррррррррррррррррддддддддддиииииииааа*

Розв’язок диференціальних рівнянь:

Диференціальне рівняння n-го порядку вигляду a(0)* [d(^n)*y(x)]/[d*x(^n)]+a(1)*[n-1…]/n-1+…+a(n-1)y(x)+ a(n)=0 використовується для математичного моделювання фізичних процесів і явищ. Для розв’язку таких рівнянь застосовуються методи численного інтегрування, які розв’язують рівняння 1-го порядку. Тому, диференціальне рівняння n-го порядку перетворюють у систему з n рівностей 1-го порядку.

y(x)=y(1)(x);

dy(1)(x)/dx=y(2)(x); ..

dy(n)(x)/dx= -[a(1)y(n-1)(x)+..+a(n-1)y(1)(x)+a(n)]/[a(0)];

………………………….FFFFFFFFFUUUUUUUUUUUUUUUUUUUUU!!!

1. Метод Ейлера

a(0)y(x)+a(1)y’(x)+a(2)=0, при початкових умовах x(0), y(x(0)), y’(x(0)). Для обчислення y(x):

- діапазон значень від х(0) до х розбивається на частини (n відрізків);

- для кожного відрізка обчислюється приріст функції і додається до попереднього значення: y(i+1)=y(i)+[дельта]y.

2. Метод Рунге-Кутта… ги-ги-ги)))

3. 4-го порядку

Рівняння перетворюється у систему диференціальних рівнянь першого порядку, для кожного з яких обираються початкові умови. Тоді для обчислення функції:

- діапазон розбивається на частини;

- для кожного відрізка обчислюється приріст функції і додається до попереднього значення:

Ячсмритьбюбдлшгонекіучсарпморилдтлжоєщгзнщешкгнківспомриотложщгшнщешук

Коди;

Регулярні вирази

- це текстовий рядок, що описує шаблон деякого тексту (інструмент, що використовується для його обробки). Призначені для пошуку інформації (слова; слів, що починаються з деяких символів; і тд), синтаксичного аналізу тексту.

Компоненти:

* Будь-який символ – будь-який, за виключенням спеціальних (‘а’, ‘№’, ‘р’, ‘~’, ‘5’, ‘\45’, ‘\023’, ‘\ua376’)

* Метасимвол - ^ \A – початок рядка; $ \Z \z – кінець рядка; . – один символ; | - вибір; () – обмеження при виборі, групування при повторі, запам’ятовування для повторного пошуку; \a, \n, \r, \t, \v, \e – керуючі символи; (…)\1,\2,… - повертаючі посилання.

* Клас символів – [будь-яких з вище перелічених символів][^будь-який відмінний від перелічених][символ - символ];

* квантифікатори - ? – нуль або один раз; + - один і більше; * - нуль або більше; {min, max} – діапазон повторів.

Якщо необхідно використати позначення метасимвола чи квантифікаторів у якості звичайного символу, тоді застосовується екранування:

1 \метасимвол - (\*,\+,\.,\?);

2 [метасимвол] - [+][*][?]

<вираз>::=<член>|<член>’|’<вираз>

<член>::=<коефіцієнт>|<коефіцієнт><член>

<коефіцієнт>::=<елемент>|<елемент>?|<елемент>*|<елемент>+

<Елемент>::=<символ?|,| (вираз)|<клас символів>

<символ>::=<будь-який, окрім спеціальних>

<клас символів>::=[<діапазон>]|[<діапазон>]<клас символів>

<діапазон>::=<набір символів>|<набір символів>-<набір символів>

Засоби мови Java для роботи з регулярними виразами

Для побудови і роботи використовується пакет java.util.regex;

Послідовність дій:

1 = створити рядок з регулярним виразом і відкомпілювати його у внутрішнє представлення (статичний метод compile() класу Pattern)

2 = асоціювати регулярний вираз з текстом (метод matcher())

3 = перевірка успішності співпадання

4 = отримання додаткової інформації про співпадання

5 = запит інформації

Кодиддддддддддддддддддддддидидидидидидидииииииииидддддддддддддддддииииииииииииди

Приклад застосування регулярного виразу для розпізнання функції y(x) заданого вигляду і обчислення з неї коефіцієнтів для обчислення інтеграла.

Код

Якщо потрібно один раз співставити текст з шаблоном то використовуються або статичний метод matches() класу Pattern, або методі matches() класу String.

Кінцеві автомати

Основні області застосування:

1. Програмне забезпечення для проектування і побудови моделі поведінки цифрових пристроїв.

2. Лексичний аналіз під час проектування побудови компіляторів для мов програмування і під час аналізу текстів природними мовами.

2. Програмне забезпечення для опрацювання і пошуку інформації на web-сторінках.

4. Програмне забезпечення для верифікації систем, котрі мають кінцеве число різноманітних станів (комунікація, криптографія і т.д.).

Автомат Мілі – це впорядкована п’ятірка {Q, X, Y, f(q), g(q)}, де Q – множина станів автомату, X – алфавіт вхідних символів, Y – алфавіт вихідних символів, f(q) – функція переходу (Q cross X=Q), q(p) – функція виходу (Q cross X = Y).

Класифікація автоматів:

1. якщо з множини станів автомату можна виділити деякий стан q(0), який називається початковим, то автомат називається ініціальним (впорядкована п’ятірка);

2. у залежності від визначення множини станів, алфавітів вхідних та вихідних символів автомату розрізняють:

- кінцевий автомат (якщо три множини Q, X, Y кінцеві);

- некінцевий (якщо хоча б одна з них некінцева).

3. у залежності від визначення функцій переходу розрізняють:

- повний автомат (якщо функції переходів і виходу повністю визначені);

- частковий автомат (якщо одна з функцій переходу чи виходу визначена лише частково);

4. у залежності від правил визначення функцій переходу розрізняють:

- детермінований автомат (якщо f(q) – функція, тобто існує однозначний перехід із стану q(i) в q(j) під час зчитування символу з алфавіту X);

- недетермінований (- відношення, тобто, існує декілька варіантів переходів з стану q(i));

5. якщо автомат представлений впорядкованою четвіркою {Q, X, f(q), F} чи, для ініціального автомату, впорядкованою п’ятіркою {Q, X, f(q), q(0), F}, F – підмножина станів Q, що називається заключними (акцентовними), то такий автомат – автомат без виходу (акцептор, Х-автомат);

6. Автомат Мура – частковий випадок автомату Мілі, у якого функція виходів g(q) виражається через функцію переходів f(q) наступним виразом: q(q)= h(f(q)), де h - це A->Y.

Способи представлення кінцевих автоматів:

1. Таблиці переходів і виходів автомату

Це дві матриці однакової розмірності, де рядки позначені символами з вхідної множини, а стовпчики – станами. //Q={0,1,2,3}, X={a,b}, Y={+,-}, q(0)=0; (f 0 1 2 3)/(a b)// Бажано, будуючи такі таблиці, стани розставляти по порядку – спочатку початковий, а в кінці, якщо є наявним, - кінцевий.

2. Граф переходів і виходів автомату

Це орієнтований граф, вершини якого визначають стани автомату, а ребра – взаємозв’язки (пара символів, розділених /, де перший – символ вхідного алфавіту, другий - вихідного). Умови його автоматності:

- умова однозначності (не існує двох ребер з однаковими вхідними відмітками, які виходять з одної і тої ж вершини);

- умова повноти (для довільних вершин і вхідного символу існує ребро, що виходить з цієї вершини і позначене цим символом).

//є кінцевий стан – кружечком обвели, а початковий стрілкою вказують.

Стан q(i) – досяжне з стану q(0), якщо існує вхідне слово p, яке переводить автомат з стану q(0) y q(i). Для встановлення досяжності достатньо визначити чи існеє шлях з вершини q(0) y q(i) у графі переходів і виходів.

Кооооооооооооооооооооооооооооооооооооооооооооод

ддддддддддддддд