Задания для самостоятельных работ

Задание 1. Пусть дана последовательность из 10 элементов 8,5,6,6,5,5,4,1,2,3. Отсортировать данную последовательность методом сортировки выбора.

Задание 2. Пусть дана последовательность из 10 элементов 7,5,6,1,5,5,4,1,2,3. Отсортировать данную последовательность методом пузырька.

Задание 3. Пусть дана последовательность из 8 элементов 10,6,4,9,2,4,3,8 Отсортировать данную последовательность методом пузырька.

Контрольные вопросы:

1. Что такое сортировка?

2. Какие алгоритмы сортировки вы знаете?

3. В чем суть метода пузырька?

Практическое занятие 6. Построение машины Тьюринга

Цель: приобрести навыки построения машины Тьюринга

Задание 1. Пусть A={0, 1, _}. На ленте в ячейках находятся символы из алфавита в следующем порядке 0011011. каретка находится над первым символом. Необходимо составить программу, которая заменит 0 на 1, 1 на 0 и вернет каретку в первоначальное положение.

Методика выполнения задания 1

Теперь определимся с состояниями каретки. Я называю их — «желания каретки что-то сделать».

q1) Каретка должна пойти вправо: если видит 0 меняет его на 1 и остается в состоянии q1, если видит 1 — меняет его на 0 и остается в состоянии q1, если видит _ — ворачивается назад на 1 ячейку «желает что-то другое», т.е переходит в состояние q2. Запишем наши рассуждения в таблицу исполнителя. Синтаксис смотрите в справке к программе)

q2) Теперь опишем «желание каретки» q2. Мы должны вернуться в первоначальное положение. Для этого: если видим 1 оставляем ее и остаемся в состоянии q2 (с тем же желанием дойти до конца ряда символов); если видим 0 — оставляем его и продолжаем двигаться влево в состоянии q2; видим _ — сдвигается вправо на 1 ячейку. Вот вы оказались там, где требуется в условии задачи. переходим в состояние q0.

Задание 2. Дано: конечная последовательность 0 и 1 (001101011101). Необходимо выписать их после данной последовательности, через пустую ячейку, а в данной последовательности заменить их на 0. Например:

Методика выполнения задания 2

Из 001101011101 получим 000000000000 1111111.

Как видите, семь единиц записались после данной последовательности, а на их местах стоят нолики.

Приступим к рассуждениям. Определим, какие состояния необходимы каретке и сколько.

q1) увидел 1 — исправь на нолик и перейди в другое состояние q2 (новое состояние вводится, чтобы каретка не поменяла на нули все единицы за один проход)

q2) ничего не менять, двигаться к концу последовательности

q3) как только каретка увидела пустую ячейку, она делает шаг вправо и рисует единичку, если она видит единичку — то движется дальше, чтобы подписать символ в конце. Как только нарисовал единицу, переходим в состояние q4

q4) проходим по написанным единицам, ничего не меняя. Как только доходим до пустой ячейки, разделяющей последовательность от единиц, переходим с новое состояние q5

q5) в этом состоянии идем начало последовательности, ничего не меняя. Доходим до пустой ячейки, разворачиваемся и переходим в состояние q1

Состояние q0 каретка примет в том случае, когда она пройдет в состоянии q1 до конца данной последовательности и встретит пустую ячейку.

Получим такую программу:

Задачи для самостоятельного решения

Задание 3.

Машина Тьюринга состоит из бесконечной ленты и головки, которая перемещается относительно ленты, стирает символы, ставит новые символы. Напишите программу, моделирующую работу машины Тьюринга, которая увеличивает заданное число на 2.

Задание 4.

Напишите программу для МТ, складывающую два целых числа, заданных набором единиц.

Задание 5.

На ленте МТ - конечный набор единиц: _11111__. Напишите программу, которая ставит звездочки вместо первой и последней единицы, остальные стирает.

Задание 6.

На ленте МТ - конечный набор единиц: _111111__. Напишите программу, которая заменяет единицы звездочками. Головка - левее первой единицы.

Задание 7.

На ленте МТ - последовательность _ABBAABAB____. Головка МТ - напротив левого символа. Напишите программу, чтобы МТ группировала символы "A" в правой части строки, а вместо них ставила звездочки.

Контрольные вопросы:

1. Устройство машины Тьюринга.

2. Система команд машины Тьюринга.

3. Алфавит машины Тьюринга.

4. Варианты окончания выполнения программы на машине Тьюринга.

Практическое занятие 7. Построение машины Поста

Цель: изучить программу имитатор машины Поста. Выработать навык составления алгоритмов для машины Поста.

Не нашли, что искали? Воспользуйтесь поиском: