Відмінності між версіями «Нормальні алгоритми»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[неперевірена версія][неперевірена версія]
м (r2.7.1) (робот додав: pt:Algoritmo de Markov)
Рядок 1: Рядок 1:
 
'''Нормальні алгоритми ''' (нормальні алгоритми) — вербальні [[алгоритм]]и, тобто, алгоритми, що перетворюють слова деякого (фіксованого) [[алфавіт]]у. Поняття нормального алгоритма введене радянським математиком [[Марков А. А.|А. А. Марковим]].
 
'''Нормальні алгоритми ''' (нормальні алгоритми) — вербальні [[алгоритм]]и, тобто, алгоритми, що перетворюють слова деякого (фіксованого) [[алфавіт]]у. Поняття нормального алгоритма введене радянським математиком [[Марков А. А.|А. А. Марковим]].
   
'''Нормальний алгоритм Маркова''' (НАМ) — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті.
+
'''Нормальний алгоритм Маркова''' — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті.
   
 
== Визначення нормального алгоритма ==
 
== Визначення нормального алгоритма ==

Версія за 14:19, 18 грудня 2012

Нормальні алгоритми (нормальні алгоритми) — вербальні алгоритми, тобто, алгоритми, що перетворюють слова деякого (фіксованого) алфавіту. Поняття нормального алгоритма введене радянським математиком А. А. Марковим.

Нормальний алгоритм Маркова — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті.

Визначення нормального алгоритма

Будь який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритма. Алфавітом нормального алгоритма може бути довільний скінченний алфавіт A. Формулами підстановок в алфавіті A називаються вирази подібні pq (проста пістановка) або p →• q (кінцева підстановка), де p та q — деякі слова в алфавіті A, які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт A не містить символів → та →•).

Кожний нормальний алгоритм в алфавіті A має скінченну кількість таких формул підстановок. Їх записуть у вигляді списку. Цей список називається схемою алгоритма.

Принцип дії

Застосування нормального алгоритма до слова s полягає в наступному.

  • В заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова s. Знаходять перше входження цієї частини в слові s і замість цього входження підставляють праву частину формули. Це дасть нове слово s1.
  • З отриманим словом s1 повторюють попередній крок.

Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритма. Крім того, постулють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул видуp →• q. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритма до слова s.

Приклад роботи

В якості прикладу схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер |*abc[1]:

При застосуванні алгоритма з наведеною вище схемою до слова будуть отримуватись слова:

  1. ,
  2. ,
  3. ,
  4. ,
  5. ,
  6. ,
  7. ,
  8. ,
  9. ,
  10. ,
  11. .

Результатом застосування буде слово .

Можливості нормальних алгоритфів

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

Аналог тези Чорча для нормальних алгорифмів є наступний принцип нормалізації А. А. Маркова: будь який алгорифм в алфавіті A достатньо еквівалентний відносно A деякому нормальному алгорифма над A.

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

Використовуючи поняття нормального алгорифма, Марков та інші дослідники довели нерозв'язність цілого набору алгоритмічних проблем.

Джерела інформації

Посилання

  1. Нормальный алгоритм (рос.), Википедия, 26 січня 2007.

Див. також

Література

  • Марков А. А. Теория алгорифмов. «Труды математического ин-та им. В. А. Стеклова АН СССР», 1954, т. 42.
  • Марков А. А., Нагорный Н. М. Теория алгорифмов. М.: Наука, 1984. – 432 с.