• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Лекція 4. Нормальні алгоритми Маркова.

План:

1 Означення і основні властивості НАМ.

2.Алгоритм роботи НАМ.

3. Приклади роботи НАМ.

4.Функції обчислюванні за Марковим.

Література:[1], [3], [10].

Пiд нормальним алгоритмом (скорочено НА) в алфавiтi T розуміють впорядковану послiдовнiсть продукцiй (правил) вигляду a®b, або a®×b, де a, bÎT*, а символи × , ®ÏT. Продукцiї вигляду a®×b називають фiнальними.

Кожен НА у алфавiтi T задає деяке словникове відображення T*→T*. Слово, яке є результатом обробки слова x нормальним алгоритмом A, позначається A(x). Обробка слова x нормальним алгоритмом A проводиться поетапно за наступною схемою.

Покладемо x₀=x i будемо вважати, що x₀ отримане iз слова x пiсля 0 етапiв роботи нормального алгоритму. Нехай слово x_n отримане iз слова x пiсля n етапiв роботи. Тодi (n+1)-й етап виконується наступним чином.

Шукаємо першу за порядком продукцію a®b або a®×b таку, що a є пiдсловом x_n. Застосуємо цю продукцію до x_n , тобто замінимо в x_n найлiвiше входження a на b. Отримане слово позначимо x_n+1. Якщо застосована на (n+1)-му етапі продукція не фiнальна, тобто a®b, то переходимо до (n+2)-го етапу. Якщо ця продукція фінальна, тобто a®×b, то пiсля її застосування A зупиняється i A(x)=x_n+1. Якщо ж на (n+1)-му етапі жодна продукція A не застосовна до x_n+1, тобто в Aнемає продукції, ліва частина якої - пiдслово слова x_n+1, то A зупиняється i A(x)=x_n.

Якщо в процесі обробки слова x нормальним алгоритмом Aне зупиняється ні на якому етапі, то вважаємо, що A(x) невизначене. Тобто алгоритм до такого слова не застосовний.

Нормальний алгоритм називають нормальним алгоритмом над алфавітом T, якщо він є нормальним алгоритмом в деякому розширенні T’ÊT. Такий нормальний алгоритм над T задає певне словникове відображення T*→T*, використовуючи в процесі обробки слів допомiжнi символи поза алфавітом T. Але вхідне і фінальне слово не повинні містити символів, що не належать Т. Зупинка нормального алгоритму Маркова A над T при роботі над словом хÎT*, результативна, коли вона відбулась на слові yÎT*, інакше вважаємо, що результат роботи A над х невизначеним.

Два нормальні алгоритми Маркова A i B вважаться еквівалентними відносно алфавіту T, якщо для всіх xÎT* A(x) та B(x) одночасно визначені або невизначені, та у випадку визначеності A(x)=B(x).

Функція називається обчислюваною за Марковим, або НА-обчислюваною, якщо існує нормальний алгоритм, який її обчислює.

Наведемо приклади нормальних алгоритмів Маркова.

Приклад 1. Нормальний алгоритм Маркова, який кожне слово виду a^x переводить в слово (тобто по суті задає функцію 2^х в розширеному алфавіті Т=(а,d, λ)).da ® add

ad ® d

d ® .d

λ ® d

Приклад 2. Нормальний алгоритм Маркова, який реалізує функцію f(x,y)=x-y алфавіті Т=(1, -, λ) .

1-1 ® -

1- ® . λ

Читайте також:

1. Алгоритми
2. Алгоритми арифметичних операцій над цілими невід’ємними числами у десятковій системі числення.
3. Алгоритми групи KWE
4. Алгоритми захисту цифрової просторової інформації
5. Алгоритми керування ресурсами
6. Алгоритми переведення чисел з однієї позиційної системи числення в іншу
7. Алгоритми побудови дерев екстремальної ваги
8. Алгоритми розрахунків
9. Алгоритми симетричного і асиметричного шифрування
10. Алгоритми та блок-схеми
11. Алгоритми Шаміра, RSA та Діффі-Хеллмана
12. Алгоритми шифрування в електронних картах

Переглядів: 1956