Предисловие переводчика
Скачать 243.75 Kb.
|
Сложность вычислений: функции, вычислимые на практикеВо время второй мировой войны Тьюринг помогал проектировать специальное вычислительное устройство, называемое Bombe. Он использовал его, чтобы взломать немецкий код “Энигма”. К 1960 году компьютеры были распространены в промышленности и университетах. Постепенно были изобретены алгоритмы для множества задач, и математики начали классифицировать алгоритмы в соответствии с их эффективностью и искать наилучшие алгоритмы для конкретных проблем. Это послужило началом современной теории вычислений. В этом разделе мы обратимся к сложности взамен вычислимости, и все машины Тьюринга, которые мы будем рассматривать, будут останавливаться на своих входах. Вместо того, чтобы рассматривать множество входов, на которых машина останавливается, мы будем рассматривать множество входов, на котором машина Тьюринга выдает 1. Для везде определенной машины Тьюринга M мы определим множество входов, которые она принимает, как L(M) = {n | M(n) = 1} . Время, требующееся алгоритму, зависит от входа и машины, на котором он выполняется. Хорошей мерой сложности алгоритма является асимптотическая функция времени в худшем случае (как функция от длины входа, n). Для входа w обозначим n = |w|. Следуя [Hartmanis, 1989], мы говорим, что машина Тьюринга M работает за время T(n) , если для всех w длины n, вычисление M(w) требует максимум T(n) шагов, а затем машина останавливается. Это так называемая функция времени в худшем случае, так как машина может работать на каком-нибудь входе длины n. Для всякой функции T : N → N, пусть TIME[T(n)] = { A | A = L(M) для какой-нибудь машины M, работающей T(n)} Алан Кобхэм и Джек Эдмондс определили класс сложности P как все задачи, решаемые за полиномиальное время, и это отличное математическое определение задач, решаемых на практике P = ∪i=1,2,… TIME[ni ] Всякая задача, не принадлежащая классу P, конечно неосуществима. С другой стороны, у задач, принадлежащих этому классу, обычно есть осуществимые алгоритмы. Кроме P было изучено много других важных классов, некоторые из них это NP, PSPACE, и EXPTIME. PSPACE состоит из задач, решаемых на полиномиальной памяти. EXPTIME - множество задач, решаемых за время 2p(n) для некоторого полинома p. Возможно, один из самых интересных описанных выше классов – это NP. Недетерминированная машина Тьюринга, N, выбирает между двумя возможными действиями на каждом шаге. Если на входе w некоторая последовательность шагов приводит к тому, что это вход принимается, тогда мы говорим, что N принимает w, и мы говорим, что недетерминированное время, необходимое N на входе w – это всего лишь количество шагов в последовательности, которая ведет к принятию w. Мы не учитываем длины всех возможных последовательностей шагов, только той, которая ведет к принятию. NP иногда определяется как класс проблем S, которые имеют короткие доказательства принадлежности множеству. Например, нам дано множество из m больших натуральных чисел a1, …, am и число t. Проблема Subset Sum формулируется следующим образом: существует ли подмножество данного нам множества, члены которого в сумме дают ровно m? Эту задачу легко решить с помощью недетерминированной машины Тьюринга: для каждого i мы решаем, включить ai в подмножество или нет. Затем мы суммируем все числе в подмножестве и проверяем, равна ли сумма t. Тем самым, недетерминированное время линейно зависит от длины входа. Однако, не известно (детерминированного) алгоритма, который бы решал эту задачу за менее чем экспоненциальное время. Алгоритмы хорошо изучены, и известна сложность многих задач. В частности, было определено сведение одной задачи к другой, что используется для сравнения сложности задач. Неформально, можно сказать, что A сводится к B (A ≤ B), если существует простое преобразование τ, которое преобразует элементы A в элементы B, так что τ(w) ∈ B ⇔ w ∈ A. Довольно большое число задач оказываются полными для одного из выше описанных классов (Задача A полна для класса сложности C, если  , и все остальные задачи этого класса не сложнее, чем A. Две полные задачи одного и того же класса имеют одинаковую сложность.)Причина существования полных проблем непонятна. Одно из возможных объяснений состоит в том, что естественные задачи в каком-то смысле выполняют роль универсальных машин Тьюринга. Универсальная проблема в определенном классе сложности может заменить любую другую. Причина того, что класс NP хорошо изучен, состоит в том, что многие задачи принадлежат NP, включая Subset Sum. Ни одна из этих проблем не имеет известного полиномиального алгоритма, хотя некоторые NP-полные задачи имеют приближенные решения. Многое еще неизвестно о сложности вычислений. Мы знаем, что строго большее количество вычислительных ресурсов позволяет нам решать строго более сложные задачи. Однако, с разными вычислительными ресурсами все не так просто. Очевидно, что P содержится в NP. Далее, NP содержится в PSPACE, поскольку в PSPACE мы можем систематически пробовать каждую ветвь NP вычислений. PSPACE содержится в EXPTIME, поскольку, если для PSPACE требуется более, чем полиномиальное число шагов, то одна и та же конфигурация встретится дважды, и работа машины зациклится. Вот известные отношения между классами: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME И хотя кажется очевидным, что все эти неравенства строгие, ни одно из них не было доказано. Единственное, что было доказано – это то, что P строго содержится в EXPTIME. Оставшиеся задачи – это фундаментальные нерешенные задачи теории сложности вычислений. |
Похожие:
 | Предисловие Предисловие переводчика Утверждение тем рефератов по истории отрасли науки для сдачи кандидатского экзамена по дисциплине «История и философия науки» | | Книга Пяти Колец предисловие переводчика япония при жизни Мусаси Традиционная власть императора была свергнута в XII веке, и, хотя каждый наследный император |
 | Абу ма'шар краткое введение в науку о приговорах звезд предисловие переводчика Федеральное агентство по образованию российской федерации фгоу впо «южный федеральный университет педагогический иститут» | | Предисловие переводчика Человечеству сил, преследующих собственные цели, одной из тактических задач которых является порабощение людей во всемирном масштабе... |
