Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Построение аналитических моделей алгоритмов и оценка их сложности

Построение аналитических моделей алгоритмов и оценка их сложности

Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 07.07.2013
Размер файла 1,5 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Страница:

Размещено на http://www.allbest.ru/

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

по курсу: «Дискретные структуры»

на тему: «Построение аналитических моделей алгоритмов и оценка их сложности»

РЕФЕРАТ

Отчет по курсовой работе содержит: 55 страниц, 21 рисунков, 4 таблиц, 5 приложения, 3 источника.

Объект исследования - рекурсивные функции, машины Тьюринга, нормальные алгоритмы Маркова.

Цель - сформировать формальное определение алгоритма в виде трех аналитических моделей, написать программную реализацию машины Тьюринга, распознающей язык L = { wwRwR¦w {0,1}* }, построить график временной сложности.

Результат - формальное определение алгоритмов на основе рекурсивных функций, машин Тьюринга и нормальных алгоритмов Маркова, программная реализация машины Тьюринга, распознающей язык L = { wwRwR ¦w {0,1}* }, график временной сложности машины Тьюринга, файловый вариант протокола работы машины Тьюринга.

МАШИНА ТЬЮРИНГА, ВРЕМЕННАЯ СЛОЖНОСТЬ, АЛФАВИТ, ЛЕНТА, ЯЗЫК, РАСПОЗНАВАНИЕ, АНАЛИТИЧЕСКАЯ МОДЕЛЬ, ПРИНАДЛЕЖНОСТЬ

СОДЕРЖАНИЕ

Введение

1. Описание формальной модели алгоритма на основе рекурсивных функций

2 Описание аналитической модели алгоритма в виде элементарных машин Тьюринга и композиции МТ

3. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга

3.1 Формальное определение распознающей машины Тьюринга

3.2 Протоколы работы машины Тьюринга (на двух словах языка и двух словах, не принадлежащих языку)

3.3 Программная модель машины Тьюринга

3.4 Протоколы работы машины Тьюринга, построенные программно (на двух словах языка и двух словах, не принадлежащих языку).

3.5 Расчет временной сложности (график функции временной сложности)

4. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова

Выводы

Перечень ссылок

Приложение А Техническое задание

Приложение Б Руководство пользователя

Приложение В Протоколы работы машины Тьюринга, построенные программно

Приложение Д Исходный код программы

Приложение Е Экранные формы

ВВЕДЕНИЕ

Первым дошедшим до нас алгоритмом в его интуитивном понимании - конечной последовательности элементарных действий, решающих поставленную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). В течение длительного времени, вплоть до начала XX века само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других математических задач использовалось слово «метод».

Начальной точкой отсчета современной теории алгоритмов можно считать работу немецкого математика Курта Гёделя (1931 год - теорема о неполноте символических логик), в которой было показано, что некоторые математические проблемы не могут быть решены алгоритмами из некоторого класса. Общность результата Геделя связана с тем, совпадает ли использованный им класс алгоритмов с классом всех (в интуитивном смысле) алгоритмов. Эта работа дала толчок к поиску и анализу различных формализаций алгоритма.

Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы Аланом Тьюрингом, Алонзо Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Черча были эквивалентными формализмами алгоритма. Сформулированные ими тезисы (Поста и Черча-Тьюринга) постулировали эквивалентность предложенных ими формальных систем и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство алгоритмически неразрешимых проблем. [1]

1. ОПИСАНИЕ ФОРМАЛЬНОЙ МОДЕЛИ АЛГОРИТМА НА ОСНОВЕ РЕКУРСИВНЫХ ФУНКЦИЙ

Исторически первой алгоритмической системой была система, основанная на использовании конструктивно определяемых арифметических (целочисленных) функций, получивших специальное название рекурсивных функций. Рекурсией называется способ задания функции, при котором значение определяемой функции для произвольных значений аргументов выражается известным образом через значения определяемой функции для меньших значений аргументов [2].

Задание: разработать алгоритм функции f(n), который находит ближайшее к n простое число.

Для начала нужно определить формулу для проверки числа на признак простоты. Для этого была выведена формула (1.1).

Поиск ближайшего числа состоит из трех частей: нахождения ближайшего простого, которое меньше заданного числа, нахождения ближайшего простого числа, большего заданного, и сравнения найденных чисел. Для реализации первой части поиска была выведена формула (1.2):

Функция нахождения ближайшего простого числа сверху описывается формулой (1.3):

Наконец, функция, находящая ближайшее простое число к числу n приведена на рисунке 1.1:

Рисунок 1.1 - Ближайшее к n простое число

На рисунке 1.2 приведен пример работы алгоритма в частном случае, когда n=0.

n=0

0-не простое и не составное

(0)=1

Рисунок 1.2 - Частный случай решения (n=0)

На рисунке 1.3 приведен пример работы алгоритма, когда n=1.

n=1

( [;

;

Рисунок 1.3 -Частный случай решения (n=1)

На рисунке 1.4 приведен пример работы алгоритма, если на вход подается число, которого ближайшие числа (сверху и снизу) находятся на одном и том же расстоянии от исходного числа.

Рисунок 1.4 - Результат работы алгоритма (n=21)

Функция сравнения написана таким образом, что если расстояние до двух простых чисел одинаковое, то всегда выбирается простое, которое меньше заданного числа.

Если на вход будет подано сразу простое число, то оно и будет результатом работы алгоритма.

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

2. ОПИСАНИЕ АНАЛИТИЧЕСКОЙ МОДЕЛИ АЛГОРИТМА В ВИДЕ ЭЛЕМЕНТАРНЫХ МАШИН ТЬЮРИНГА И КОМПОЗИЦИИ МТ

Задание: реализовать выделение подстроки, заключенной между двумя символами (первая пара) в алфавите . Если последовательность отсутствует на ленте, стереть все.

Опишем работу машины Тьюринга тремя способами:

а) системой команд;

б) функциональной таблицей;

в) графом (диаграммой) переходов.

В таблице 2.1 представлена функциональная таблица, в которой записаны переходы между состояниями машины Тьюринга, выполняющей поставленную задачу.

Таблица 2.1 - Функциональная таблица

a

b

*

0

1

=

л

q0

q0aR

q0bR

q0*R

-

-

-

q1=L

q1

q1aL

q1bL

q1*L

-

-

-

q2 лR

q2

q2aR

q2bR

q3*R

-

-

q8=L

-

q3

q40R

q71R

q9*L

q3aL

q3bL

q8=L

-

q4

q4aR

q4bR

q5*R

-

-

-

-

q5

q5aR

q5bR

q5*R

-

-

q5=R

q6aL

q6

q6aL

q6bL

q6*L

q30R

q31R

q6=L

-

q7

q7aR

q7bR

q7*L

-

-

q7=R

q6bL

q8

q8aL

q8bL

q8*L

-

-

-

qzлR

q9

q9aL

q9bL

q9*L

q9aL

q9bL

-

qzлR

На рисунке 2.1 представлено описание машины Тьюринга с помощью системы команд.

//Установка разделителя

“=”

q0* q0*R

q0a q0aR

q0b q0bR

q0лq1=L

//Возврат на начало

слова

q1* q1*L

q1a q1aL

q1b q1bL

q1л q2 лR

//Поиск символа “*”

q2* q3*R

q2a q2aR

q2b q2bR

q2=q8=L

//Установка разделителей

для слова, между “*”

q3* q9*L

q3aq40R

q3b q71R

q30 q3aL

q31 q3bL

q3= q8=L

//Копирование, если

Первым символом оказался “a”

q4* q5*R

q4a q4aR

q4b q4bR

//Установка “a” после

Символа “=”

q5a q5aR

q5b q5bR

q5= q5=R

