MaterStudiorum.ru - домашняя страничка студента.
Минимум рекламы - максимум информации.


Авиация и космонавтика
Административное право
Арбитражный процесс
Архитектура
Астрология
Астрономия
Банковское дело
Безопасность жизнедеятельности
Биографии
Биология
Биология и химия
Биржевое дело
Ботаника и сельское хоз-во
Бухгалтерский учет и аудит
Валютные отношения
Ветеринария
Военная кафедра
География
Геодезия
Геология
Геополитика
Государство и право
Гражданское право и процесс
Делопроизводство
Деньги и кредит
Естествознание
Журналистика
Зоология
Издательское дело и полиграфия
Инвестиции
Иностранный язык
Информатика
Информатика, программирование
Исторические личности
История
История техники
Кибернетика
Коммуникации и связь
Компьютерные науки
Косметология
Краткое содержание произведений
Криминалистика
Криминология
Криптология
Кулинария
Культура и искусство
Культурология
Литература и русский язык
Литература(зарубежная)
Логика
Логистика
Маркетинг
Математика
Медицина, здоровье
Медицинские науки
Международное публичное право
Международное частное право
Международные отношения
Менеджмент
Металлургия
Москвоведение
Музыка
Муниципальное право
Налоги, налогообложение
Наука и техника
Начертательная геометрия
Новейшая история, политология
Оккультизм и уфология
Остальные рефераты
Педагогика
Полиграфия
Политология
Право
Право, юриспруденция
Предпринимательство
Промышленность, производство
Психология
Психология, педагогика
Радиоэлектроника
Разное
Реклама
Религия и мифология
Риторика
Сексология
Социология
Статистика
Страхование
Строительные науки
Строительство
Схемотехника
Таможенная система
Теория государства и права
Теория организации
Теплотехника
Технология
Товароведение
Транспорт
Трудовое право
Туризм
Уголовное право и процесс
Управление
Управленческие науки
Физика
Физкультура и спорт
Философия
Финансовые науки
Финансы
Фотография
Химия
Хозяйственное право
Цифровые устройства
Экологическое право
Экология
Экономика
Экономико-математическое моделирование
Экономическая география
Экономическая теория
Эргономика
Этика
Юриспруденция
Языковедение
Языкознание, филология
    Начало -> Математика -> Алгоритми Маркова

Название:Алгоритми Маркова
Просмотров:106
Раздел:Математика
Ссылка:Скачать(26 KB)
Описание: Алгоритми Маркова Зміст Вступ. 3 1. Побудова алгоритмів з алгоритмів. 4 Висновки. 8 2. Нормальні Алгоритми Маркова. Побудова алгоритмів з алгоритмів. 9 Список літератури. 13

Университетская электронная библиотека.
www.infoliolib.info

Часть полного текста документа:

Алгоритми Маркова


Зміст

Вступ. 3

1. Побудова алгоритмів з алгоритмів. 4

Висновки. 8

2. Нормальні Алгоритми Маркова. Побудова алгоритмів з алгоритмів. 9

Список літератури. 13


Вступ

В 1956 році вітчизняним математиком А.А. Марковим було запропоновано нове уточнення поняття алгоритму, яке пізніше названий його ім'ям.

В цьому уточненні виділені нами 7 параметрів були визначено таким чином:

Сукупність початкових даних - слова в алфавіті S;

Сукупність можливих результатів - слова в алфавіті W;

Сукупність можливих проміжних результатів - слова в алфавіті

Р=SWV, де V - алфавіт службових допоміжних символів.

Дії:

Дії мають вигляд або a®g, або a a g, де a, g ÎP*, де

P* - безліч слів над алфавітом Р, і називається правилом підстановки. Значення цього правила полягає в тому, що оброблюване слово w є видимим зліва направо і шукається входження в нього слова a.


1. Побудова алгоритмів з алгоритмів

Дотепер, будуючи той або інший МТ, або НАМ ми кожного разу всі робили наново. Природно задати питання, а чи не можна при побудові, наприклад, нової МТ користуватися вже побудованою раніше МТ.

Наприклад, МТ3 з прикладу 3

U3((n) 1) =(n) 10

