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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
м
 
(Не показані 19 проміжних версій 3 користувачів)
Рядок 1: Рядок 1:
'''Нормальні алгоритми ''' (нормальні алгоритми) — вербальні [[алгоритм]]и, тобто, алгоритми, що перетворюють слова деякого (фіксованого) [[алфавіт]]у. Поняття нормального алгоритму введене радянським математиком [[Марков Андрій Андрійович (молодший)|А. А. Марковим]] у 1956-му році.
+
'''Нормальні алгоритми Маркова (нормальні алгорифми)''' — формалізація поняття алгоритму, що являє собою систему послідовних застосувань підстановок до слів певного алфавіту, введена математиком [[Марков Андрій Андрійович (молодший)|А. А. Марковим]] у 1956-му році. Доведено що нормальні алгоритми [[Повнота за Тюрингом|повні за Тюрингом]], тобто можуть описувати всі алгоритми що можуть виконуватись будь-яким комп'ютером.
 
'''Нормальний алгоритм Маркова''' — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті.
 
   
 
== Визначення нормального алгоритму ==
 
== Визначення нормального алгоритму ==
  +
Будь-який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритму. Алфавітом нормального алгоритму може бути довільний скінченний алфавіт ''A''.
   
Будь-який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритму. Алфавітом нормального алгоритму може бути довільний скінченний алфавіт ''A''. Формулами підстановок в алфавіті ''A'' називаються вирази подібні ''p'' → ''q'' (проста пістановка) або ''p'' →• ''q'' (кінцева підстановка), де ''p'' та ''q'' — деякі слова в алфавіті ''A'', які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт ''A'' не містить символів → та →•).
+
Схемою нормального алгоритму називають список формул підстановок цього алгоритму. Формулами підстановок в алфавіті ''A'' називаються вирази подібні ''p'' → ''q'' (проста підстановка) або ''p'' →• ''q'' (заключна підстановка), де ''p'' та ''q'' — деякі слова в алфавіті ''A'', які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт ''A'' не містить символів → та →•).
 
Кожний нормальний алгоритм в алфавіті ''A'' має скінченну кількість таких формул підстановок. Їх записують у вигляді списку. Цей список називається схемою алгоритму.
 
   
 
=== Принцип дії ===
 
=== Принцип дії ===
Рядок 16: Рядок 13:
 
* З отриманим словом ''s''<sub>1</sub> повторюють попередній крок.
 
* З отриманим словом ''s''<sub>1</sub> повторюють попередній крок.
   
Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул виду''p'' →• ''q''. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова ''s''.
+
Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулюють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із заключних формул підстановки, тобто, формул виду ''p'' →• ''q''. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова ''s''.
   
=== Приклад роботи ===
+
=== Перший приклад роботи ===
   