q5* q5*R

q5= q5=R

q5 л q6aL

//Возврат в состояние “q3”, для копирование следующего символа

q6* q6*L

q6a q6aL

q6b q6bL

q60q30R

q61 q31R

q6= q6=L

//Установка “b” после символа “=”

q7* q7*R

q7a q7aR

q7b q7bR

q7= q7=R

q7 лq6bL

//Если комбинация “*…*” не найдена, возврат на начало слова

q8* q8*L

q8a q8aL

q8b q8bL

q8 лqz лR

//Возврат на начало слова, и замена всех разделителей

q9*q9*L

q9a q9aL

q9bq9bL

q91q9bL

q90 q9aL

q9 л qz лR

Рисунок 2.1 - Система команд

Граф переходов изображен на рисунке 2.2. Структура данного представления следующая:

- вершины графа - состояния УУ;

- дуги графа и их направление - переходы между состояниями

- вершина, из которой выходит дуга - старое состояние;

- вершина, в которую входит дуга - новое состояние;

Рисунок 2.2 - Граф состояний

Тестовый пример работы алгоритма приведен на рисунке 2.3.

Исходное слово - *ab*b

q0*ab*b

* q0ab*b

*a q0b*

*ab q0*

*ab* q0л

*ab*q1=

*abq1*=

*aq1b*=

* q1ab*=

л q1*ab*=

q2*ab*=

*q3ab*=

*0q4b*=

*0bq5*=

*0b*q5=

*0b*=q5л

*0b*=q6a

*0b*q6=a

*0bq6*=a

*0q6b*=

*0q3b*=

*01q7*=a

*01*q7=a

*01*=q7a

*01*=aq7л

*01*=aq6b

*01*=q6ab

*01*q6=ab

*01q6*=ab

*01q3*=ab

*01q9*=ab

*0q9b*=ab

*q9ab*=ab

лq9*ab*=ab

qz*ab*=ab

Рисунок 2.3 - Тестовый пример работы МТ

Покажем работу машины Тьюринга на еще одном примере. На рисунке 2.4 приведен пример работы машины Тьюринга на частном случае.

Исходное слова - abba

q0abba

aq0bba

abq0ba

abbq0a

abbaq0л

abbaq1=

abbq1a=

abq1ba=

aq1bba=

л q1abba=

л abba=

q2abba=

aq2bba=

abq2ba=

abbq2a=

abbaq2=

abba=

abba=

abba=

abba=

л abba=

abba=

abba=

Рисунок 2.4 - Частный случай работы машины Тьюринга

Машина Тьюринга корректно отработала для двух примеров входных слов: частном и общем. Следовательно, можно полагать, что данная машина корректно отработает на всех вариантах входных слов.

Для нахождения ближайшего простого к n числа используем композицию машин Тьюринга. Для этого составим блок-схему и запишем все элементарные машины Тьюринга.

Элементарные машины Тьюринга, реализующие каждый простой блок композиции, приведены на рисунке 2.5:

- сумма двух аргументов

- предикат равенства

- предикат сравнения (строгое)

- вычитание двух аргументов

- предикат “меньше 2” (строгое)

Рисунок 2.5 - Элементарный машины Тьюринга

На рисунке 2.6 приведена блок-схема алгоритма.

Рисунок 2.6 - Блок-схема алгоритма

3. РАЗРАБОТКА АНАЛИТИЧЕСКОЙ И ПРОГРАММНОЙ МОДЕЛИ АЛГОРИТМА ДЛЯ РАСПОЗНАЮЩЕЙ МАШИНЫ ТЬЮРИНГА

3.1 Формальное определение распознающей машины Тьюринга

Программная модель была написана с целью распознания языка

L = { wwRwR ¦w {0,1}* }.

Обработка слова не является трудоемкой и не потребует более одной ленты.

/*Вход в машину Тьюринга. Установка разделителя в конце слова*/

0->0R

1->1R

~->*L

/*Замена "1" и "0" на символы "а" или "b"*/

0->aL

1->bL

a->aL

b->bL

*->*L

d->dL

~->~R

/*Замена "1" и "0" на "а" и "b" */

0->aL

1->bL

~->~R

/*Замена "1" и "0" на "а" и "b"*/

0->aR

1->bR

~->~R

/*Возврат в конец слова и установка признака mod 3*/

a->aR

b->bR

*->*R

~->dL

d->dR

/*Повторение действий предыдущих состояний, пока не встретим пустой символ*/

a->aR

b->bR

*->*R

d->dR

~->~L

//Если преждевременно находим пустой символ возвращаемся назад

d->~L

*->*R

Система команда МТ

/*Установка признака "0" - слово не является словом языка*/

~->0L

d->~L

*->*R

//Замена всех разделителей (кроме "*") на "1" или "0". //Конец работы машины

*->*L

b->1L

a->0L

d->dR

n->1L

0->0L

1->1L

p->0L

o->1L

h->0L

~->~R

~->~R

/*Если слово подходит по количеству символов - меняем разделитель

Возврат в конец слова*/

a->aR

b->bR

*->*R

d->mL

m->mR

p->pR

n->nR

h->hR

o->oR

~->~L

1->1R

0->0R

//Проходим снова влево, устанавливаем новый разделитель для последнего символа слова

a->pR

b->oR

m->mL

*->*L

p->pL

o->oL

0->hR

1->nR

n->nL

h->hL

/*Проходим снова влево, устанавливаем новый разделитель для предпоследнего символа слова*/

m->dL

n->nR

*->*R

~->~L

d->dR

o->oR

p->pR

h->hR

//Проходим снова влево, устанавливаем новый разделитель символа слова

h->hL

*->*L

b->nR

n->nL

a->hR

p->pL

o->oL

d->dL

m->mL

1->1R

0->0R

Система команд МТ

//Проверка на равенство двух последних триад

d->dL

*->*L

p->0R

o->1R

0->0L

1->1L

a->aR

b->bR

~->~R

// Если первый был символ "p"

*->*L

0->0L

1->1L

o->oL

p->pL

h->0R

n->nR

//Проход вправо до “*”

p->pR

o->oR

1->1R

0->0R

*->*L

//Проверка на реверс двух первых триад

0->uL

1->vL

u->uL

n->nL

h->hL

v->vL

~->~R

//Если первый был символ “0”

0->0L

1->1L

b->bL

a->aL

v->vL

u->uL

~->~R

//Проход в конец слова

0->0R

1->1R

o->oR

p->pR

n->nR

a->aR

b->bR

h->hR

u->uR

v->vR

*->*R

d->dR

m->mR

~->~L

//Замена разделителей (n->1)

*->*L

0->0L

1->1L

o->oL

p->pL

n->1R

h->hR

//Проход вправо до “*”

p->pR

o->oR

1->1R

0->0R

*->*L

// Проход вправо до “~”

0->0L

1->1L

v->vL

u->uL

b->bL

a->aL

~->~R

Система команд МТ

//Замена старого символа на новый (b->v)

b->vR

v->vR

u->uR

a->aR

//Проход вправо до границы слова

b->bR

a->aR

0->0R

1->1R

v->vR

u->uR

n->nL

h->hL

//Замена старого символа на новый (a->u)

a->uR

v->vR

u->uR

b->bR

//Проход вправо до границы слова

b->bR

a->aR

0->0R

1->1R

v->vR

u->uR

n->nL

h->hL

//Очистка всех признаков

d->~L

m->~L

*->*R

алгоритм тьюринг аналитический марков

//Проход в конец слова

0->0R

1->1R

o->oR

p->pR

n->nR

a->aR

b->bR

h->hR

u->uR

v->vR

*->*R

d->dR

m->mR

~->~L

//Очистка всех признаков

d->~L