| Предисловие переводчика Так что не удивляйтесь когда к вам подсядет долговязый парень, или заглянет через плечо мужчина средних лет с бородкой. Читать кого-то... | | Предисловие переводчика Так что не удивляйтесь когда к вам подсядет долговязый парень, или заглянет через плечо мужчина средних лет с бородкой. Читать кого-то... |
| Программа по формированию навыков безопасного поведения на дорогах... ... | | Ложные друзья переводчика Динамическая эквивалентность как способ преодоления различий в национальных картинах мира |
| Перевод И. И. Городинского От переводчика Курсовая работа по дисциплине «Бухгалтерский учет» выполняется студентами в соответствии с учебным планом на завершающем этапе обучения... | | Электронный русско-англо-китайский переводчик rec-4510v подробная... Вид переводчика в открытом положении и коментарии к функциям клавиш |
| Календарно-тематическое планирование Информатика и икт 10 класс ... | | Урок французского и русского языков на тему: «Путешествие в страну Лингвинию» Цель урока: познакомить учащихся с такими понятиями как «языковые параллели» и «ложные друзья переводчика» |
| Ресурсы интернета для переводчика Все ссылки (и некоторые названия ресурсов) являются интерактивными – при нажатии и удержании клавиши и щелчке по левой клавише мыши... | | Программа по формированию навыков безопасного поведения на дорогах... Выставка книг 95 лет со дня рождения русского поэта и переводчика Бориса Владимировича Заходера (1918-2000) |
| Программа подготовки переводчика в сфере профессиональной коммуникации ... | | Темы для работы в группе ас выздоровление продолжается… Предисловие 2 |
