На головну

Нормальні алгорифм Маркова

  1.  ГЛАВА II. САМОГУБСТВО І НОРМАЛЬНІ ПСИХІЧНІ СТАНУ. РАСА. Спадковий
  2.  ГЛАВА II. САМОГУБСТВО І НОРМАЛЬНІ ПСИХІЧНІ СТАНУ. РАСА. Спадковий
  3.  Головні нормальні і головні дотичні напруження
  4.  Диз'юнктивні і кон'юнктівние нормальні форми.
  5.  Конструктивна логіка А. А. Маркова
  6.  Нервюри-нормальні і посилені.
  7.  НОРМАЛЬНІ АЛГОРИТМИ МАРКОВА

Автор - А. а. Марков, віддавав перевагу транскрипції алгоритмифм. Нормальні алгорифм Маркова представляються нормальної схемою підстановок, Яка складається із сукупності підстановок, розташованих в певному порядку. Підстановки мають вигляд: P ® (·)Q(P ® Q -(Проста) Підстановка, P ® ·Q -заключна підстановка).

Кажуть, що рядок R входить в рядок L, якщо L має вигляд L1RL2.

Кажуть, що підстановка застосовна до слова, якщо рядок, відповідна лівій частині підстановки, входить в слово. Застосування полягає в заміні в Перетворювані слові лівої рядки підстановки правої.

Дві особливі підстановки:

P ® - анулює.

® Q - породжує.

Механізм роботи нормальних алгорифм:

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

1) Слово завжди проглядається зліва направо.

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

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

Приклади.




 Завдання про 4 фарбах |  Визначення шляхів в графі |  Приведення графа до ярусно-паралельній формі |  Внутрішня стійкість графа |  ядро графа |  Побудова Кліки. |  морфізм груп |  Група Клейна четвертого ступеня |  поняття алгоритму |  складність обчислень |

© um.co.ua - учбові матеріали та реферати