АиАС - Контрольная работа: правила машины Тьюринга

Дисциплина: Алгоритмы и алгоритмическая сложность

ВУЗ: Белорусский государственный университет информатики и радиоэлектроники

Специальность: АСОИ

Готовые решения с 1-9 вариант

КОНТРОЛЬНОЕ ЗАДАНИЕ 1

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

ВАРИАНТЫ.

1. На вход поступает последовательность из 0 и 1. Машина должна записать ее в обратном порядке. Пример 0001110 заменяется на 0111000.

2. На вход поступает последовательность из 0 и 1. Машина должна заменить каждый второй 0 на 1. Пример. 000111 заменяется на 010111.

3. На вход поступает последовательность из 0 и 1. Машина должна выдать 0 если число 0-ей больше и 1 – в противном случае. Пример. 000011. Машина выдает 0.

4. На вход поступает последовательность из 0 и 1. Машина должна выдать 1, если не встречается комбинация 011 в данной последовательности и 0 – в противном случае. Пример 0001001. Машина выдает 1.

5. На вход поступает последовательность из 0 и 1. Машина должна заменить каждые два подряд идущих нуля одной единицей. Пример 00010100 заменяется на 101011.

6. На вход поступает последовательность из 0 и 1. Машина должна выдать 1, если число пар 01 четное, и 0 – если нечетное. Пример 001001 выдаем 1.

7. На вход поступает последовательность из 0 и 1. Машина должна поменять местами соседние элементы по парам. Пример. 0100101001 заменяется на 1000010110.

8. На вход поступает последовательность из 0 и 1. Машина должна заменить каждую единицу на 01. Пример. 00110010 заменяется на 00010100010.

9. На вход поступает последовательность из 0 и 1. Машина должна дописать к ней слева единицу. Пример. 011001 заменяется на 1011001 (слева появилась 1).

Не можешь написать работу сам?

Доверь её нашим специалистам