m->~L

*->*R

//Слово не принадлежит

~->0L

//Замена всех разделителей

1->1L

0->q300L

q30o->1L

p->0L

n->1L

v->1L

u->0L

h->0L

a->0L

b->1L

~->~R

//Слово принадлежит

*->*L

~->1L

Система команд МТ

3.2 Протоколы работы машины Тьюринга (на двух словах языка и двух словах, не принадлежащих языку)

Пример работы алгоритма на слове “01”, которое не является словом исходного языка приведен в таблице 3.1.

Таблица 3.1 - Протокол работы МТ на слове “01”

Шаг

Состояние

Слово на ленте

Команда

1

л01л

2

л01л

1 -> 1R

3

л01л

л -> *L

4

л0b*л

1 ->bL

5

лab*л

0 -> aL

6

лab*л

л -> лR

7

лab*л

a -> aR

8

лab*л

b -> bR

9

лab*л

* -> *R

10

лab*л

~ -> ~L

11

лab*л

* -> *R

12

лab*0

~ -> 0L

13

лab*0

* -> *L

14

лab*0

b -> 1L

15

лa1*0

a -> 0L

16

л01*0

~ -> ~R

л01*0

В таблице 3.2 представлен протокол работы машины Тьюринга на пустом слове. Это слово принадлежит языку, что совпадает с результатом работы машины.

Таблица 3.2 - Проток работы МТ на пустом слове

Шаг

Состояние

Слово на ленте

Команда

1

ллл

2

л*л

R

3

л*л

4

л*л

5

л*л

6

л*л

7

л*л

8

л*л

9

л*л

10

л*1

11

л*1

12

л*1

13

л*1

В таблице 3.3 представлен протокол работы распознающей машины Тьюринга на слове 1. Это слово не принадлежит языку, что сходится с результатом выполнения машины.

Таблица 3.3 - Протокол работы МТ на слове “1”

Шаг

Состояние

Слово на ленте

Команда

1

л1л

2

л1*

3

лb*

1 ->bL

4

лb*

-> R

5

лb*

b -> bR

6

лb*

* -> *R

7

лb*л

-> L

8

лb*л

* -> *R

9

лb*0

-> 0L

10

лb*0

* -> *L

11

л1*0

b -> 1L

12

л1*0

-> R

13

л1*0

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

3.3 Программная модель машины Тьюринга

Для наглядной демонстрации работы детерминированной машины Тьюринга была разработана программа.

Программная модель распознающей машины Тьюринга реализована на языке программирования С#. Исходный код программы представлен в приложении Д.

Лента моделируется с помощью множества элемента управления Label, а создается в момент запуска пользователем программы. При должной настройки параметров экземпляров этого класса, получается точная графическая модель машины Тьюринга.

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

В программе предусмотрено пошаговое прохождение слова с выполнением команд, автоматическая обработка слова, построение и сохранение графика алгоритма.

3.4 Протоколы работы машины Тьюринга, построенные программно (на двух словах языка и двух словах, не принадлежащих языку)

Протоколы работы машины Тьюринга, построенные программно, приведены в приложении В. Стрелкой в них выделено положение УУ. Символом “~” обозначен пустой символ.

3.5 Расчет временной сложности (график функции временной сложности)

Данный алгоритм устроен таким образом, что наибольшее время выполняются слова длиной, кратной трем, так как для таких слов требуется наибольшее количество проверок.

Как видно из эскиза, график имеет полиномиальную зависимость 2-го порядка с неединичными коэффициентами. Также, из-за резких скачков на точках, кратных трем, можно определить, что график описывается системой из трех квадратичных уравнений.

Машина Тьюринга реализована на одной ленте, из-за чего требуются многочисленные проходы по слову для установки тех или иных разделителей.

Для слов длины кратной трем используется проход до конца слова и обратно за 2(n+2) шагов, после чего делается снова возврат на конец слова и начинается сравнение частей слов, тактами длиной (n+2)/3.

Для слов длины не кратной трем используется 2(n+2) шагов для установки разделителя, после чего осуществляется (n+2)/3 шагов для проверки слова на четность. Так как слово не принадлежит алфавиту, то делается возврат на начало слова, длиной n+2.

Таким образом, график состоит из трех частей, и экспериментально были выведены уравнения определенных точек. Уравнения приведены формулой 3.3.

Построенный программой график практически совпадает с теоретическими расчетами. На рисунке 3.2 приведен график сложности алгоритма.

Рисунок 3.2 - График сложности алгоритма

4 РАЗРАБОТКА АНАЛИТИЧЕСКОЙ МОДЕЛИ АЛГОРИТМА С ИСПОЛЬЗОВАНИЕМ НОРМАЛЬНЫХ АЛГОРИТМОВ МАРКОВА

Марковская подстановка - это операция над словами, заключающаяся в следующем:

в исходном слове г ищется самое левое вхождение слова л, если оно существует, л заменяется в на в слове г;

полученное слово г является результатом применения Марковской подстановки к слову г;

если л слово не входит в слово г, то говорят, что данная Марковская подстановка не применима к слову г [3].

Задание: реализовать алгоритм над алфавитом , который выдает 1, если исходное слово содержит комбинацию baccd, и 0 - в противном случае.

Реализация приведена на рисунке 4.1.

Рисунок 4.1 - Правила НАМ

Примеры работы алгоритма представлены на рисунке 4.2 , если слово содержит искомую комбинацию символов. На рисунке 4.3 - не содержит.

abab01baccd110d

abab01x110d

bab01x110d

bb01x110d

b01x110d

01x110d

01x110

0x110

0x10

0x0

x0

x

1

Рисунок 4.2 - Пример работы алгоритма

abad01

bad01

bd01

d01

01

1

0

Рисунок 4.3 - Пример работы алгоритма

ВЫВОДЫ

В ходе выполнения курсовой работы были закреплены навыки работы с рекурсивными функциями, машинами Тьюринга и нормальными алгоритмами Маркова.

Особенно детально были изучены различные одноленточные машины Тьюринга. Также получены навыки построения графика временной сложности алгоритма.

В данной работе разработан программный продукт, демонстрирующий работу распознающей машины Тьюринга для языка L = {wwRwR¦w {0,1}*}.

Результатом работы машины является символ “1” или “0”, в зависимости от слова, который записывается после входного слова.

Для данной машины Тьюринга был построен график временной сложности для входных слов длиной от 1 до 13.

ПЕРЕЧЕНЬ ССЫЛОК

1. Введение в теорию алгоритмов [Электронный ресурс]. - Электронные текстовые данные. - Режим доступа: http://th-algoritmov.narod.ru/1.htm

2. Алферова З. В. Теория алгоритмов. - М.: Издательство «Статистика», 1973. - 164 с.

3. Марков А.А. Теория алгорифмов./ А.А. Марков, Н.М. Нагорный - М.: Наука, 1984. -217 с.: ил.

ПРИЛОЖЕНИЕ А

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

1 Основанием для разработки является задание на курсовую работу, выданное кафедрой прикладной математики и информатики.

2 Целью разработки является создание программной модели машины Тьюринга, распознающей язык L = { wwRwR ¦w {0,1}* }, расчет и экспериментальная проверка расчета временной сложности МТ.

3 Требования к программе:

-при проверке слова на принадлежность языку необходимо запретить ввод с клавиатуры символов не из входного алфавита заданного языка;

-при проверке слова на принадлежность языку выводить на экран каждый шаг работы машины Тьюринга;

-сохранять протокол работы машины Тьюринга в текстовом файле;

-при построении графика временной сложности работы машины Тьюринга значения для графика получить практически, с помощью созданной программной модели машины Тьюринга; для генерации слов длиной n использовать метод полного перебора.

