6 (Лабораторная работа №6)

Лабо ато ная абота№ био ин о матике: 8 ак льтет 1 к с 1 семест 2007/08 чебногого а Конструирование диаграмм Тьюринга Разработать диаграмму Тьюринга решения задачи с использованием стандартных машин (к, Х, и, х., К, а,. ) Вариант задания определяется преподавателем согласно выбранному студентом уровню сложности. Работоспособность диаграммы демонстрируется студентом преподавателю на Х-терминалах в среде интерпретатора 3с1с2 во время лабораторной работы либо диаграмму тестирует преподаватель (возможно во внеурочное время).

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

Определяемые заданием вычисления, как правило, должны быть нормяровпниыьчн (аргументы после работы программы сохраняются на ленте в неизменном виде и нс остается промежуточных результатов). Варианты заданий (* отмечены задачи повышенной сложности) 0 * Вычисление суммы двух двоичных чисел без знака. (Разбирается на занятии). 1 Вычисление разности двух десятичных чисел без знака, при условии, что первое число больше второго. 2 Реверс девятиричного числа со знаком (запись цифр в обратном порядке). 3 Зеркальное отражение двух десятичных слов относительно промежутка между ними.

4 Перевод числа из двоичной системы счисления в шестнадцатиричную (линейная сложность). 5 Перевод числа из шестнадцатиричной системы счисления в двоичную (линейная сложность). 6 Перевод числа из четверичной системы счисления в шестнадцатиричную (линейная сложность). 7 Перевод числа из шестнадцатиричной системы счисления в чстверичную (линейная сложность). 8 * Перевод числа из двоичной системы счисления в шестнадцатиричную (логарифмическая сложность). 9 «Перевод числа из шестнадцатиричной системы счисления в двоичную (логарифмическая сложность). 10 * Перевод числа из чегверичной системы счисления в шестнадцатиричную (логарифмическая слс жность).

11 ь Перевод числа из шестнадцатиричной системы счисления в четверичную (логарифмическая сложность). 12 *«Вычисление произведения двух неотрицательных чисел в шестнадцатиричной системе счисления. 13 Вычисление прсдиката х<у для двух чисел в алфавите (0,1,2,3,4,5,6,7,8,9,Т,Г).

14 Вычисление прсдиката делимости на 3 десятичного числа. 15 «Деление двух неотицательных десятичных чисел. 16 Я Подсчет числа различных букв слова в латинском алфавите. 17 * Вычисление прсдиката взаимной простоты двух чисел в натуральной системе счисления. 18 «Вычисление предиката «и подслово чо> в латинском алфавите. 19 Вычисление двоичного логического сдвига второго числа влево на число разрядов, равное первому. 20 Вычисление двоичного логического сдвига первого числа вправо на число разрядов, равное второму. 21 «Вычисление двоичного арифметического сдвига второго числа влево на число разрядов, равное первому.

22 «Вычисление двоичного арифметического сдвига первого числа вправо на число разрядов, равное второму. 23 * Вычисление двоичного циклического сдвига второго числа влево на число разрядов, равное первому. 24 * Вычисление двоичного циклического сдвига первого числа вправо на число разрядов, равное второму. 25 Выделение разрядов первого двоичного числа по маске„задаваемой вторым числом. 26 Вычисление поразрядной конъюнкции двух двоичных чисел (слова одинаковой длины). 27 Вычисление поразрядной дизьюнкции двух двоичных чисел (слова одинаковой длины). 28 * Вычисление поразрядной конъюнкции двух двоичных чисел (слова разной длины, дополняются 0 слева). 29 *" Вычисление поразрядной дизьюнкции двух двоичных чисел (слова разной длины, дополняются 0 слева).

30 Получение дополнительной кодировки двоичного отрицательного числа с тем же абсолютным значением. 31 Получение обратной кодировки двоичного отрицательного числа с тем же абсолютным значением. 32 Увеличение на единицу целого неотрицательного числа в шестнадцатеричной системе счисления.

(Рекурсивный вариант — «). 33 Уменьшение на единицу целого неотрицательного числа в шестнадцатеричной системе счисления. (Рекурсивный вариант — в'"). 34 Восстановление целого числа в восьмеричной системе счисления по дополнительному коду. 35 Восстановление целого числа в восьмеричной системс счисления по обратному коду.

36 Натурапизацтля двоичного числа в позиционной записи (перевод в единичную систему счисления Ц)). 37 * Натурализация двоичного числа в позиционной записи (с логарифмической сложностью). 38 Вычисление логического произведения (сссс в Си) двоичных чисел. 39 ** Вычисление наибольшего общего делителя двоичных чисел. 40 ** Вычисление наибольшего общего делителя двух чисел в десятичной системе счисления.

