Теория сложности вычислений

Материал из MachineLearning.

Перейти к: навигация, поиск
Данная статья является непроверенным учебным заданием.
Студент: Участник:DmitryKonstantinov
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Теория сложности вычислений — раздел теории вычислений, изучающий объем работы, требуемой для решения вычислительной проблемы.

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

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

Содержание

Вычислительные проблемы

Экземпляры задач

Вычислительные проблемы(задачи) можно рассматривать как бесконечный набор пар: (экземпляр задачи, решение для данного экземпляра). Входной строкой для вычислительной проблемы является строка, описывающая экземпляр задачи. Выходная строка для вычислительной проблемы — описание решения для экземпляра задачи, описанного входной строкой. Например, проблема распознавания простоты числа: экземпляр задачи — число, для которого следует определить простое оно или нет, решение — строка «да», если это число простое и «нет» в противном случае. Теория сложности вычислений рассматривает только массовые задачи, т.е. требование о бесконечности набора экземпляров задач обязательно.

Представление задачи

При рассмотрении вычислительных задач описанием экземпляра задачи является строка над алфавитом. Как правило, алфавит берется бинарным(т. е. множество {0,1}). Различные математические объекты должны быть соответствующим образом закодированы. Так, например, целые числа могут быть представлены в двоичной системе счисления, и графы могут быть закодированы непосредственно через их матрицы смежности или через их кодирование списков смежности в двоичной системе.

Задачи распознавания

Задачи распознавания является одним из центральных объектов исследования в теории сложности вычислений. Задача распознавания является особым типом вычислительных проблемы, ответом на которую является либо "да" или "нет"(1 или 0). Задачу распознавания можно сформулировать в виде задачи принадлежности входной строки к некоторому подмножеству (языку) множества всех входных строк. Входная строка проблемы принадлежит соответствующему языку тогда и только тогда, когда ответом на эту строку является «да». Таким образом задача распознавания — это задача распознавания принадлежности входной строку к некоторому языку.

Пример задачи распознавания. Входная строка: описание произвольного графа. Проблема состоит в решении вопроса связен ли данный граф или нет. Язык связных графов — это множество описаний всех связных графов. Для получения точного определения этого языка, нужно решить, как графы кодируются как бинарных строки.

Задачи поиска

Задачей поиска является вычислительная задача, где выходное значение является более сложным , то есть, это не просто да или нет.

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

Существует парная зависимость между задачами распознавания и задачами поиска. Задачу поиска можно сформулировать в качестве задачи распознавания. Например, для задачи поиска «умножение двух чисел», соответствующая парная задача распознавания может быть представлена как множество троек (A, B, C) таких, что отношения A × B = C выполнено.

Измерение сложности

Вычислительные модели

Классы сложности

Открытые проблемы

Ссылки

Личные инструменты