4 Требования к программной документации:

- пояснительная записка;

- руководство пользователя.

5 Этапы разработки

Приложение Б

Руководство пользователя

Б.1 Назначение программы

Программа предназначена для демонстрации работы одноленточной машины Тьюринга на примере языка L = { wwRwR ¦w {0,1}* }. Пользователь может проверить введенное им слово на принадлежность языку, сохранить результаты работы в текстовый файл, построить и сохранить график сложности алгоритма для слова выбранной длины.

Б.2 Исполнение программы

Так как программа выполнена на языке C#, то для ее запуска обязательно наличие Microsoft .NET Framework версии, не ниже 4.0. Запуск приложения осуществляется через файл TuringMachine.exe.

При запуске приложения открывается основное окно работы программы, приведенное на рисунке Б.1 , где пользователь может с помощью соответствующих кнопок выполнять интересующие его действия.

Изначально на ленте записано пустое слово. Для смены слова, пользователь должен ввести его в графу “Слово” и ввести начальное состояние, после чего нажать на кнопку “Ввести”. Ввод состояния был внедрен для большей гибкости программы, чтобы пользователь мог начать работу с любого другого состояния.

Файл листинга программы сохраняется автоматически при завершении обработки слова в текущую директорию программы под названием listing.txt.

В нем содержится информация об изменениях слова при выполнении определенных операций над ним.

Для запуска работы машины Тьюринга предназначена кнопка “Старт”, которая начинает автоматически выполнять команды над текущим словом. Работу машины можно приостановить нажав на кнопку “Пауза\Продолжить”. Левее кнопок располагается бегунок, манипулируя которым пользователь может изменять скорость работы машины. Также предусмотрена кнопка “Шаг”, при нажатии на которую, машина выполняет одну команду и выводит текущее состояние, команду на экран.

Ниже располагается поле для ввода длины слова и кнопка “Построить график”, по нажатию на которую начинает строиться график временной сложности данного алгоритма.

Рисунок Б.1 - Главное окно программы

Приложение В

Протоколы работы машины Тьюринга, построенные программно

Протокол 1 (слово принадлежит языку):

Исходное слово - 100101

->100101 | Команда: q01 -> q01R | Состояние: q0

1->00101 | Команда: q00 -> q00R | Состояние: q0

10->0101 | Команда: q00 -> q00R | Состояние: q0

100->101 | Команда: q01 -> q01R | Состояние: q0

1001->01 | Команда: q00 -> q00R | Состояние: q0

10010->1 | Команда: q01 -> q01R | Состояние: q0

100101 | Команда: q0~ -> q1*L | Состояние: q0

10010->1*| Команда: q11 -> q2bL | Состояние: q1

1001->0b* | Команда: q20 -> q3aL | Состояние: q2

100->1ab* | Команда: q31 -> q4bR | Состояние: q3

100b->ab* | Команда: q4a -> q4aR | Состояние: q4

100ba->b* | Команда: q4b -> q4bR | Состояние: q4

100bab->* | Команда: q4* -> q4*R | Состояние: q4

100bab* | Команда: q4~ -> q1dL | Состояние: q4

100bab->*d | Команда: q1* -> q1*L | Состояние: q1

100ba->b*d | Команда: q1b -> q1bL | Состояние: q1

100b->ab*d | Команда: q1a -> q1aL | Состояние: q1

100->bab*d | Команда: q1b -> q1bL | Состояние: q1

10->0bab*d | Команда: q10 -> q2aL | Состояние: q1

1->0abab*d | Команда: q20 -> q3aL | Состояние: q2

->1aabab*d | Команда: q31 -> q4bR | Состояние: q3

b->aabab*d | Команда: q4a -> q4aR | Состояние: q4

ba->abab*d | Команда: q4a -> q4aR | Состояние: q4

baa->bab*d | Команда: q4b -> q4bR | Состояние: q4

baab->ab*d | Команда: q4a -> q4aR | Состояние: q4

baaba->b*d | Команда: q4b -> q4bR | Состояние: q4

baabab->*d | Команда: q4* -> q4*R | Состояние: q4

baabab*->d | Команда: q4d -> q4dR | Состояние: q4

baabab*d | Команда: q4~ -> q1dL | Состояние: q4

baabab*->dd | Команда: q1d -> q1dL | Состояние: q1

baabab->*dd | Команда: q1* -> q1*L | Состояние: q1

baaba->b*dd | Команда: q1b -> q1bL | Состояние: q1

baab->ab*dd | Команда: q1a -> q1aL | Состояние: q1

baa->bab*dd | Команда: q1b -> q1bL | Состояние: q1

ba->abab*dd | Команда: q1a -> q1aL | Состояние: q1

b->aabab*dd | Команда: q1a -> q1aL | Состояние: q1

->baabab*dd | Команда: q1b -> q1bL | Состояние: q1

baabab*dd | Команда: q1~ -> q9~R | Состояние: q1

->baabab*dd | Команда: q9b -> q9bR | Состояние: q9

b->aabab*dd | Команда: q9a -> q9aR | Состояние: q9

ba->abab*dd | Команда: q9a -> q9aR | Состояние: q9

baa->bab*dd | Команда: q9b -> q9bR | Состояние: q9

baab->ab*dd | Команда: q9a -> q9aR | Состояние: q9

baaba->b*dd | Команда: q9b -> q9bR | Состояние: q9

baabab->*dd | Команда: q9* -> q9*R | Состояние: q9

baabab*->dd | Команда: q9d -> q10mL | Состояние: q9

baabab->*md | Команда: q10* -> q10*L | Состояние: q10

baaba->b*md | Команда: q10b -> q9oR | Состояние: q10

baabao->*md | Команда: q9* -> q9*R | Состояние: q9

baabao*->md | Команда: q9m -> q9mR | Состояние: q9

baabao*m->d | Команда: q9d -> q10mL | Состояние: q9

baabao*->mm | Команда: q10m -> q10mL | Состояние: q10

baabao->*mm | Команда: q10* -> q10*L | Состояние: q10

baaba->o*mm | Команда: q10o -> q10oL | Состояние: q10

baab->ao*mm | Команда: q10a -> q9pR | Состояние: q10

baabp->o*mm | Команда: q9o -> q9oR | Состояние: q9

baabpo->*mm | Команда: q9* -> q9*R | Состояние: q9

baabpo*->mm | Команда: q9m -> q9mR | Состояние: q9

baabpo*m->m | Команда: q9m -> q9mR | Состояние: q9

baabpo*mm | Команда: q9~ -> q11~L | Состояние: q9

baabpo*m->m | Команда: q11m -> q12dL | Состояние: q11

baabpo*->md | Команда: q12m -> q12mL | Состояние: q12

baabpo->*md | Команда: q12* -> q12*L | Состояние: q12

baabp->o*md | Команда: q12o -> q12oL | Состояние: q12

baab->po*md | Команда: q12p -> q12pL | Состояние: q12

baa->bpo*md | Команда: q12b -> q11nR | Состояние: q12

baan->po*md | Команда: q11p -> q11pR | Состояние: q11

baanp->o*md | Команда: q11o -> q11oR | Состояние: q11

baanpo->*md | Команда: q11* -> q11*R | Состояние: q11

baanpo*->md | Команда: q11m -> q12dL | Состояние: q11

baanpo->*dd | Команда: q12* -> q12*L | Состояние: q12

baanp->o*dd | Команда: q12o -> q12oL | Состояние: q12

baan->po*dd | Команда: q12p -> q12pL | Состояние: q12

baa->npo*dd | Команда: q12n -> q12nL | Состояние: q12

ba->anpo*dd | Команда: q12a -> q11hR | Состояние: q12

bah->npo*dd | Команда: q11n -> q11nR | Состояние: q11

