|
АиАС - Контрольная работа: правила машины Тьюринга
| |||
|
Дисциплина: Алгоритмы и алгоритмическая сложность ВУЗ: Белорусский государственный университет информатики и радиоэлектроники Специальность: АСОИ Готовые решения с 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).
| |||