1. На ленте машины Тьюринга содержится последовательностью символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.
Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.
Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
6. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
Задание 5:
ответ:64=2^6 ---> 6 битов для кодировки одного ученика 72:6 = 12 учеников отобрано
Задание 6:
91 : 13 = 7 бит- на один файл
2^7 = 128 файлов- было
128 – 13 = 115 файлов- осталось
ответ: 115
Задание 7:По формуле Хартли N= 2^{i} вспоминаем степени двойки.
2⁵ = 32 => 1 буква несет 5 бит информации, ибо i = 5. Т.к в слове муравей 7 букв, то сообщение содержит 7 * 5 = 35 бит.
Задание 8:Решение:
i-?,
Число возможных информационных сообщений о положении крестика равно количеству клеток, т.е. 8*8=64, поэтому
N=2i , 64=2i, 2^6=2i, i=6.
ответ: 6 бит.
Задание 9:1) 2^5 = 32, поэтому на 1 букву 5 бит
2) 5 бит ∙ 5 букв = 25 бит, значит 25 вопросов
ответ: 25 вопросов