Создание имитационных моделей абстрактных автоматов Тьюринга и Маркова
Изучение программа машины Тьюринга. Рассмотрение записи программы прибавления единицы к двоичному числу. Описание нормальных алгоритмов Маркова - непустого конечного упорядоченного набора формул подстановки. Исследование функции просмотра и ссылок.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | методичка |
Язык | русский |
Дата добавления | 11.04.2023 |
Размер файла | 1,5 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
36. Пусть P имеет вид Q>R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.
Задачи для самостоятельного решения по НАМ
Замечания:
В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.
Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа; например: 2>| | , 5 >| | | | | , 0 ><пустое слово>.
1.A={f,h,p}. В слове P заменить все пары ph на f.
2.A={f,h,p}. В слове P заменить на f только первую пару ph, если такая есть.
3. A={ | }. Считая слово Р записью положительного числа в единичной системе счисления, уменьшить это число на 1.
4. A={ | }. Считая слово Р записью числа в единичной системе счисления, увеличить это число на 2.
5. A={a,b,c}. Определить, входит ли символ а в слово Р. Ответ (выходное слово): слово а, если входит, или пустое слово, если не входит.
6. A={a,b}. Если в слово Р входит больше символов а, чем символов b, то в качестве ответа выдать слово из одного символа а, если в Р равное количество а и b, то в качестве ответа выдать пустое слово, а иначе выдать ответ b.
7. A={0,1,2,3}. Преобразовать слово Р так, чтобы сначала шли все чётные цифры (0 и 2), а затем - все нечётные.
8. A={a,b,c}. Преобразовать слово Р так, чтобы сначала шли все символы а, затем - все символы b и в конце - все символы с.
A={a,b,c}. Определить, из скольких различных символов составлено слово Р; ответ получить в единичной системе счисления (например: асаас > | | ).
9. A={a,b,c}. В непустом слове Р удвоить первый символ, т.е. приписать этот символ слева к Р.
10. A={a,b,c}. За первым символом непустого слова Р вставить символ с.
11. A={a,b,c}. Из слова Р удалить второй символ, если такой есть.
12. A={a,b,c}. Если в слове Р не менее двух символов, то переставить два первых символа.
13. A={0,1,2}. Считая непустое слово Р записью троичного числа, удалить из этой записи все незначащие нули.
14. A={a,b,c}. Удалить из непустого слова Р его последний символ.
15. A={a,b}. В слове Р все символы а заменить на b, а все (прежние) символы b - на а.
16. A={a,b,c}. Удвоить каждый символ в слове P (например: bacb > bbaaccbb).
17. A={a,b}. Приписать справа к слову P столько палочек, сколько всего символов входит в P (например: babb > babb ||||).
18. A={a,b}. Пусть слово P имеет чётную длину (0, 2, 4, _). Удалить правую половину этого слова. (Рекомендация: использовать решение предыдущей задачи.)
19. A={a,b}. Пусть длина слова P кратна 3. Удалить правую треть этого слова.
20. A={a,b}. Приписать справа к слову P столько палочек, со скольких подряд идущих символов a начинается это слово (например: aababa >aababa| | ).
21. A={a,b,c}. Удалить из слова P второе вхождение символа a, если такое есть.
22. A={a,b,c}. Удалить из слова P третье вхождение символа a, если такое есть.
23. A={a,b,c}. Оставить в слове P только первое вхождение символа a, если такое есть.
24. A={a,b}. Если слово P содержит одновременно символы a и b, то заменить P на пустое слово.
25. A={a,b,c}. Если буквы в непустом слове P не упорядочены по алфавиту, то заменить P на пустое слово, а иначе P не менять.
26. A={a,b,c}. Если P отлично от слова abaca, то заменить его на пустое слово.
27. A={0,1,2,3}. Считая непустое слово P записью четверичного числа, проверить, чётно оно или нет. Ответ: слово 0, если чётно, и слово 1 иначе.
28. A={0,1,2}. Считая непустое слово P записью троичного числа, увеличить это число на 1.
29. A={0,1,2}. Считая непустое слово P записью положительного троичного числа, уменьшить это число на 1.
30. A={ | }. Считая слово P записью числа в единичной системе счисления, получить запись этого числа в троичной системе. (Рекомендация: следует в цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к троичному числу, которое вначале положить равным 0.)
31. A={0,1,2}. Считая непустое слово Р записью числа в троичной системе, получить запись этого числа в единичной системе.
32. A={a,b,c}. Определить, входит ли первый символ непустого слова Р ещё раз в это слово. Ответ: слово а, если входит, или пустое слово иначе.
33. A={a,b}. Перенести первый символ непустого слова Р в конец слова.
34. A={a,b}. Перенести последний символ непустого слова Р в начало слова.
35. A={a,b}. В непустом слове Р переставить первый и последний символы.
36. A={a,b}. Если в непустом слове Р совпадают первый и последний символы, то удалить оба этих символа, а иначе слово не менять.
37. A={a,b}. Определить, является ли слово Р палиндромом (перевёртышем, симметричным словом). Ответ: слово а, если является, или пустое слово иначе.
38. A={a,b}. Пусть слово Р имеет нечётную длину. Удалить из него средний символ.
39. A={ | }. Считая слово Р записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27,…). Ответ: пустое слово, если является, или слово из одной палочки иначе.
40. A={ | }. Считая слово Р записью числа n в единичной системе, получить в этой же системе число 2n.
41.A={ | }. Пусть слово Р является записью числа 2n (n=0, 1, 2, в единичной системе. Получить в этой же системе число n.
42. A={a,b}. Перевернуть слово P (например: abb > bba).
43. Пусть P имеет вид Q=R, где Q и R - любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.
44. Пусть P имеет вид Q=R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.
45. Пусть P имеет вид Q>R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.
Рекомендуемая литература
1. Н.Т.Когабаев, Лекции по теории алгоритмов. учебное пособие-Новосибирск, Издательство Новосибирского государственного университета, 2009г - 107с.
2. Л.В.Рудикова, Microsoft Word для студента- Санкт-Петербург, Издательство БХВ,2011- 400с.
3. И.Пащенко, Word 2007 (Шаг за шагом).- Санкт-Петербург, Издательство Питер,2008- 464с.
4. З.В.Алферова, Теория алгоритмов - Москва,Издательство “Статистика”, 1973г-137с.
5. В.С. Пташинский, Самоучитель Office 2013- Москва, Издательство Эксмо, 2013. - 288с.
6. О.В.Спиридонов, Microsoft Office для пользователя- Москва, Издательство Эксмо, 2013- 350с.
7. Н.В.Макарова, В.Б. Волков, Информатика - Санкт-Петербург, Издательство Питер, 2011- 576с.
8. Г.Н.Хубаев, С.М. Патрушина, Н.Г. Савельева, Е.Г. Веретенникова, Информатика- Ростов-на-Дону, Издательство Феникс, 2010- 288с.
9. Ю.И.Кудинов, Ф.Ф. Пащенко, А.Ю. Келина, Практикум по основам современной информатики - Санкт-Петербург, Издательство Лань, 2011- 352 с.
10. Ю.И. Кудинов ,Ф.Ф. Пащенко, Основы современной информатики- Санкт-Петербург, Издательство Лань , 2011- 256 с.
11.А.В. Гураков, Информатика. Введение в Microsoft Office -Томск, издательство Эль Контент, 2012- 120с.
12. А.С.Грошев, Информатика. учебник для вузов - Архангельск, издательство Архангельского государственного технического университета,2010-470с.
13. Э.З. Любимский, В.В. Мартынюк, Н.П. Трифонов. Программирование. - М., "Наука", 1980.
14. Л.С. Корухова, М.Р. Шура-Бура. Введение в алгоритмы (учебное пособие для студентов 1 курса) - М., Издательский отдел факультета ВМК МГУ, 1997.
15. А. А. Марков, Н.М. Нагорный. Теория алгоритмов. - М., ФАЗИС, 1996.
Учебное издание
Создание имитационных моделей абстрактных автоматов Тьюринга и Маркова
Учебно-методическое пособие по выполнению лабораторной работы № 1 и №2 по дисциплине «Информатика» для направления 11.03.03 «Конструирование и технология электронных средств» по профилю «Проектирование и технология радиоэлектронных средств»
Составители: Шамсиахметов Олег Явзатович
Подписано в печать _______. Усл. печ. л. ______. Тираж _____ экз. Заказ № _____
Издательство Ижевского государственного технического университета имени М. Т. Калашникова
Отпечатано в типографии Издательства ИжГТУ. 426069, Ижевск, Студенческая, 7
Размещено на Allbest.ru
...Подобные документы
Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.
курсовая работа [1,5 M], добавлен 07.07.2013Нормальный алгоритм Маркова. Тезис Маркова и машина Тьюринга. Гипотеза теории алгоритмов. Алгоритмически неразрешимые проблемы. Задача эквивалентности двух слов в ассоциативном исчислении. Задача распознавания выводимости. Линейная оценка сложности.
методичка [57,0 K], добавлен 06.07.2009Принципы работы и основы программирования машины Тьюринга, а также перечень правил написания алгоритмов на ее эмуляторе. Особенности решения задачи по сложению нескольких чисел в двоичной системе путем реализации ее алгоритма на эмуляторе машины Тьюринга.
контрольная работа [82,4 K], добавлен 05.12.2010Простое вычислительное устройство машина Тьюринга и ее алгоритмические свойства. Тезис Черча–Тьюринга и моделирование машины Тьюринга (операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке с учетом изменения состояния машины).
контрольная работа [23,3 K], добавлен 24.04.2009Изучение методик языка Javascript по формализации и решению поставленной задачи, технологических приемов разработки программ на языке Javascript, HTML, CSS. Формально определение машины Тьюринга, распознающую язык. Ее программная модель, протоколы работы.
курсовая работа [220,7 K], добавлен 03.03.2015Методика разработки программы, предназначенной для разбора предложения с помощью многоленточной машины Тьюринга. Цели и назначение данной системы, основные требования, предъявляемые к ней. Организационно-исполнительные работы по содержанию системы.
курсовая работа [386,8 K], добавлен 16.12.2010Положения машины Тьюринга. Алгоритмически неразрешимые проблемы: "остановка", эквивалентность алгоритмов, тотальность. Свойства алгоритма: дискретность, детерминированность, результативность, массовость. Выбор структуры данных. Решение на языке Haskell.
курсовая работа [957,6 K], добавлен 16.11.2013Примеры запросов к одной из поисковых систем Интернет (подбор ключевых слов) и расчетов в табличном процессоре MS Excel (инструменты). Описание машины Тьюринга: составляющие и их функционирование. Основные форматы представления графических данных.
контрольная работа [24,5 K], добавлен 09.06.2009Происхождение и сущность понятия "алгоритм". Основные требования к алгоритмам. Роль абстрактных алгоритмических систем. Алгоритм как абстрактная машина. Алгоритмическая машина Поста. Схема логического устройства и функционирования машины Тьюринга.
реферат [62,2 K], добавлен 16.03.2011А.М. Тьюринг как английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики. Понятие и назначение машины Тьюринга, принцип ее работы и сферы практического применения. Этапы реализации парадигмы программирования.
реферат [8,1 K], добавлен 04.10.2011Синтез и детерминизация, алгоритм минимизации автоматов–распознавателей. Машина Тьюринга как универсальный тип абстрактного преобразователя. Моделирование систем и событий с помощью сетей Петри. Методы синтеза структурных автоматов на базе триггеров.
учебное пособие [2,3 M], добавлен 17.06.2014Более строгое описание алгоритма, чем общее или формализация понятия алгоритма. Три подхода к формализации: теория конечных и бесконечных автоматов, теория вычислимых (рекурсивных) функций и л-исчисление Черча. Воображаемые машины Поста и Тьюринга.
реферат [370,0 K], добавлен 09.02.2009Автоматизация технологических процессов. Написание имитационных моделей систем с дискретными событиями. Модели систем массового обслуживания в общецелевой системе GPSS. Логическая схема алгоритмов и схема программы. Математическая модель и ее описание.
курсовая работа [1,4 M], добавлен 29.06.2011История возникновения и развития понятия "машинный интеллект". Суть теста Тьюринга, разработанного для оценки интеллекта машины. Принцип функционирования машины для решения головоломки из восьми фишек. Состояние распознавание образа, мышления, анализа.
презентация [479,6 K], добавлен 14.10.2013Исследование алгоритмов и характеристик существующих программных систем аналогов для проверки знаний: Aму Life Test Gold, SunRav TestOfficePro. Разработка архитектуры программной системы. Проверка программы в нормальных условиях, руководство пользователя.
курсовая работа [2,5 M], добавлен 17.06.2012Изучение условий поставленной задачи и используемых данных для разработки программы хранения информации о рейсах поезда. Описание разработанных функций, листинга, блок-схем алгоритмов и дерева функции. Рассмотрение сценария диалога данной программы.
курсовая работа [532,7 K], добавлен 20.07.2014Информационная система предприятия. Создание программы средствами Delphi 7 для обработки информации от пользователя и выдачи конечного результата для просмотра. Выбор программных и аппаратных средств. Методика расчета стоимости изготовления изделия.
отчет по практике [237,1 K], добавлен 05.03.2013Написание программы на языке Delphi - создание электронной записной книжки. Описание типов "запись", полей и массива, составление процедур. Создание приветствия и редактирование записи. Создание команды для вызова справки. Принцип работы программы.
контрольная работа [17,9 K], добавлен 23.09.2010Существующие альтернативы программы. Описание формул для выкроек, используемых в разработке. Описание разрабатываемой программы, а также структура ее интерфейса. Детальное описание возможностей и спецификация, функциональные особенности программы.
курсовая работа [427,4 K], добавлен 10.10.2015Создание программы "Телефонный справочник": загрузка телефонной книги; разработка алгоритмов добавления, редактирования, удаления записи; поиск по различным параметрам, вывод данных на печать. Интерфейс пользователя, системные требования и ограничения.
курсовая работа [1,5 M], добавлен 24.09.2012