Відмінності між версіями «Визначення нормального алгоритму і його виконання»
Melani (обговорення • внесок) (Створена сторінка: В середині минулого століття видатний російський математик А.А. Марков ввів поняття норм...) |
Melani (обговорення • внесок) |
||
| Рядок 3: | Рядок 3: | ||
Для визначення НАМ вводиться довільний алфавіт - кінцеве непорожня множина символів, за допомогою яких описується алгоритм і дані. В алфавіт також включається порожній символ, який ми будемо позначати грецькою буквою. Під словом розуміється будь-яка послідовність непустих символів алфавіту або порожній символ, який позначає порожнє слово. | Для визначення НАМ вводиться довільний алфавіт - кінцеве непорожня множина символів, за допомогою яких описується алгоритм і дані. В алфавіт також включається порожній символ, який ми будемо позначати грецькою буквою. Під словом розуміється будь-яка послідовність непустих символів алфавіту або порожній символ, який позначає порожнє слово. | ||
| − | Всякий НАМ визначається кінцевою впорядкованою множиною пар слів алфавіту, названих підстановками. У парі слів підстановки ліве (перше) слово непорожній, а праве (друге) слово може бути порожнім символом. Для наочності ліве і праве слово розділяються стрілкою. | + | Всякий НАМ визначається кінцевою впорядкованою множиною пар слів алфавіту, названих підстановками. У парі слів підстановки ліве (перше) слово непорожній, а праве (друге) слово може бути порожнім символом. Для наочності ліве і праве слово розділяються стрілкою. |
| + | |||
| + | В якості даних алгоритму береться будь-яка непорожній рядок символів. Робота НАМ складається з послідовності абсолютно однотипних кроків. Крок роботи алгоритму може бути описаний таким чином: | ||
| + | 1.У впорядкованої послідовності підстановок шукаємо найпершу підстановку, ліве слово якої входить в рядок даних. | ||
| + | 2.У рядку даних шукаємо найперше (ліве) входження лівого слова знайденої підстановки. | ||
| + | 3.Це входження в рядку даних замінюємо на праве слово знайденої підстановки (перетворення даних). | ||
| + | |||
| + | Крок роботи алгоритму повторюється до тих пір, поки | ||
| + | *або не виникне ситуація, коли крок не зможе бути виконаний через те, що жодна підстановка не підходить (ліве слово підстановки вже не входить в рядок даних) - правило зупинки; | ||
| + | *або не буде встановлено, що процес підстановок не може зупинитися. | ||
| + | |||
| + | У першому випадку рядок даних, що вийшла, при зупинці алгоритму, є вихідний (результатом) і алгоритм застосуємо до вхідних даних, а в другому випадку алгоритм не застосуємо до вхідних даних. | ||
Версія за 17:07, 29 жовтня 2012
В середині минулого століття видатний російський математик А.А. Марков ввів поняття нормального алгоритму (алгорифм) з метою уточнення поняття "алгоритм", що дозволяє вирішувати задачі по визначенню алгоритмічно нерозв'язних проблем. Пізніше це поняття отримало назву нормального алгоритму Маркова (НАМ). Мова НАМ, з одного боку, навмисно бідна, що необхідно для мети введення поняття "алгоритм". Однак, з іншого боку, ідеї НАМ покладені в основу великої групи мов програмування, що одержали назву мови логічного програмування.
Для визначення НАМ вводиться довільний алфавіт - кінцеве непорожня множина символів, за допомогою яких описується алгоритм і дані. В алфавіт також включається порожній символ, який ми будемо позначати грецькою буквою. Під словом розуміється будь-яка послідовність непустих символів алфавіту або порожній символ, який позначає порожнє слово.
Всякий НАМ визначається кінцевою впорядкованою множиною пар слів алфавіту, названих підстановками. У парі слів підстановки ліве (перше) слово непорожній, а праве (друге) слово може бути порожнім символом. Для наочності ліве і праве слово розділяються стрілкою.
В якості даних алгоритму береться будь-яка непорожній рядок символів. Робота НАМ складається з послідовності абсолютно однотипних кроків. Крок роботи алгоритму може бути описаний таким чином: 1.У впорядкованої послідовності підстановок шукаємо найпершу підстановку, ліве слово якої входить в рядок даних. 2.У рядку даних шукаємо найперше (ліве) входження лівого слова знайденої підстановки. 3.Це входження в рядку даних замінюємо на праве слово знайденої підстановки (перетворення даних).
Крок роботи алгоритму повторюється до тих пір, поки
- або не виникне ситуація, коли крок не зможе бути виконаний через те, що жодна підстановка не підходить (ліве слово підстановки вже не входить в рядок даних) - правило зупинки;
- або не буде встановлено, що процес підстановок не може зупинитися.
У першому випадку рядок даних, що вийшла, при зупинці алгоритму, є вихідний (результатом) і алгоритм застосуємо до вхідних даних, а в другому випадку алгоритм не застосуємо до вхідних даних.
