Автор: Пользователь скрыл имя, 21 Октября 2011 в 14:54, контрольная работа
Алан Тьюринг может быть причислен к плеяде составляющих гордость человечества величайших математических и философских умов, таких, как Р.Декарт, Г.В. Лейбниц, Б.Рассел, Д.Гильберт, А.Витгенштейн. Удивительно, сколь злую шутку сыграло с Тьюрингом его полное безразличие к борьбе за приоритет в научных открытиях: вплоть до недавнего времени его место в истории развития научных и инженерных идей представлялось очень неполно, если не сказать однобоко (и не в последнюю очередь благодаря некоторым американским историкам науки, тщательно заботившимся об абсолютизации своего национального приоритета в создании компьютеров, да и пожалуй, в создании всей информатики).
Введение……………………………………………………………………....3
1.Тьюринг Алан Матисон – биография……………………………………..4
2. Описание машины Тьюринга……………………………………………..4
3. Свойства машины Тьюринга как алгоритма……………………………..6
4. Сложность алгоритмов…………………………………………………….7
5. Сложность проблем………………………………………………………..8
6. Машина Тьюринга и алгоритмически неразрешимые проблемы……...10
Заключение…………………………………………………………………...13
Список использованной литературы………………………………………..14
в) Логическая неразрешимость (в смысле теоремы Гёделя о неполноте)
Проблема 5: Проблема "останова" (см. теорема);
Проблема 6: Проблема эквивалентности алгоритмов;
По двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.
Проблема 7: Проблема тотальности;
По
произвольному заданному
Заключение
Теория сложности также классифицирует и сложность самих проблем, а не только сложность конкретных алгоритмов решения проблемы. Теория рассматривает минимальное время и объем памяти, необходимые для решения самого трудного варианта проблемы на теоретическом компьютере, известном как машина Тьюринга. Машина Тьюринга представляет собой конечный автомат с бесконечной лентой памяти для чтения записи и является реалистичной моделью вычислений.
Задачи можно разбить на классы в соответствии со сложностью их решения. Вот важнейшие из них и предполагаемые соотношения между ними:
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