Автор: Пользователь скрыл имя, 13 Февраля 2012 в 15:10, курсовая работа
Данная курсовая работа состоит из двух частей. Первая содержит описание машины Тьюринга и ее свойств, описание сложностей алгоритмов и проблем. Вторая часть состоит из решения задачи: нахождения произведения двух чисел.
ВВЕДЕНИЕ
I ГЛАВА: ОПИСАНИЕ ………………………….....………………………2
1. ОПИСАНИЕ МАШИНЫ ТЬЮРИНГ…………………………………………………3
1.1 СВОЙСТВА МАШИНЫ ТЬЮРИНГА КАК АЛГОРИТМА……..…..…..……………..5
2. СЛОЖНОСТЬ АЛГОРИТМОВ …………………………………………………7
2.1 СЛОЖНОСТЬ ПРОБЛЕМ………………………………………..………………..9
3. МАШИНА ТЬЮРИНГА И АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ..........12
II Глава :Решение задачи…………………..…………………..……..………....19
ЗАКЛЮЧЕНИЕ …………………………..………………………………21
СПИСОК ЛИТЕРАТУРЫ …………………………………………………….23
Задачи можно разбить на классы в соответствии со сложностью их решения. Вот важнейшие из них и предполагаемые соотношения между ними:
P<=NP<=EXPTIME
Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (это вариант обычной машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно угадывая”, либо перебирая все предположения параллельно – и проверяет свое предположение за полиномиальное время.
Класс NP включает в себя класс P, поскольку любую задачу, решаемую за полиномиальное время на детерминированной (обычной) машине Тьюринга, можно решить и на недетерминированной за полиномиальное время, просто этап предположения опускается.
Если все задачи класса NP решаются за полиномиальное время и на детерминированной машине, то P=NP. Тем не менее, никем не доказано, что P<>NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что это классы неравны.
Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что и любая задача этого класса. Такие задачи называются NP-полными. То есть, если такая задача решается за полиномиальное время, то P=NP.
1. Рощин А.Г., Половов Р.М. Теория автоматов. Часть I. Тексты лекций - Москва: МГТУ ГА, 2001. - 76 с.
2. Фалевич Б.Я. Теория алгоритмов. – М.: ИНФРА-М, 2006. – с.324.
3. Фалина Н.М. Машина Тьюринга // Информатика. - №26. – 2005. – с.12-15