Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.
Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.
В 1956 году отечественным математиком А.А. Марковым было предложено новое уточнение понятия алгоритма, которое позднее было названо его именем.
В этом уточнении выделенные нами 7 параметров были определены следующим образом:
Совокупность исходных данных - слова в алфавите S;
Совокупность возможных результатов - слова в алфавите W;
Совокупность возможных промежуточных результатов - слова в алфавите
Р=S
W
V, где V - алфавит служебных вспомогательных символов.
Действия:
Действия имеют вид либо a®g, либо a a g, где a, g ÎP*, где
P* - множество слов над алфавитом Р, и называется правилом подстановки. Смысл этого правила состоит в том, что обрабатываемое слово w просматривается слева направо и ищется вхождение в него слова a.
Определение.3.1. Слово a называется вхождением в слово w, если существуют такие слова b и n над тем же алфавитом, что и a и w, для которых верно: w=ban.
Если вхождение a в w найдено, то слово a заменяется на слово g.
Все правила постановки упорядочиваются. Сначала ищется вхождение для первого правила подстановки. Если оно найдено, то происходит подстановка и преобразуемое слово опять просматривается слева направо в поисках вхождения. Если вхождение для первого правила не найдено, то ищется вхождение для второго правила и т.д. Если вхождение найдено для i-го правила подстановки, то происходит подстановка, и просмотр правил начинается с первого, а слово просматривается сначала и слева направо.
Вся совокупность правил подстановки называется схемой алгоритма.
Правило начала - просмотр правил всегда начинается с первого.
Правило окончания - выполнение алгоритма заканчивается, если:
было применено правило подстановки вида a a g,
не применимо ни одно правило подстановки из схемы алгоритма.
7. Правило размещения результата - слово, полученное после окончания выполнения алгоритма.
Рассмотрим пример 1 из лекции 2:
построить алгоритм для вычисления
U(n)=n+1;
S={0,1,2,3,4,5,6,7,8,9}; S=W; V={*,+}.
Cхема этого НАМ показана на рисунке 3.1.
|
Больше работ по теме:
Структуры данных
Реферат Ссылочный тип данных. Динамические объекты. Реферат Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод Реферат Познание природы и логика Реферат Математика в средние века Реферат Предмет: Математика Тип работы: Реферат Новости образования
Российский государственный социальный университет реорганизует сеть своих филиалов
22 Июля 2016 16:26 Более 70 представителей крупных вузов АСЕАН подтвердили участие в форуме во Владивостоке 22 Июля 2016 12:51 Абызов: публикация первичных статсведений снизит бюрократическую нагрузку на школы 22 Июля 2016 11:53 В Чечне свыше 200 школьников сдали ЕГЭ с результатом свыше 90 баллов - министр 22 Июля 2016 05:36 Замглавы Минобрнауки РФ: задача сократить число людей с высшим образованием не стоит 21 Июля 2016 20:19 КОНТАКТНЫЙ EMAIL: [email protected] Скачать реферат © 2019 | Пользовательское соглашение ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ |
