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 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
1. Для записи алгоритмов используют несколько словесный
графический
программный
Словесный – это записи алгоритма на естественном языке, но с тщательно отработанным набором слов и фраз, не допускающих повторений, синонимов, двусмысленности, лишних слов. Допускается использование математических символов. При графическом описания алгоритма осуществляется с блок-схем. Программный это запись алгоритма на языке программирования (в виде компьютерной программы).
2. Налить 9 литров. Перелить в другое ведро 5 литров. В 9-ти литровом останется 4 литра. Из 5-ти литрового вылить воду. Перелить из 9-ти литрового оставшиеся 4 литра в 5-ти литровое ведро. Наполнить 9-ти литровое ведро водой. Перелить в 5-ти литровое ведро 1 литр (больше в 5-ти литровое не влезет). Из 5-ти литрового вылить воду. В 9-ти литровом останется 8 литров. Перелить в 5-ти литровое ведро. ИТОГ: в 9-ти литровом останется 3 литра.
3. Прямоугольник - блок вычислений
Ромб - условие
Параллелограмм - блок ввода-вывода данных
овал - начало и конец алгоритма
Стрелки, соединяющие эти фигуры, и задают порядок выполнения действий.
Размер предложения 67символа*16 бит =1072бит(4)