Создание имитационных моделей абстрактных автоматов Тьюринга и Маркова

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 в единичной системе, получить в этой же системе число 2ⁿ.

41.A={ | }. Пусть слово Р является записью числа 2ⁿ (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