bahn->po*dd | Команда: q11p -> q11pR | Состояние: q11

bahnp->o*dd | Команда: q11o -> q11oR | Состояние: q11

bahnpo->*dd | Команда: q11* -> q11*R | Состояние: q11

bahnpo*->dd | Команда: q11d -> q11dR | Состояние: q11

bahnpo*d->d | Команда: q11d -> q11dR | Состояние: q11

bahnpo*dd | Команда: q11~ -> q13~L | Состояние: q11

bahnpo*d->d | Команда: q13d -> q13dL | Состояние: q13

bahnpo*->dd | Команда: q13d -> q13dL | Состояние: q13

bahnpo->*dd | Команда: q13* -> q13*L | Состояние: q13

bahnp->o*dd | Команда: q13o -> q191R | Состояние: q13

bahnp1->*dd | Команда: q19* -> q19*L | Состояние: q19

bahnp->1*dd | Команда: q191 -> q191L | Состояние: q19

bahn->p1*dd | Команда: q19p -> q19pL | Состояние: q19

bah->np1*dd | Команда: q19n -> q201R | Состояние: q19

bah1->p1*dd | Команда: q20p -> q20pR | Состояние: q20

bah1p->1*dd | Команда: q201 -> q201R | Состояние: q20

bah1p1->*dd | Команда: q20* -> q13*L | Состояние: q20

bah1p->1*dd | Команда: q131 -> q131L | Состояние: q13

bah1->p1*dd | Команда: q13p -> q140R | Состояние: q13

bah10->1*dd | Команда: q141 -> q141L | Состояние: q14

bah1->01*dd | Команда: q140 -> q140L | Состояние: q14

bah->101*dd | Команда: q141 -> q141L | Состояние: q14

ba->h101*dd | Команда: q14h -> q150R | Состояние: q14

ba0->101*dd | Команда: q151 -> q151R | Состояние: q15

ba01->01*dd | Команда: q150 -> q150R | Состояние: q15

ba010->1*dd | Команда: q151 -> q151R | Состояние: q15

ba0101->*dd | Команда: q15* -> q13*L | Состояние: q15

ba010->1*dd | Команда: q131 -> q131L | Состояние: q13

ba01->01*dd | Команда: q130 -> q130L | Состояние: q13

ba0->101*dd | Команда: q131 -> q131L | Состояние: q13

ba->0101*dd | Команда: q130 -> q130L | Состояние: q13

b->a0101*dd | Команда: q13a -> q9aR | Состояние: q13

ba->0101*dd | Команда: q90 -> q90R | Состояние: q9

ba0->101*dd | Команда: q91 -> q91R | Состояние: q9

ba01->01*dd | Команда: q90 -> q90R | Состояние: q9

ba010->1*dd | Команда: q91 -> q91R | Состояние: q9

ba0101->*dd | Команда: q9* -> q9*R | Состояние: q9

ba0101*->dd | Команда: q9d -> q10mL | Состояние: q9

ba0101->*md | Команда: q10* -> q10*L | Состояние: q10

ba010->1*md | Команда: q101 -> q9nR | Состояние: q10

ba010n->*md | Команда: q9* -> q9*R | Состояние: q9

ba010n*->md | Команда: q9m -> q9mR | Состояние: q9

ba010n*m->d | Команда: q9d -> q10mL | Состояние: q9

ba010n*->mm | Команда: q10m -> q10mL | Состояние: q10

ba010n->*mm | Команда: q10* -> q10*L | Состояние: q10

ba010->n*mm | Команда: q10n -> q10nL | Состояние: q10

ba01->0n*mm | Команда: q100 -> q9hR | Состояние: q10

ba01h->n*mm | Команда: q9n -> q9nR | Состояние: q9

ba01hn->*mm | Команда: q9* -> q9*R | Состояние: q9

ba01hn*->mm | Команда: q9m -> q9mR | Состояние: q9

ba01hn*m->m | Команда: q9m -> q9mR | Состояние: q9

ba01hn*mm | Команда: q9~ -> q11~L | Состояние: q9

ba01hn*m->m | Команда: q11m -> q12dL | Состояние: q11

ba01hn*->md | Команда: q12m -> q12mL | Состояние: q12

ba01hn->*md | Команда: q12* -> q12*L | Состояние: q12

ba01h->n*md | Команда: q12n -> q12nL | Состояние: q12

ba01->hn*md | Команда: q12h -> q12hL | Состояние: q12

ba0->1hn*md | Команда: q121 -> q161R | Состояние: q12

ba01->hn*md | Команда: q16h -> q16hL | Состояние: q16

ba0->1hn*md | Команда: q161 -> q21vL | Состояние: q16

ba->0vhn*md | Команда: q210 -> q210L | Состояние: q21

b->a0vhn*md | Команда: q21a -> q21aL | Состояние: q21

->ba0vhn*md | Команда: q21b -> q21bL | Состояние: q21

ba0vhn*md | Команда: q21~ -> q22~R | Состояние: q21

->ba0vhn*md | Команда: q22b -> q23vR | Состояние: q22

v->a0vhn*md | Команда: q23a -> q23aR | Состояние: q23

va->0vhn*md | Команда: q230 -> q230R | Состояние: q23

va0->vhn*md | Команда: q23v -> q23vR | Состояние: q23

va0v->hn*md | Команда: q23h -> q16hL | Состояние: q23

va0->vhn*md | Команда: q16v -> q16vL | Состояние: q16

va->0vhn*md | Команда: q160 -> q17uL | Состояние: q16

v->auvhn*md | Команда: q17a -> q17aL | Состояние: q17

->vauvhn*md | Команда: q17v -> q17vL | Состояние: q17

vauvhn*md | Команда: q17~ -> q24~R | Состояние: q17

->vauvhn*md | Команда: q24v -> q24vR | Состояние: q24

v->auvhn*md | Команда: q24a -> q25uR | Состояние: q24

vu->uvhn*md | Команда: q25u -> q25uR | Состояние: q25

vuu->vhn*md | Команда: q25v -> q25vR | Состояние: q25

vuuv->hn*md | Команда: q25h -> q16hL | Состояние: q25

vuu->vhn*md | Команда: q16v -> q16vL | Состояние: q16

vu->uvhn*md | Команда: q16u -> q16uL | Состояние: q16

v->uuvhn*md | Команда: q16u -> q16uL | Состояние: q16

->vuuvhn*md | Команда: q16v -> q16vL | Состояние: q16

vuuvhn*md | Команда: q16~ -> q18~R | Состояние: q16

->vuuvhn*md | Команда: q18v -> q18vR | Состояние: q18

v->uuvhn*md | Команда: q18u -> q18uR | Состояние: q18

vu->uvhn*md | Команда: q18u -> q18uR | Состояние: q18

vuu->vhn*md | Команда: q18v -> q18vR | Состояние: q18

vuuv->hn*md | Команда: q18h -> q18hR | Состояние: q18

vuuvh->n*md | Команда: q18n -> q18nR | Состояние: q18

vuuvhn->*md | Команда: q18* -> q18*R | Состояние: q18

vuuvhn*->md | Команда: q18m -> q18mR | Состояние: q18

vuuvhn*m->d | Команда: q18d -> q18dR | Состояние: q18

vuuvhn*md | Команда: q18~ -> q26~L | Состояние: q18

vuuvhn*m->d | Команда: q26d -> q26~L | Состояние: q26

vuuvhn*->m | Команда: q26m -> q26~L | Состояние: q26

vuuvhn->* | Команда: q26* -> q31*R | Состояние: q26

vuuvhn* | Команда: q31~ -> q311L | Состояние: q31

vuuvhn->*1 | Команда: q31* -> q30*L | Состояние: q31

