Информатика ← ЛабораторныеЛабораторная работа №6

Конструирование диаграмм Тьюринга

Задание

Разработать диаграмму Тьюринга решения задачи в среде интерпретатора jdt или VisualTuring 2.0 с использованием стандартных машин (r, l, R, L, Kn, ai) и вспомогательных машин, определяемых поставленной задачей.

Работспособность диаграммы демонстрируется студентом преподавателю в ОС Unix на X-терминалах или рабочих станциях на предварительно согласнованных тестах. В сдаваемом отчете в пункте «Идея, алгоритм, блок-схема» необходимо начертить иерархический (или рекурсивный) вариант диаграммы с использованием нестандартных вспомогательных машин, если это представляется целесообразным по характеру решаемой задачи. ИСпользование одного из диаграммеров при выполнении задания обязательно, причем на отличную оценку, как правило, принимаются иерархические диаграммы со вспомогательными машнами. Распечатанное изображение отлаженной и оттестированной в соответствующей среде машиной диаграммы, скрепленное подписью преподавателя, помещается в отчет как протокол.

Алфавит диаграммы определяется заданием. В начальном состоянии головка МТ, определяемой диаграммой, находится на пустой ячейке непосредственно справа от записанных на ленте аргументов. В конечном состоянии головка МТ должна находиться на пустой ячейке непосредственно справа от результата (последнего преобразованного или вновь сформированного слова). Определяемые заданием вычисления должны быть нормированными (аргументы после работы программы сохраняются на ленте в неизменно виде и не отсается промежуточных результатов).

Варианты заданий

(Звездочкой отмечены задачи повышенной сложности.)

  1. Вычисление разности двух десятичных чисел без знака, при условии, что первое число больше второго.
  2. Реверс девятиричного числа со знаком (запись цифр в обратном порядке).
  3. Зеркальное отражение двух десятичных слов относительно промежутка между ними.
  4. Перевод числа из двоичной системы счичсления в шестнадцатиричную (линейная сложность).
  5. Перевод числа из шестнадцатиричной системы счисления в двоичную (линейная сложность).
  6. Перевод числа из четверичной системы счисления в шестнадцатиричную (линейная лсожность).
  7. Перевод числа из шестнадцатиричной системы счисления в четверичную (линейная сложность).
  8. *Перевод числа из двоичной системы счисления в шестнадцатирчную (логарифмическая сложность).
  9. *Перевод числа из шестнадцатиричной системы счилсения в двоичную (логарифмическая сложность).
  10. *Перевод числа из четверичной системы счисления шестнадцатиричную (логарифмическая сложность).
  11. *Перевод числа из шестнадцатиричной системы счисления в четверичную (логарифмическая сложность).
  12. **Вычисление произведения двух неотрицательных чисел в шестнадцатиричной системе счисления.
  13. Вычисление предиката x < y для двух чисел в алфавите {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
  14. Вычисление предиката делимости на 3 десятичного числа.
  15. *Деление двух неотрицательных десятичных чисел.
  16. *Подсчет числа различных букв слова в латинском алфавите.
  17. *Вычисление предиката взаимной простоты двух чисел в натуральной системе счисления.
  18. *Вычисление предиката «u подслово w» в латинском алфавите.
  19. Вычисление двоичного логического сдвига второго числа влево на число разрядов, равное первому.
  20. Вычисление двоичного логического сдвига первого числа вправо на число разрядов, равное второму.
  21. *Вычисление двоичного арифметического сдвига второго числа влево на число разрядов, равное первому.
  22. *Вычисление двоичного арифмечтического сдвига первого числа вправо на число разрядов, равное второму.
  23. *Вычисление двоичного циклического сдвига второго числа влево на число разрядов, равное первому.
  24. *Вычисление двоичного циклического сдвига певрого числа вправо на число разрядов, равное второму.
  25. Выделение разрядов первого двоичного числа по маске, задаваемой вторым числом.
  26. Вычисление поразрядной конъюнкции двух двоичных чисел (слова одинаковой длины).
  27. Вычисление поразряюной дизъюнкции двух двоичных числе (слова одинаковой длины).
  28. *Вычисление поразрядной конъюнкции двух двиочных чисел (слова разной длины, дополняются 0 слева).
  29. *Вычисление поразрядной дизъюнкции двух двоичных чисел (слова разной длины, дополняются 0 слева).
  30. Получение дополнительной кодировки двоичного отрицательного числа с тем же абсолютным значением.
  31. Получение обратной кодировки двоичного отрицательного числа с тем же абсолютным значением.
  32. Увеличение на единицу целого неотрицательного числа в шестнадцатеричной системе счисления. (Рекурсивный вариант — *.)
  33. Уменьшение на единицу целого не отрицательного числа в шестнадцатеричной сисетме счисления. (Рекурсивный вариант — **.)
  34. Восстановление целого числа в восьмеричной системе счисления по дополнительному коду.
  35. Восстановление целого числа в восьмеричной системе счисления по обратному коду.
  36. Натурализация двоичного числа в позиционной записи (перевод в единичную систему счисления {|}).
  37. *Натурализация двоичного числа в позиционной записи (с логарифмической сложностью).
  38. Вычисление логического произведения (&& в Си) двоичных чисел.
  39. **Вычисление наибольшего общего делителя двоичных чисел.
  40. **Вычисление наибольшего общего делителя двух чисел в десятичной системе счисления.
  41. **Вычисление наименьшего общего кратного двух чисел в десятичной системе счисления. (Подсказка: НОК(m, n) * НОД(m, n) = m * n.)
  42. **Нахождение максимального числа в последовательности.
  43. **Натурализация числап в римской записи.
  44. *Проверка арифметической прогрессии трех десятичных чисел.
  45. **Проверка геометрической прогрессии трех десятичных чисел.
  46. **Вычисление факториала числа в троичной системе счисления.
  47. **Сокращение обыкновенных дробей в десятичной системе счисления.
  48. *Возведение двоичного числа в квадрат.

Ссылки

Оригинальный текст лабораторной