Як приклад схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер <tt>|*abc</tt>:
+
Як приклад схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер <tt>|*abc</tt>, яка реалізовує унарне множення:
   
 
<math>\left\{\begin{matrix}
 
<math>\left\{\begin{matrix}
Рядок 46: Рядок 43:
 
# <math>c||</math>,
 
# <math>c||</math>,
 
# <math>||</math>.
 
# <math>||</math>.
Результатом застосування буде слово <math>||</math>.
+
Результатом застосування буде слово <math>||</math>, що узгоджується з <math>|*|| = ||</math>.
   
  +
=== Другий приклад роботи ===
== Можливості нормальних алгоритмів ==
 
  +
Даний алгоритм перетворює [[Двійкова система числення|двійкові числа]] в «<nowiki/>[[Унарна система числення|унарні]]<nowiki/>» (в яких записом цілого невід'ємного числа N є рядок з N паличок). Наприклад, двійкове число 101 перетвориться в 5 паличок: |||||.
   
  +
==== Алфавіт ====
Доведено, що відносно виконуваних перетворень, нормальні алгоритми збігаються з іншими класами алгоритмів, введених для уточнення інтуїтивного поняття алгоритму, наприклад, з [[Машина Тюринга|машинами Тюринга]].
 
  +
{ 0, 1, | }.
   
  +
==== Правила ====
Аналог [[Чорча теза|тези Чорча]] для нормальних алгорифмів є такий принцип нормалізації А.&nbsp;А.&nbsp;Маркова: будь-який алгорифм в алфавіті ''A'' достатньо еквівалентний відносно ''A'' деякому нормальному алгорифма над ''A''.
 
   
  +
# 1 → 0|,
Визначення алгоритмів у нормальному вигляді дуже схоже на [[числення]], і це є дуже корисним у випадках, коли поняття числення в досліджуваному розділі [[математика|математики]] або [[кібернетика|кібернетики]] широко застосовують, як, приміром, в [[логіка математична|математичній логіці]] або в [[лінгвістика математична|математичній лінгвістиці]].
 
  +
# |0 → 0||,
  +
# 0 → (порожній рядок).
   
  +
==== Покрокове виконання алгоритму ====
Використовуючи поняття нормального алгоритма, Марков та інші дослідники довели нерозв'язність цілого набору алгоритмічних проблем.
 
  +
При застосуванні алгоритму з наведеною вище схемою до слова 101 будуть отримуватись слова:
   
  +
# 0|01,
  +
# 0|00|,
  +
# 00||0|,
  +
# 00|0|||,
  +
# 000|||||,
  +
# 00|||||,
  +
# 0|||||,
  +
# |||||.
   
  +
== Можливості нормальних алгоритмів ==
= 1 =
 
   
  +
Доведено, що відносно виконуваних перетворень, нормальні алгоритми збігаються з іншими класами алгоритмів, введених для уточнення інтуїтивного поняття алгоритму, наприклад, з [[Машина Тюринга|машинами Тюринга]].
== Нормальні Алгоритми Маркова. Побудова алгоритмів з алгоритмів ==
 
В запропонованому марковим уточненні виділені 7 параметрів були визначені таким чином:
 
* Сукупність початкових даних&nbsp;— слова в алфавіті S;
 
* Сукупність можливих результатів&nbsp;— слова в алфавіті W;
 
* Сукупність можливих проміжних результатів&nbsp;— слова в алфавіті
 
* Р = SWV, де V&nbsp;— алфавіт службових допоміжних символів.
 
P *&nbsp;— безліч слів над алфавітом Р, n називається правилом підстановки. Сенс цього правила полягає в тому, що оброблюване слово w є видимим зліва направо і шукається входження в нього слова a. Слово a називається входженням в слово w, якщо існують такі слова b і n над тим же алфавітом, що і a і w, для яких вірно: w = ban. Якщо входження a в w знайдено, то слово a замінюється на слово g. Всі правила постановки упорядковуються. Спочатку шукається входження для першого правила підстановки. Якщо воно знайдено, то відбувається підстановка і перетворюване слово знову проглядається зліва направо у пошуках входження. Якщо входження для першого правила не знайдено, то шукається входження для другого правила і&nbsp;т.&nbsp;д. Якщо входження знайдено для n-го правила підстановки, то відбувається підстановка, і перегляд правил починається з першого, а слово проглядається спочатку і зліва направо. Вся сукупність правил підстановки називається схемою алгоритму.
 
   
  +
Аналог [[Чорча теза|тези Чорча]] для нормальних алгорифмів є такий принцип нормалізації А.&nbsp;А.&nbsp;Маркова: будь-який алгорифм в алфавіті ''A'' достатньо еквівалентний відносно ''A'' деякому нормальному алгорифма над ''A''.
   
  +
Визначення алгоритмів у нормальному вигляді дуже схоже на [[числення]], і це є дуже корисним у випадках, коли поняття числення в досліджуваному розділі [[математика|математики]] або [[кібернетика|кібернетики]] широко застосовують, як, приміром, в [[логіка математична|математичній логіці]] або в [[лінгвістика математична|математичній лінгвістиці]].
   
  +
Використовуючи поняття нормального алгоритму, Марков та інші дослідники довели нерозв'язність цілого набору алгоритмічних проблем.
== Принцип дії ==
 
Застосування нормального алгоритму до слова ''s'' полягає в наступному.
 
   
* В заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова ''s''. Знаходять перше входження цієї частини в слові ''s'' і замість цього входження підставляють праву частину формули. Це дасть нове слово ''s''<sub>1</sub>.
 
* З отриманим словом ''s''<sub>1</sub> повторюють попередній крок.
 
   
Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулюють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул виду''p'' →• ''q''. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова ''s''.
 
   
 
== Див. також ==
 
== Див. також ==
Рядок 95: Рядок 97:
 
* [[Енциклопедія кібернетики]], т. '''2''', c. 90—91.
 
* [[Енциклопедія кібернетики]], т. '''2''', c. 90—91.
 
* Джон Хопкрофт, Раджів Мотані, Джеффрі Ульман РОЗДІЛ 8. Введення в теорію машин Тюрінга // Введення в теорію автоматів, мов і обчислень.&nbsp;— М., 2002.&nbsp;— С528.
 
* Джон Хопкрофт, Раджів Мотані, Джеффрі Ульман РОЗДІЛ 8. Введення в теорію машин Тюрінга // Введення в теорію автоматів, мов і обчислень.&nbsp;— М., 2002.&nbsp;— С528.
  +
* {{cite book|
* ''Марков А. А.'' Теория алгорифмов. «Труды математического ин-та им. В.&nbsp;А.&nbsp;Стеклова АН СССР», 1954, т. 42. {{ref-ru}}
 
  +
|last=Марков
  +
|first=А. А.
  +
|authorlink=Марков Андрій Андрійович (молодший)
  +
|title=Теория алгорифмов. «Труды математического ин-та им. В.&nbsp;А.&nbsp;Стеклова АН СССР»
  +
|year=1954
  +
|volume=42
  +
|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tm&paperid=1178&option_lang=rus
  +
|ref=harv
  +
}} {{ref-ru}}
 
* ''Марков А. А., Нагорный Н. М.'' Теория алгорифмов.&nbsp;— М.: Наука, 1984.&nbsp;— 432 с. {{ref-ru}}
 
* ''Марков А. А., Нагорный Н. М.'' Теория алгорифмов.&nbsp;— М.: Наука, 1984.&nbsp;— 432 с. {{ref-ru}}
   
 
=== Посилання ===
 
=== Посилання ===
 
* [http://yad-studio.github.io/ Yad Studio&nbsp;— IDE та інтерпритатор для Нормальних Алгоритмів Маркова (Open Source)]
 
* [http://yad-studio.github.io/ Yad Studio&nbsp;— IDE та інтерпритатор для Нормальних Алгоритмів Маркова (Open Source)]
 
{{math-stub}}
 
   
 
[[Категорія:Теорія алгоритмів]]
 
[[Категорія:Теорія алгоритмів]]

Поточна версія на 09:37, 11 травня 2019

Нормальні алгоритми Маркова (нормальні алгорифми) — формалізація поняття алгоритму, що являє собою систему послідовних застосувань підстановок до слів певного алфавіту, введена математиком А. А. Марковим у 1956-му році. Доведено що нормальні алгоритми повні за Тюрингом, тобто можуть описувати всі алгоритми що можуть виконуватись будь-яким комп'ютером.

Визначення нормального алгоритму[ред. | ред. код]

Будь-який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритму. Алфавітом нормального алгоритму може бути довільний скінченний алфавіт A.

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

Принцип дії[ред. | ред. код]

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

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

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

Перший приклад роботи[ред. | ред. код]

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

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

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

Результатом застосування буде слово , що узгоджується з .

Другий приклад роботи[ред. | ред. код]

Даний алгоритм перетворює двійкові числа в «унарні» (в яких записом цілого невід'ємного числа N є рядок з N паличок). Наприклад, двійкове число 101 перетвориться в 5 паличок: |||||.

Алфавіт[ред. | ред. код]

{ 0, 1, | }.

Правила[ред. | ред. код]

  1. 1 → 0|,
  2. |0 → 0||,
  3. 0 → (порожній рядок).

Покрокове виконання алгоритму[ред. | ред. код]

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

  1. 0|01,
  2. 0|00|,
  3. 00||0|,
  4. 00|0|||,
  5. 000|||||,
  6. 00|||||,
  7. 0|||||,
  8. |||||.

Можливості нормальних алгоритмів[ред. | ред. код]

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

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

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

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


Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

Література[ред. | ред. код]

Посилання[ред. | ред. код]