Машина Тьюринга для транспонирования булевых матриц

Федеральное агентство  по образованию РФ

Государственное образовательное учреждение

высшего профессионального  образования

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

Факультет прикладной математики и кибернетики

 

 

 

КУРСОВАЯ РАБОТА

По дискретной математике

Тема 9. <<Машина Тьюринга для транспонирования булевых  матриц>>

 

 

 

 

 

 

 

 

 

Выполнил:

Студент 17-группы

Шарифов Фарход Сурурриллоевич

 

 

 

Тверь 2011

Тема 9. Машина Тьюринга для транспонирования булевых матриц

А) Построить программу м.Т. для транспонирования квадратных  булевых матриц. Квадратная  n X n матрица   A =(),  , представляется перечислением строк, разделенных символов  *.

Вход  имеет вид: a₁₁a_12.... a_1n * a₂₁a₂₂ … a_2n * … * a_n1 a_n2… a_nn . Выход: транспонированная матрица  в виде:

a₁₁a_21.... a_n1 * a₁₂a₂₂ … a_n2 * … * a_1n a_2n… a_nn

Б)  Обосновать правильность построенной программы.

В)  Привести протокол вычисления программы для значения аргумента:

 А =

Г)  Оценить (по порядку) время работы программы как функцию  от размера матрицы  т .

Алгоритм построения машины Тьюринга:

Для начала, в конце слова поставим #. Вернёмся обратно до начала и возьмём первый элемент, отметим его штрихом, дойдём до первой звёздочки, его тоже отмечаем и идём направо до пустышки. Вместо пустышки поставим тот элемент, который  запоминали. Вернёмся влево до отмеченной звёздочки и идём направо, берём  первый не штрихованный элемент и доходим до первой звёздочки справа от этого элемента, а затем отмечаем эту звёздочку и идём направо до пустышки, ставим элемент, который запоминали. Когда взяли все первые элементы каждой строки, то  идём направо до конца, вставим в конец звёздочку. Наш цикл продолжаем до тех пор, пока есть не заштрихованные элементы. Когда все элементы, стоящие слева от # будут заштрихованными, то заканчиваем цикл и стираем эти элементы, потом дойдём до конца и стираем самую конечную звёздочку.

 

 

 

 

 

 

А)    a₁₁a_12.... a_1n * a₂₁a₂₂ … a_2n * … * a_n1 a_n2… a_nn

;

Поставим в конец #:

q₀1→ q₀1 П

q₀0→ q₀0 П

q₀*→ q₀* П

q₀Λ→ q₁# Л

q₁1→ q₁1 Л

q₁0→ q₁0 Л

q₁*→ q₁* Л

q₁ Λ→ q₂ Λ П

a₁₁a_12.... a_1n * a₂₁a₂₂ … a_2n * … * a_n1 a_n2… a_nn#

Составим новую строку из первых элементов каждой строки 

q₂a→ q^aa’ П,  a ∈{0,1} //запоминаем 1-ю элемент первой строки

q^a b→ q^ab П, b ∈{0,1} //пропускаем любую букву до первой * 

q^a *→ q₁^a *’ П   //отметим 1-ю * штрихом *’

q₁^a b→ q₁^a b П, b ∈{0,1}  

q₁^a *→ q₁^a * П

q₁^a # → q₁^a # П

q₁^a Λ → q₃a Л, a ∈{0,1} //дошли до Λ, поставим на её место элемент который запомнили и вернёмся до *’

q₃b→ q₃b Л

q₃# → q₃# Л

q₃* → q₃* Л

q₃*’ → q₂*’ П   

q₂a’ → q₂a’ П, a ∈{0,1}

q₂b → q₂b П,  b ∈{0,1}

после того как получили очередную  строку транспонированной матрицы  поставим * в её конец

q₂# → q₄# П

q₄b → q₄b П, b ∈{0,1}

q₄* → q₄* П

q₄ Λ → q₅* Л  //поставили *, вернёмся к самому началу

и по пути расштрихуем все *’

q₅b → q₅b Л, b ∈{0,1}

q₅* → q₅* Л

q₅# → q₅# Л

q₅a’ → q₅a’ Л,  a ∈{0,1}

q₅*’ → q₅* Л

q₅ Λ → q₆ Λ П

q₆b’ → q₆b’ П, b ∈{0,1} //пропускаем все b’ и берём 1-й b и

q₆a → q^aa’ П, a ∈{0,1} // заново входим в цикл (q^a)

q₆* → q₆* П

q₆# → q₇Λ Л   //стираем # и ВСЁ что слева от него

q₇a → q₇Λ Л, a ∈{0,1}

q₇b’ → q₇Λ Л, b ∈{0,1}

q₇* → q₇Λ Л

q₇Λ → q₇Λ П

q₇ a → q₈ a П, a ∈{0,1}

q₈ a → q₈ a П , a ∈{0,1} 

q₈ * → q₈ * П

q₈ Λ → q₉ Λ Л   //дойдём до конца, «шаг налево» и сотрём (последнюю) *

q₉ * → q_f Λ Н   //КОНЕЦ РАБОТЫ ПРОГРАММЫ

 

Б)   a₁₁a_12.... a_1n * a₂₁a₂₂ … a_2n * … * a_n1 a_n2… a_nn # a₁₁a_21.... a_n1 * *a₁₂a₂₂ … a_n2 * … * a_1n a_2n… a_nn

  Wq₂ … * … … * ... * … … # u W … … … * … * … … #u

В)

                                                               

                                                             

                                                             

                                                      

                                                       

                                                        

                                                        

                                                        

                                                  

 

                                                        

                                                        

                                                        

                                              

                                 

                               

Г) N = n²+n+1  - длина слова

       Поставить # : 0(N)

      Число итераций: n x n= 0(N)

       Cтереть: 0(N)

Время :0(N x N)= 0(N²);