4 т * Вычисление наименьшего общего кратного двух чисел в десятичной системе счисления. (НО/т"(тт, п) «НОД(т, и) =т Ян) 42 в* Нахождение максимального числа в последовательности. 43 «* Натурализация числа в римской записи. 44 *" Проверка арифметической прогрессии трех десятичных чисел. 45 ** Проверка геометрической прогрессии трех десятичных чисел. 46 ««Вычисление факториала числа в троичной системе счисления. 47 """ Сокращение обыкновенных дробей в десятичной системе счисления. 48 " Возведение двоичного числа в квадрат.

Варианты составлены проф. Зайцевым В.Е., ст. преп. Дзюбой Д.В. и Сеницким П.А., доц. Сошниковым Д.В. Необходимо тренироваться в сос>навлении диаграмм Тьюринга. Этот тин задач часто встречается ка экзамене! Краткое описание диаграммера Тьюринговых вычиспений .) 0Т2 «Щелкни кобылу в нос — она махнет хвоснюлт!» Козьма Прутков ЛЭТ2 является интерактивной средой интерпретатора диаграмм Тьюринга, выполненного в виде,Тачаприложсния, функционирующего в среде виртуспьнои лтаиттт>ты тат а на х-терминалах (г>вс, 'геКггопхх и др) в ОС ВытХ, на тВМ ВС в среде МВ Ххпс(ока и даже на КПК Воспет ВС. ЛЭТ2 разработан ст. преп.

Дзюбой Д.В. под руководством проф. Зайцева В.Е. Дпя работы о т>т2 в среде мв тнхпстоттз необходимо установить ~вв (тат>а впп~хтпе впчхгопптеп~. Последняя версия твв (6, црт(а(е 2) может быть скачана отсюда Ьс(т рт //3 ат>а. сота/гп/с(отлп1оад/тпаптта1. 3 вр ). Среда ЛЭТ2 позволяет создавать многоуровневые иерархические рекурсивные()) диаграммы Тьюринга в терминах элементарных машин х, 2, лт, Х,, Х„, ат с неограниченным числом машин и связей между ними и с практически неограниченной в обе стороны лентой. Запуск Л)Т2 осуществляется командой 3 стс2 из библиотеки локальных исполнимых программ /взг/(осаИ>тв/ Данная версия программы находится в стадии опытной эксплуатации.

Существует вариант для КПК, оптимизированный под разрешение 320х240 и адаптированный под микросреду Зат>а. Кроме того, для домашних работ студенты могут использовать свободно распространяемые программы: версия >т>т для мв Хт пс(оьв 3. 1х/95/ИТ, интерпретатор диаграмм Тьюринга (>(>т (МБ ВОЯ, автор ст. преп. Дзюба Д.В.), мультимодельная система студента Рыбакова К.А. (ныне к.ф.-м.н., доцент кафедры 805) и другие аналогичные системы из с(>-хрестоматии к курсу. Для создания новой диаграммы на панели инструментов выберите стандартный значок создания нового документа (пиктограмма «белый лист»). Далее укажите имя диаграммы и рабочий алфавит. Алфавит может содержать любые знаки клавиатуры.

В качестве несобственной буквы используется пробел. Рабочее поле диаграммера состоит из четырех частей: ленты, панели стандартных машин, поля конструктора диаграмм и панели свойств текущей машины (конструируемой или исполняемой) Для добавления новой машины в диаграмму необходимо выбрать нужную машину в панели стандартных машин(внизу) и щелчком левой кнопки мыши в поле конструктора диаграмм указать положение добавляемой машины в диаграмме. Для модификации диаграммы необходимо выбрать пиктограмму-указатель в панели инструментов (вверху), после чего кликнуть редактируемый элемент диаграммы. Аналогично можно изменить множество букв, надписанных над стрелкой.

Для построения диаграммы введены служебные машины, обозначающие начало и конец диаграммы. Каждая диаграмма обязательно должна содержать только одну начальную и хотя бы одну конечную машину. Начальная машина не может иметь входящих стрелок; конечные машины не могут иметь исходящих. Для соединения двух машин необходимо: ° выбрать элемент слгрелка в панели инструментов; ° щелчками левой кнопки мыши в поле конструктора диаграмм указать начало и конец стрелки. Для вклочения в диаграмму машины записи буквы на ленту необходимо добавить в диаграмму машину записи, а затем модифицировать выбранный элемент стандартным образом.

Для изменения буквы в ячейке ленты необходимо щелчком левой кнопки мыши выбрать ячейку с буквой и ввести с клавиатуры новую букву. Для перемещения указателя головки машины Тьюринга по ленте необходимо щелчком левой кнопки мыши указать новое положение головки на ленте. Для запуска МТ, определяемой диаграммой, необходимо в панели инструментов выбрать значок запуск. Ниже приведен вид окна диаграммера с открытой рекурсивной диаграммой десятичного сложения (прилагаемой к уй2) на 1ВМ РС в среде МБ %шдовз ХР и на смартфонс ОТс1г 5110 под управлением %шйоъв МоЬ!1е 2003; ;1 ополнишельное зиданне. Настроить диаграммер какой-либо САЬЕ-системы на диаграммы Тьюринга и проделать в этой системе одно из заданий ЛР №6.

.