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

Скачать

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

Размер: 1,5 M
Тип: курсовая работа
Категория: ПРОГРАММИРОВАНИЕ
Скачать

Другие файлы:

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

Исследование экономико-математических моделей
Оценка адекватности эконометрических моделей статистическим данным. Построение доверительных зон регрессий спроса и предложения. Вычисление коэффициен...

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

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

Эконометрика.
М.: Изд-во Рос. экон. акад., 2002. — 640 с. В рамках учебной дисциплины `Эконометрика` рассмотрены проблемы построения эконометрических м...


Краткое сожержание материала:

Размещено на

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

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

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

РЕФЕРАТ

Отчет по курсовой работе содержит: 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

...