В 1956 году отечественным математиком А.А. Марковым было предложено новое уточнение понятия алгоритма, которое позднее было названо его именем.
В этом уточнении выделенные нами 7 параметров были определены следующим образом:
Совокупность исходных данных - слова в алфавите S;
Совокупность возможных результатов - слова в алфавите W;
Совокупность возможных промежуточных результатов - слова в алфавите
Возможно вы искали - Реферат: Космическая программа Китая
Р=S
WV, где V - алфавит служебных вспомогательных символов.
Действия:
Действия имеют вид либо a®g, либо aag, где a, gÎP* , где
P* - множество слов над алфавитом Р, и называется правилом подстановки. Смысл этого правила состоит в том, что обрабатываемое слово w просматривается слева направо и ищется вхождение в него слова a.
Определение.3.1. Слово a называется вхождением в слово w, если существуют такие слова b и n над тем же алфавитом, что и a и w, для которых верно: w=ban.
Похожий материал - Реферат: Структуры данных
Если вхождение a в w найдено, то слово a заменяется на слово g.
Все правила постановки упорядочиваются. Сначала ищется вхождение для первого правила подстановки. Если оно найдено, то происходит подстановка и преобразуемое слово опять просматривается слева направо в поисках вхождения. Если вхождение для первого правила не найдено, то ищется вхождение для второго правила и т.д. Если вхождение найдено для i-го правила подстановки, то происходит подстановка, и просмотр правил начинается с первого, а слово просматривается сначала и слева направо.
Вся совокупность правил подстановки называется схемой алгоритма.
Правило начала - просмотр правил всегда начинается с первого.
Правило окончания - выполнение алгоритма заканчивается, если:
Очень интересно - Реферат: Ссылочный тип данных. Динамические объекты.
было применено правило подстановки вида aag,
не применимо ни одно правило подстановки из схемы алгоритма.
7. Правило размещения результата - слово, полученное после окончания выполнения алгоритма.
Рассмотрим пример 1 из лекции 2:
построить алгоритм для вычисления
Вам будет интересно - Реферат: Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод
U(n)=n+1;
S={0,1,2,3,4,5,6,7,8,9}; S=W; V={*,+}.
Cхема этого НАМ показана на рисунке 3.1.
 |
Перегоняем служебный символ * в конец слова n, чтобы отметить последнюю цифру младших разрядов. Увеличиваем на единицу, начиная с цифр младших разрядов. |
|
Похожий материал - Реферат: Познание природы и логика
| Вводим служебный символ * в слово, чтобы им отметить последнюю цифру в слове. |
Рис.3.1. Схема НАМ для вычисления U1 (n)=n+1
Нетрудно сообразить, что сложность этого алгоритма, выраженная в количестве выполненных правил подстановки, будет равна:
(k+1)+(l+1),