Казанский государственный университет

Факультет вычислительной математики и кибернетики

Кафедра теоретической кибернетики

В.С. Кугураков, Р.К. Самитов, Р.Б. Ахтямов, В.Р. Байрашева

Практикум работы на ЭВМ.

Задание 3. Представление данных и методы разработки алгоритмов.

Казань 2007.

УДК (075.8) 004.3

Кугураков Владимир Сергеевич

Самитов Ринат Касимович

Ахтямов Рауф Баграмович

Байрашева Венера Рустамовна

Практикум работы на ЭВМ. Задание 3. Представление данных и методы разработки алгоритмов. Казань: КГУ. 2007 - с.

Пособие предназначено для студентов, обучающихся по специальности «Прикладная математика и информатика» и направлению «Информационные технологии», а также для преподавателей, ведущих практические занятия по информатике, алгоритмическим языкам и программированию.

Компьютерная верстка и дизайн обложки: Ахтямова Светлана Станиславовна.

1 Т и п о в ы е з а д а ч и

1.1 Моделирование автомата

Автоматом  называется некоторое устройство, которое математически описывается тремя множествами X, Y, S и диаграммой D работы:

X = {x₁, x₂, … , x_n} – множество входных символов;

Y = {y₁, y₂, … , y_m} – множество выходных символов;

S = {s₁, s₂, … , s_k}  множество состояний.

Диаграмма строится так. Рисуется К кружков и внутри каждого из них помещается по символу из множества S. Из каждого кружка выводится n стрелок, которые доводятся до кружков (стрелка может выйти из кружка и зайти в него же, две стрелки могут соединять одну и ту же пару кружков). Около каждой стрелки пишется пара символов а/b, где а X и bY, с единственным условием: разные стрелки, выходящие из одного (любого) кружка, помечаются парами с разными символами из X. Таким образом,  = {X, Y, S, D}.

Работа автомата складывается из тактов (номер такта обозначается буквой t , t = 1, 2, 3, …). На каждом такте на вход автомата подается один из входных символов: на первом такте символ а₁ X, на втором – а₂ X и т.д. Последовательность входных символов a₁, a₂, …, a _r называется входным словом и обозначается через A. В ответ на входное слово автомат вырабатывает (на своем выходе) последовательность b₁, b₂, … , b_r символов из Y, т.е. образуется выходное слово, обозначаемое через B.

Выходное слово образуется так. Перед первым тактом автомат устанавливается в состоянии c₀ S. В общем случае – перед тактом t автомат оказался в состоянии c_t-1  S. Тогда в диаграмме находится кружок с символом c_t-1 и выходящая из него стрелка с парой, содержащей символ a_t . Второй символ из пары – это и есть выходной символ b_t , а к следующему (t + 1) – му такту автомат оказывается в том состоянии (c_t  S), к которому приводит эта стрелка.

Задание. Построить программу, моделирующую работу конкретного автомата  и решающую для этого автомата задачу М.

Исходные данные

I. Автомат :

а) X = {0, 1}, Y = {*, +, }, S = {s₁, s₂, s₃, s₄, s₅}

б) X = {+, }, Y = {0, 1, 2, 3, 4}, S = {s₁, s₂, s₃, s₄, s₅, s₆}

в) X = {,  , }, Y = {1, 4, 7}, S = {s₁, s₂, s₃}

г) X = {, }, Y = {, , , , }, S = {s₁, s₂, s₃, s₄}

д) X = {0, 1, 2, 3} , Y = {, }, S = {s₁, s₂, s₃}

е) X = {*, +, }, Y = {, }, S = {s₁, s₂, s₃, s₄}

ж) X = {0, 1}, Y = {2, 3}, S = {s₁, s₂, s₃, s₄, s₅, s₆, s₇}

з) X = {, }, Y = {,  , }, S = {s₁, s₂, s₃, s₄, s₅, s₆}

II. Задача М. При заданном начальном состоянии c₀ S и заданном входном слове A длины r определить:

а) количество символа y₁ в выходном слове B;

б) количество «подслов» вида y₁ y₂ y₂ в выходном слове B;

в) сколько раз автомат, работая, окажется в состоянии S₁ и выдаст на выходе при этом символ y ₁;

г) выдаст ли автомат на выходе символ y ₁ в такты t = 10, 20, 30 (т.е. будет ли b₁₀ = y₁  b₂₀ = y₁  b₃₀ = y₁);

д) максимальную длину подслов B , состоящих только из символа y₁ (т.е. максимальную длину повторения символа y₁);

е) тот такт, на котором автомат впервые окажется в состоянии S₂ , и выдаст при этом на выходе символ y₂ ;

ж) окажется ли автомат в своей работе хотя бы по одному разу в каждом из своих состояний и в выходном слове будут ли представлены все символы из y;

з) сколько раз каждый из символов множества y окажется в выходном слове B .

1.2. Моделирование машины Тьюринга.

Всякая машина Тьюринга M состоит из:

- ячейки с бесконечным в обе стороны числом разрядов …, x_-2 , x_-1 , x₀ , x₁ , x₂ , … В каждом разряде может быть записан один из n символов множества A = a₀, a₁, … , a_n-1, причем символ a₀ называется пустым (n  2);

- устройство, которое в каждый момент времени обозревает один из разрядов ячейки, а само может находиться в состояниях {q₀, q₁, … , q_m-1} = Q; состояние q₀ называется «стоп-состояние»;

- программы работы – это таблица из n строк и m1 столбцов. Строки соответствуют символам из множества A , столбцы – символам из Q; в каждой клетке помещен один из символов A, один из символов Q и одна из букв Л, П, Н.

Машина предназначена для переработки информации в ячейке. Переработка совершается тактами, номер такта обозначается буквой t (t = 1,2,3, …). Перед первым тактом устройство устанавливается в состояние q₁ на обозревание разряда x₀, а начальная информация записывается в ячейку так, что в разрядах x₀, x₁, … , x_k – не пустые символы, в остальных разрядах – пустой символ a₀.

В общем случае – если перед тактом t устройство оказалось в состоянии q  Q и обозревает разряд x_l , то работа одного такта сводится к следующему:

- если q = q₀, то машина останавливается и информация в ячейке считается результатом работы машины;

- если q  q₀, то берется символ a из разряда x_l и находится клетка в программе, соответствующая символу a и состоянию q, - в этой клетке три символа (a , q , R);

- в разряд x_l помещается символ a  (вместо a); устройство переходит в состояние q  и начинает обозревать разряд x_l+1 , если R = П, или x_l1, если R = Л, или x_l , если R = Н.

По завершении такта t машина автоматически переходит к выполнению действий такта t+1.

Задание. Построить программу, моделирующую работу конкретной машины Тьюринга М и решающую для этой машины задачу Г. В каждой задаче рассматривать работу машины в течение не более заданного числа Т тактов.