vuuvh->n*1 | Команда: q30n -> q301L | Состояние: q30

vuuv->h1*1 | Команда: q30h -> q300L | Состояние: q30

vuu->v01*1 | Команда: q30v -> q301L | Состояние: q30

vu->u101*1 | Команда: q30u -> q300L | Состояние: q30

v->u0101*1 | Команда: q30u -> q300L | Состояние: q30

->v00101*1 | Команда: q30v -> q301L | Состояние: q30

100101*1 | Команда: q30~ -> qz~R | Состояние: q30

Протокол 2 (слово не принадлежит языку)

Исходное слово - 010

->010 | Команда: q00 -> q00R | Состояние: q0

0->10 | Команда: q01 -> q01R | Состояние: q0

01->0 | Команда: q00 -> q00R | Состояние: q0

010 | Команда: q0~ -> q1*L | Состояние: q0

01->0* | Команда: q10 -> q2aL | Состояние: q1

0->1a* | Команда: q21 -> q3bL | Состояние: q2

->0ba* | Команда: q30 -> q4aR | Состояние: q3

a->ba* | Команда: q4b -> q4bR | Состояние: q4

ab->a* | Команда: q4a -> q4aR | Состояние: q4

aba->* | Команда: q4* -> q4*R | Состояние: q4

aba* | Команда: q4~ -> q1dL | Состояние: q4

aba->*d | Команда: q1* -> q1*L | Состояние: q1

ab->a*d | Команда: q1a -> q1aL | Состояние: q1

a->ba*d | Команда: q1b -> q1bL | Состояние: q1

->aba*d | Команда: q1a -> q1aL | Состояние: q1

aba*d | Команда: q1~ -> q9~R | Состояние: q1

->aba*d | Команда: q9a -> q9aR | Состояние: q9

a->ba*d | Команда: q9b -> q9bR | Состояние: q9

ab->a*d | Команда: q9a -> q9aR | Состояние: q9

aba->*d | Команда: q9* -> q9*R | Состояние: q9

aba*->d | Команда: q9d -> q10mL | Состояние: q9

aba->*m | Команда: q10* -> q10*L | Состояние: q10

ab->a*m | Команда: q10a -> q9pR | Состояние: q10

abp->*m | Команда: q9* -> q9*R | Состояние: q9

abp*->m | Команда: q9m -> q9mR | Состояние: q9

abp*m | Команда: q9~ -> q11~L | Состояние: q9

abp*->m | Команда: q11m -> q12dL | Состояние: q11

abp->*d | Команда: q12* -> q12*L | Состояние: q12

ab->p*d | Команда: q12p -> q12pL | Состояние: q12

a->bp*d | Команда: q12b -> q11nR | Состояние: q12

an->p*d | Команда: q11p -> q11pR | Состояние: q11

anp->*d | Команда: q11* -> q11*R | Состояние: q11

anp*->d | Команда: q11d -> q11dR | Состояние: q11

anp*d | Команда: q11~ -> q13~L | Состояние: q11

anp*->d | Команда: q13d -> q13dL | Состояние: q13

anp->*d | Команда: q13* -> q13*L | Состояние: q13

an->p*d | Команда: q13p -> q140R | Состояние: q13

an0->*d | Команда: q14* -> q14*L | Состояние: q14

an->0*d | Команда: q140 -> q140L | Состояние: q14

a->n0*d | Команда: q14n -> q27nR | Состояние: q14

an->0*d | Команда: q270 -> q270R | Состояние: q27

an0->*d | Команда: q27* -> q27*R | Состояние: q27

an0*->d | Команда: q27d -> q27dR | Состояние: q27

an0*d | Команда: q27~ -> q28~L | Состояние: q27

an0*->d | Команда: q28d -> q28~L | Состояние: q28

an0->* | Команда: q28* -> q29*R | Состояние: q28

an0* | Команда: q29~ -> q310L | Состояние: q29

an0->*0 | Команда: q31* -> q30*L | Состояние: q31

an->0*0 | Команда: q300 -> q300L | Состояние: q30

a->n0*0 | Команда: q30n -> q301L | Состояние: q30

->a10*0 | Команда: q30a -> q300L | Состояние: q30

010*0 | Команда: q30~ -> qz~R | Состояние: q30

Приложение Д

Исходный код программы

//Основная форма.Содержит: машина Тьюринга, построение маленького эскиза графика

// Form1.cs

using System;

using System.Collections;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Threading;

using System.Drawing;

using System.Linq;

using System.Text.RegularExpressions;

using System.IO;

using System.Windows.Forms;

using System.Windows.Forms.DataVisualization.Charting;

namespace TuringMachine

