ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.02.2021
Просмотров: 150
Скачиваний: 1
Алгорифм
Маркова
Операционные
правила
обработки
дискретных
сообщений
являются
алгоритмами
над
последовательностями
знаков
.
Приступим
теперь
к
уточнению
понимавшегося
до
сих
пор
интуитивно
понятия
алгоритма
.
В
частности
,
нам
предстоит
выяснить
,
что
можно
считать
„
элементарными
тактами
обработки
".
Без
сомнения
,
элементарной
операцией
над
последовательностями
знаков
может
считаться
замена
подслова
на
некоторое
слово
(
текстовая
замена
).
Будем
исходить
из
множеств
M
и
M’
слов
над
общим
набором
знаков
V
(
это
можно
делать
без
ограничения
общности
).
Отдельную
операцию
замены
(
продукцию
)
будем
записывать
в
виде
а
-> b
и
понимать
её
так
:
если
а
является
подсловом
заданного
слова
х
,
то
заменить
это
подслово
на
b
.
В
случае
если
подслово
а
встречается
в
х
несколько
раз
,
словом
b
заменяется
то
из
них
,
которое
стоит
в
самой
левой
позиции
.
Далее
,
если
дано
(
конечное
)
множество
таких
продукций
,
перечисленных
в
определённом
порядке
,
то
текстовая
замена
должна
производиться
посредством
применения
самой
первой
(
относительно
этого
порядка
)
из
применимых
продукций
.
Всё
это
повторяется
до
тех
пор
,
покуда
возможно
,
или
же
до
применения
особым
образом
отмеченной
продукции
(„
останавливающей
").
Такого
рода
алгоритмы
называют
алгорифмами
Маркова
по
имени
советского
математика
А
.
А
.
Маркова
,
который
впервые
описал
их
(
в
1951
г
.);
сам
Марков
называл
их
„
нормальными
алгорифмами
"
Алгоритмы
Маркова
можно
считать
уточнением
понятия
алгоритма
,
достигаемым
за
счёт
использования
специальной
формы
описания
.
В
качестве
примера
приведем
алгоритм
Маркова
,
который
по
заданному
двоичному
слову
строит
производное
двоичное
слово
.
Этот
алгоритм
использует
вспомогательные
знаки
β
α
,
(„
челноки
")
и
содержит
следующие
продукции
:
Останавливающие
продукции
отмечены
точкой
.
На
рис
. 2
показано
применение
алгоритма
к
слову
OOLLOLLLOLOL
OOLLOLLLOLOL
α
OOLLOLLLOLOL
O
α
OLLOLLLOLOL
OO
α
LLOLLLOLOL
OOL
β
LOLLLOLOL
OOLO
β
OLLLOLOL
OOLOL
α
LLLOLOL
OOLOLL
β
LLOLOL
OOLOLLO
β
LOLOL
OOLOLLOO
β
OLOL
OOLOLLOOL
α
LOL
OOLOLLOOLL
β
OL
OOLOLLOOLLL
α
L
OOLOLLOOLLLL
β
OOLOLLOOLLLL
Рис
2
. “
Челнок
”.
Благодаря
компактным
правилам
замены
алгоритмы
Маркова
представляют
собой
мощное
средство
описания
:
на
сегодня
нет
таких
алгоритмов
над
последовательностями
знаков
,
для
которых
не
существовало
бы
алгоритма
Маркова
,
выполняющего
ту
же
самую
обработку
сообщений
.
Описания
,
сформулированные
в
виде
алгоритмов
Маркова
,
часто
оказываются
весьма
короткими
по
сравнению
с
другими
,
менее
„
рафинированными
"
формами
описания
.
Заметим
,
что
элементарную
для
алгоритмов
Маркова
операцию
замены
можно
также
рассматривать
как
сложную
,
рекурсивно
определяемую
операцию
над
последовательностями
знаков
.
Поэтому
понятие
элементарности
всегда
относительно
.
В
зависимости
от
информации
,
содержащейся
в
обрабатываемых
сообщениях
,
часто
,
наоборот
,
рассматривают
как
элементарные
такие
такты
обработки
,
которые
,
собственно
говоря
,
являются
сложными
.
Основанием
для
этого
может
служить
,
например
,
тот
факт
,
что
такие
макротакты
фактически
состоят
из
конечного
числа
описанных
выше
текстовых
замен
,
причём
их
внутренняя
структура
несущественна
для
предпринимаемой
обработки
.
Так
обстоит
дело
,
скажем
,
для
сложения
,
вычитания
,
умножения
и
деления
с
остатком
,
в
случае
,
когда
сообщения
представлены
целыми
числами
в
некоторой
цифровой
форме
записи
.
В
остальном
же
несущественно
,
представлена
последовательность
инструкций
в
виде
диаграммы
или
как
-
нибудь
более
схематично
,
равно
как
несущественно
и
то
,
описаны
отдельные
такты
обработки
словесно
или
заданы
посредством
формул
.
Собственно
действия
с
числами
в
цифровой
записи
относятся
,
таким
образом
,
к
классу
алгоритмов
над
цепочками
знаков
.
Здесь
в
арифметике
мы
обнаруживаем
исторические
корни
слова
algorismo;
еще
Лейбниц
говорил
об
„
алгоритме
умножения
".
А
.
А
.
Марковым
был
сформулирован
принцип
нормализации
:
всякая
вычислимая
в
интуитивном
смысле
функция
вычислима
с
помощью
некоторого
нормального
алгорифма
.
Из
эквивалентности
трех
приведенных
выше
уточнений
алгоритма
(
машина
Тьюринга
,
частично
-
рекурсивная
функция
и
нормальный
алгорифм
Маркова
)
следует
эквивалентность
соответствующих
тезисов
о
вычислимой
функции
.
Каждый
из
приведенных
тезисов
является
основанием
для
вывода
о
неразрешимости
алгоритмической
проблемы
после
того
,
как
доказано
,
что
эта
проблема
не
может
быть
решена
в
рамках
того
или
иного
уточнения
понятия
алгоритма
.
Ввиду
инвариантности
основных
результатов
общей
теории
алгоритмов
прикладное
значение
ее
результатов
никак
не
связано
с
тем
,
насколько
близки
к
практике
используемые
в
ней
теоретические
модели
алгоритмов
.
Машины
Тьюринга
весьма
далеки
от
современных
ЭВМ
,
а
рекурсивные
функции
—
от
языков
программирования
прежде
всего
из
-
за
предельной
скромности
используемых
средств
.
Однако
именно
скромность
средств
,
во
-
первых
,
делает
эти
модели
чрезвычайно
удобным
языком
доказательств
,
а
во
-
вторых
,
позволяет
по
-
нять
,
без
чего
обойтись
нельзя
,
а
без
чего
можно
и
какой
ценой
,
т
.
е
.
отличать
удобства
от
принципиальных
возможностей
.
Иначе
говоря
,
прикладное
значение
рассматриваемых
здесь
моделей
заключается
в
том
,
что
с
их
помощью
удобно
строить
теорию
,
верную
для
любых
алгоритмических
моделей
,
в
том
числе
и
для
сколь
угодно
близких
к
практике
.
Поскольку
несмотря
на
их
универсальность
,
эти
способы
описания
алгоритмов
оказались
практически
неприемлемыми
для
описания
алгоритмов
решения
задач
при
их
реализации
на
ЭВМ
,
возникла
необходимость
создания
языков
программирования
(
алгоритмических
языков
),
в
которых
находят
свое
отражение
такие
важные
особенности
решения
задач
на
современных
ЭВМ
,
как
наличие
различных
запоминающих
сред
,
внешние
среды
,
с
которым
связаны
ввод
и
вывод
данных
и
др
.
Вообще
говоря
,
теорию
алгоритмов
можно
разделить
на
дескриптивную
(
качественную
)
и
метрическую
(
количественную
).
Первая
исследует
алгоритмы
с
точки
зрения
устанавливаемого
между
исходными
данными
и
результатами
;
к
ней
относятся
,
в
частности
,
проблемы
построения
алгоритма
,
обладающего
теми
или
иными
свойствами
, -
алгоритмические
проблемы
.
Вторая
исследует
алгоритмы
с
точки
зрения
сложности
как
самих
алгоритмов
,
так
и
задаваемых
ими
вычислений
,
т
.
е
.
процессов
последовательного
преобразования
конструктивных
объектов
.