по суті є належним чином з'єднані МТ для U1(n) =n+1 і U2((n) 1) =(n-1) 1.

Аналогічне питання можна сформулювати для НАМ. Іншими словами чи можна акумулювати знання у формі алгоритмів так, щоб з них можна було будувати інші алгоритми.

Ми розглянемо цю проблему стосовно МТ. Проте всі сформульовані нами твердження будуть справедливі і для НАМ і для інших еквівалентних уточнень поняття алгоритму. Еквівалентність уточнень поняття алгоритму ми розглянемо пізніше.

Визначення 3.2. Говоритимемо, що МТ1 можна ефективно побудувати з МТ2 і МТ3 якщо існує алгоритм, який дозволяє, маючи програму для МТ2 і МТ3, побудувати програму для МТ3.

Визначення 3.3. Послідовною композицією МТ А і В називається така МТ З, що

область застосовності МТ А і Із співпадають;

C(a) =B(A(a)).

Іншими словами, застосування З до слова a дає такий же результат, як послідовне застосування до цього ж слова спочатку А, а потім до результату застосування А - В.

Послідовну композицію МТА і МТВ позначатимемо АoВ.

Теорема 3.1. Хай дані МТ А і В, такі, що В застосовна до результатів роботи А і QAQB=Æ.

Тоді можна ефективно побудувати МТ З таку, що С= АoВ.

Доказ.

Як алфавіт даних і безлічі станів для МТС візьмемо об'єднання алфавітів даних і безлічі станів для А і В, тобто

DC=DADВ, QC= QAQB

В програмі для А всі правила ap®b! w, де a,bÎDA* wÎ{Л, П, Н} замінимо на ap®bqoBw, де qoBÎ QB - початковий стан для В. Это забезпечить включення У в той момент, коли А свою роботу закінчила і не раніше, оскільки QAQB=Æ.

Що і т.д.


Табличний запис програми для З показана на малюнку 3.3

Рис 3.3. Структура табличного запису програм для Машини З.

Означення. Паралельною композицією Машин Тюрінга А і В назвемо таку Машину З, для якої:

DC=DADB

QC=QAQB

C(a||b) =A(a||b) °B=B(a||b) °A=A(a) ||B(b).

З цього визначення видно, що порядок застосування МТА і МТВ не впливає на результат. Він буде таким же неначебто ми незалежно застосували А до слова a, а В до слова b.

Теорема 3.2 Для будь-яких МТ А і МТ В можна ефективно побудувати МТ З таку, що С=А||В

Обгрунтовування. ............





Нет комментариев.



Оставить комментарий:

Ваше Имя:
Email:
Антибот:  
Ваш комментарий:  



Похожие работы:

Название:Научная организация творческого процесса. Алгоритм решения изобретательских задач
Просмотров:91
Описание: СОДЕРЖАНИЕ   Введение Научная организация творческого процесса Алгоритм решения изобретательских задач Литература Приложения процесс творчество алгоритм изобретательство Введение Тем

Название:Построение эйлерова цикла. Алгоритм Форда и Уоршелла
Просмотров:145
Описание: БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра информатики РЕФЕРАТ на тему: «Построение эйлерова цикла. Алгоритм форда и Уоршелла»

Название:Алгоритмы планирования действий
Просмотров:85
Описание: Содержание   Введение Алгоритмы планирования действий 1. Поведение системы 2. Принятие решений в интеллектуальных играх 3. Минимаксный алгоритм 4. Альфа – бета алгоритм Заключение Использованы ист

Название:Алгоритмический язык Паскаль
Просмотров:154
Описание:МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ им. А.В. ЛУНАЧАРСКОГО КАФЕДРА ИНФОРМАТИКИДипломная работа ЧЕРЕПОВЕЦ 2010 1. ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКОВ ПРОГРАММИРО

Название:Розробка на мові асемблера алгоритму контролю на парність масиву даних
Просмотров:100
Описание: Вступ Мікропроцесори корпорації Intel і персональні комп'ютери на їх базі пройшли не дуже довгий у часі, але значний за сущністю шлях розвитку, протягом якого кардинально змінювалися їхні можливості і навіть са

 
     

Вечно с вами © MaterStudiorum.ru