{

delegate void TheDelegate();

delegate int IntDelegate();

delegate void ParamDelegate(double a);

public partial class Form1 : Form

{

private int location = 0; //положение УУ на МТ

private int steps= 0; // Количество проходов УУ по элементу слова

private static String shortState; //кортоткая форма номера состония (Например,q0)

private String state; //Полное состояние МТ (Например, q00R)

int currWordLength = 0; //Длина текущего слова

private int index = 0; // Индекс элемента в массиве max

public static int[] max = new int[20]; //Массив, содержащий в себе пару "длина слова-максимальное количество тактов"

private int RandomWordLength = 0; //Вводимая пользователем длина слова, для построения графика

String[] keyv = new String[2]; //Массив команд вида: q00->q00R

private bool flag = true; //Признак: работает МТ в текущий момент или нет.

private bool second_flag = true; // Признак: проводить ли рендеринг движения УУ или нет.

private static int WordLength; //Длина введенного пользователем слова

private static Label[] ribbon = new Label[200]; //Лента МТ

StreamWriter strwr = new StreamWriter(@"./listing.txt"); // Поток-писатель для выведения листинга в файл

private String curstate; //Текущее состояние МТ

private SortedList<String, String> mtstates = new SortedList<String, String>(); //Контейнер для всех состояний МТ

Thread okras; // Второй поток для параллельного рендеринга

public Form1()

{

InitializeComponent();

int i; trackBar1.Value = 250; chart1.Series[0].Name = "";

chart1.Series[0].Color = Color.Red;

textBox1.Text = File.ReadAllText(@"D:/МТ_Моя.txt");

for (int j = 0; j < textBox1.Lines.Length; j++)

{

if (textBox1.Lines[j].Equals(""))

continue;

keyv[0] = Splited(textBox1.Lines[j])[0];

keyv[1] = Splited(textBox1.Lines[j])[2];

mtstates.Add(keyv[0], keyv[1]);

}

for (int j = 0; j < 20; j++)

max[j] = new int();

state = Splited(textBox1.Lines[0])[2];

for (i = 0; i < 50; i++)

{

ribbon[i] = new Label();

ribbon[i].Text = "~";

ribbon[i].Size = label1.Size;

ribbon[i].Location = new Point(0 + (i) * ribbon[i].Width, 0);

ribbon[i].Font = label1.Font;

ribbon[i].BackColor = Color.White;

ribbon[i].BorderStyle = BorderStyle.FixedSingle;

panel1.Controls.Add(ribbon[i]);

}

}

private void button2_Click(object sender, EventArgs e)

{

button2.Enabled = false;

okras = new Thread(new ThreadStart(Paint_Label));

okras.Start();

}

public void State()

{

textBox3.Text = curstate;

}

public void Button2Enabled()

{

button2.Enabled = true; ;

}

public void Replace()

{

ribbon[location + 10].Text = state[state.Length - 2].ToString();

}

public void ShowState()

{

textBox4.Text = curstate + ribbon[location + 10].Text + "->" + state;

}

public int TrackBar()

{

return trackBar1.Value;

}

public void Paint_Label()

{

TheDelegate deli = new TheDelegate(State);

TheDelegate enbl = new TheDelegate(Button2Enabled);

while (true)

{

shortState = state.Remove(state.Length - 2, 2);

if (shortState.Equals("qz"))

{

if (second_flag == true)

{

MessageBox.Show("Машина Тьюринга завершила свою работу.", "Сообщение", MessageBoxButtons.OK, MessageBoxIcon.Information);

steps = 0;

shortState = "q0";

curstate = "qz";

Invoke(deli);

ribbon[location + 10].BackColor = Color.SkyBlue;

ribbon[location + 9].BackColor = Color.White;

}

Invoke(enbl);

return;

}

try

{

Steps(mtstates[String.Concat(shortState + ribbon[location + 10].Text)], shortState, second_flag);

}

catch (Exception e)

{

MessageBox.Show(String.Concat(shortState + ribbon[location + 10].Text) + " отсутствует в словаре", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);

Invoke(enbl);

okras.Abort();

break;

}

}

}

public String ToFile()

{

return String.Concat(shortState + ribbon[location + 10].Text) + " -> " + mtstates[String.Concat(shortState + ribbon[location + 10].Text)];

}

void PrintDataToFile()

{

String str = "";

for (int k = 0; k < 50; k++)

{

if (!ribbon[k].Text.Equals("~"))

{

if (currWordLength - 10 == location)

str = str + "->" + ribbon[currWordLength].Text;

else

str = str + ribbon[currWordLength].Text;

}

currWordLength++;

}

strwr.WriteLine(str + " | Команда: " + ToFile() +" | Состояние: "+ shortState + "\n");

strwr.WriteLine("");

strwr.Flush();

currWordLength = 0;

}

public void Steps(String state, String shortState, bool graph)

{

if (graph == true)

{

PrintDataToFile();

}

TheDelegate deli = new TheDelegate(State);

TheDelegate deli_zamena = new TheDelegate(Replace);

TheDelegate deli_show = new TheDelegate(ShowState);

IntDelegate deli_track = new IntDelegate(TrackBar);

this.state = state;

switch (state[state.Length - 1])

{

case 'L':

curstate = shortState;

if (graph == true)

{

ribbon[location + 10].BackColor = Color.SkyBlue;

Invoke(deli_show);

ribbon[location + 9].BackColor = Color.White;

Invoke(deli);

Thread.Sleep(Convert.ToInt32(Invoke(deli_track)));

ribbon[location + 10].BackColor = Color.White;

ribbon[location + 9].BackColor = Color.White;

}

Invoke(deli_zamena);

location--;

steps++;

break;

case 'R':

curstate = shortState;

if (graph == true)

{

ribbon[location + 10].BackColor = Color.SkyBlue;

Invoke(deli_show);

ribbon[location + 9].BackColor = Color.White;

Invoke(deli);

}

Invoke(deli_zamena);

location++; steps++;

if (graph == true)

Thread.Sleep(Convert.ToInt32(Invoke(deli_track))); break;

}

}

private void заполнитьToolStripMenuItem_Click(object sender, EventArgs e)

{

OpenFileDialog dialog = new OpenFileDialog();

dialog.InitialDirectory = "D:\\";

dialog.Filter = "Text documents (*.txt*)|*.txt*";

dialog.RestoreDirectory = true;

if (dialog.ShowDialog() == DialogResult.OK)

{

try

{

dialog.OpenFile();

textBox1.Text = File.ReadAllText(dialog.FileName);

for (int j = 0; j < textBox1.Lines.Length; j++)

{

if (textBox1.Lines[j].Equals(""))

continue;

keyv[0] = Splited(textBox1.Lines[j])[0];

keyv[1] = Splited(textBox1.Lines[j])[2];

mtstates.Add(keyv[0], keyv[1]);

}

state = Splited(textBox1.Lines[0])[2];

}

catch (ArgumentException ec)

{

MessageBox.Show(ec.Message, "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error); textBox4.Text = "";

}

}

}

public String[] Splited(String str)

{

String delimeter = "->";

String[] first = new String[3];

first = str.Split(delimeter.ToCharArray());

return first;

}

private void button3_Click(object sender, EventArgs e)

{

if (textBox3.Text.Equals("") || textBox2.Text.Equals(""))

{ MessageBox.Show("Машина Тьюринга не запущена!"); return; }

if (textBox3.Text.Equals("qz"))

{ MessageBox.Show("Машина Тьюринга завершила свою работу!"); return; }

if (flag == true)

{

if (okras == null)

{

MessageBox.Show("Работа машины не начата.");

return;

}

if (okras.IsAlive == true)

{

okras.Suspend();

flag = false;

}

else

MessageBox.Show("Работа машины завершена.");

}

else

{

okras.Resume();

flag = true;

}

}

private void button4_Click(object sender, EventArgs e)

{

max[0] = 12; index = 0; button2.Enabled = true;

strwr.WriteLine("Листинг машины Тьюринга:");

strwr.WriteLine("");

strwr.WriteLine("Исходное слово - " + textBox2.Text);

strwr.WriteLine("");

if (textBox3.TextLength == 0)

{ MessageBox.Show("Введите состояние.", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error); return; }

string pattern = "\\bq((\\d\\d)|(\\d))\\b";

Regex rgx = new Regex(pattern);

Match isMatch = rgx.Match(textBox3.Text);

if (isMatch.Value == "")

{

MessageBox.Show("Состояние введено неверно.", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error); return;

}

for (int j = 0; j < 50; j++)

ribbon[j].Text = "~"; location = 0;

String template = textBox2.Text;

WordLength = textBox2.TextLength;

state = textBox3.Text + state.Remove(0, state.Length - 2);

int i = 0;

while (i < textBox2.TextLength)

{

ribbon[i + 10].Text = Convert.ToString(template[i]);

i++;

}

}

private void button5_Click(object sender, EventArgs e)

{

TheDelegate deli = new TheDelegate(State);

TheDelegate enbl = new TheDelegate(Button2Enabled);

shortState = state.Remove(state.Length - 2, 2);

if (shortState.Equals("qz"))

{

MessageBox.Show("Машина Тьюринга завершила свою работу.", "Сообщение", MessageBoxButtons.OK, MessageBoxIcon.Information);

curstate = "qz";

Invoke(deli);

Invoke(enbl);

ribbon[location + 10].BackColor = Color.SkyBlue;

ribbon[location + 9].BackColor = Color.White;

return;

}

try

{

StepByStep(mtstates[String.Concat(shortState + ribbon[location + 10].Text)], shortState);

}

catch (Exception ex)

{

MessageBox.Show(ex.Message, "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);

textBox4.Text = ""; Invoke(enbl);

}

}

public void StepByStep(String state, String shortState)

{

TheDelegate deli = new TheDelegate(State);

TheDelegate deli_zamena = new TheDelegate(Replace);

TheDelegate deli_show = new TheDelegate(ShowState);

this.state = state;

PrintDataToFile();

switch (state[state.Length - 1])

{

case 'L':

curstate = shortState;

ribbon[location + 10].BackColor = Color.SkyBlue;

Invoke(deli_show);

Invoke(deli_zamena);

ribbon[location + 9].BackColor = Color.White;

ribbon[location + 11].BackColor = Color.White;

Invoke(deli);

location--; steps++;

break;

case 'R':

curstate = shortState;

ribbon[location + 10].BackColor = Color.SkyBlue;

Invoke(deli_show);

Invoke(deli_zamena);

ribbon[location + 9].BackColor = Color.White;

ribbon[location + 11].BackColor = Color.White;

Invoke(deli);

location++; steps++;

break;

}

}

private void textBox2_KeyPress(object sender, KeyPressEventArgs e)

{

{

string str = e.KeyChar.ToString();

if (System.Text.RegularExpressions.Regex.IsMatch(str, @"[^0-1\b]$"))

{

e.Handled = true;

}

}

}

private void textBox3_KeyPress(object sender, KeyPressEventArgs e)

{

{

string str = e.KeyChar.ToString();

if (System.Text.RegularExpressions.Regex.IsMatch(str, @"[^\bq\d]$"))

{

e.Handled = true;

}

}

}

private void trackBar1_Scroll(object sender, EventArgs e)

{

toolTip1.SetToolTip(trackBar1, "Скорость работы МТ. Текущая скорость - " + trackBar1.Value.ToString() + " мс");

}

WordGenerator wh;

private void button1_Click(object sender, EventArgs e)

{

max[0] = 12;

state = "q00R"; index = 0;

if (textBox5.TextLength == 0)

{ MessageBox.Show("Введите длину слова (в пределах разумного).", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error); return; }

Int32 r = Convert.ToInt32(textBox5.Text); WordLength = r;

wh = new WordGenerator(0, r, "01");

ParamDelegate pamd = new ParamDelegate(ProgressBarRender);

double progress = 0.0;

double progr = 100.00 / r;

progressBar1.Value = 0;

while (true)

{

for (int i = 0; i < 50; i++)

{

ribbon[i].Text = "~";

}

curstate = "q0";

int p = 0;

try

{

String temp = wh.NextWord(ref p);

if (!temp.Equals(""))

{

if (temp.Length > RandomWordLength)

{

index++; pamd(progress);

progress = progress + progr;

}

for (int i = 0; i < temp.Length; i++)

{

ribbon[i + 10].Text = temp[i].ToString();

}

second_flag = false;

state = "q00R";

pamd(progress);

Paint_Label();

if (steps > max[index])

max[index] = steps;

steps = 0;

second_flag = true;

RandomWordLength = temp.Length;

}

}

catch (Exception ec)

{ RandomWordLength = 0; ; GraphicRender(); return; }

for (int i = 0; i < 50; i++)

{

ribbon[i].Text = "~";

}

}

}

private void button6_Click(object sender, EventArgs e)

{

for (int i = 0; i < index+1; i++)

{

MessageBox.Show(max[i].ToString());

}

}

public void ProgressBarRender(double a)

{

progressBar1.Value = Convert.ToInt32(Math.Round(a));

}

public void GraphicRender(){

chart1.Series.Clear();

Series mainGrapgh = new Series();

mainGrapgh.ChartType = SeriesChartType.Line;

chart1.Series.Add(mainGrapgh);

chart1.Series[0].Color = Color.Red;

mainGrapgh.Name = "ГС";

Point[] points = new Point[index + 1];

for (int i = 0; i < index + 1; i++)

{

points[i] = new Point(i, chart1.Size.Height + max[i]);

chart1.Series[0].Points.AddXY(i,max[i]);

if (i % 3 == 0)

{

chart1.Series[0].Points[i].MarkerColor = Color.ForestGreen;

chart1.Series[0].Points[i].MarkerStyle = MarkerStyle.Circle;

chart1.Series[0].Points[i].MarkerSize = 3;

}

chart1.Series[0].Points[i].Label = max[i].ToString();

}

}

private void chart1_Click(object sender, EventArgs e)

{

График graph = new График();

graph.Show();

}

private void Form1_FormClosing(object sender, FormClosingEventArgs e)

{

strwr.Close();

Environment.Exit(0);

}

private void textBox5_KeyPress(object sender, KeyPressEventArgs e)

{

{

string str = e.KeyChar.ToString();

if (System.Text.RegularExpressions.Regex.IsMatch(str, @"[^\b\d]$"))

{

e.Handled = true;

}

}

}

}

}

//Дополнительная форма. Содержит: построение большого графика

//График.cs

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Windows.Forms.DataVisualization.Charting;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace TuringMachine

{

public partial class График : Form

{

public График()

{

InitializeComponent();

RenderGraph(ref Form1.max);

}

void RenderGraph(ref Int32[] max)

{

int i = 0;

chart1.Series.Clear();

Series mainGrapgh = new Series();

Series highGrapgh = new Series();

Series lowGraph = new Series();

Series lowGraph2 = new Series();

Страница:


Подобные документы

  • Эффективность алгоритмов

    Анализ алгоритмов, оценка параметров алгоритма (эффективности, сложности, правильности). Комплексный анализ эффективности алгоритма на основе комплексной оценки ресурсов формальной системы. Верификация при коллективной разработке программных систем.

    презентация [234,9 K], добавлен 22.10.2013

  • Разработка алгоритма обработки сигнала на основе теории восприятия информации человеком

    Анализ существующих алгоритмов обработки информации человеком и современных моделей памяти. Разработка алгоритмов и математической модели ассоциативного мышления. Имитационная модель обработки информации. Компьютерный эксперимент по тестированию модели.

    курсовая работа [2,3 M], добавлен 19.11.2014

  • Оценка сложности алгоритмов

    Общее понятие алгоритма и меры его сложности. Временная и емкостная сложность алгоритмов. Основные методы и приемы анализа сложности. Оптимизация, связанная с выбором метода построения алгоритма и с выбором методов представления данных в программе.

    реферат [90,6 K], добавлен 27.11.2012

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

    Принципы работы и основы программирования машины Тьюринга, а также перечень правил написания алгоритмов на ее эмуляторе. Особенности решения задачи по сложению нескольких чисел в двоичной системе путем реализации ее алгоритма на эмуляторе машины Тьюринга.

    контрольная работа [82,4 K], добавлен 05.12.2010

  • Формализация понятия "алгоритм"

    Более строгое описание алгоритма, чем общее или формализация понятия алгоритма. Три подхода к формализации: теория конечных и бесконечных автоматов, теория вычислимых (рекурсивных) функций и л-исчисление Черча. Воображаемые машины Поста и Тьюринга.

    реферат [370,0 K], добавлен 09.02.2009

  • Виды и свойства алгоритмов. Решение задачи Майхилла (о стрелках)

    Виды алгоритмов как логико-математических средств, характеристика свойств. Корректный вывод алгоритма при решении вычислительной задачи. Механизм реализации алгоритма, его описание. Решение задачи Майхилла при помощи автоматной модели поведения стрелка.

    курсовая работа [53,6 K], добавлен 17.07.2014

  • Разработка алгоритма и программы управления лифтом

    Разработка модели лифта, алгоритма и программы на языке JavaScript. Возможность использования модели при проектировании промышленных лифтов и отладки управляющих программ. Основные принципы построения модели лифта, выполнение вычислительного эксперимента.

    курсовая работа [495,8 K], добавлен 09.06.2013

  • Разработка алгоритмов и программ для определения сходства семантических сетей на основе их сложности

    Семантические сети как модели представления знаний. Основные методы определения сходства графовых моделей систем. Метод решения задач определения сходства семантических сетей на основе их сложности. Разработка алгоритмов и их программная реализация.

    дипломная работа [1,3 M], добавлен 17.12.2011

  • Построение концептуальной имитационной модели

    Построение концептуальной модели и метод имитационного моделирования. Определение переменных уравнений математической модели и построение моделирующего алгоритма. Описание возможных улучшений системы и окончательный вариант модели с результатами.

    курсовая работа [79,2 K], добавлен 25.06.2011

  • Теория алгоритмов

    Нормальный алгоритм Маркова. Тезис Маркова и машина Тьюринга. Гипотеза теории алгоритмов. Алгоритмически неразрешимые проблемы. Задача эквивалентности двух слов в ассоциативном исчислении. Задача распознавания выводимости. Линейная оценка сложности.

    методичка [57,0 K], добавлен 06.07.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены