Теория сложности вычислений
Материал из MachineLearning.
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Теория сложности вычислений — раздел теории вычислений, изучающий объем работы, требуемой для решения вычислительной проблемы.
Задача рассматривается как сложная, если решение проблемы требует большого количества ресурсов, независимо от алгоритма, используемого для ее решения. Теория формализует это интуитивное понятие, вводя математические модели вычислений для изучения этих проблем и количественной оценки объема ресурсов, необходимых для их решения, такие как время и используемая память. Возможны и другие меры сложности, такие как: количество сообщений (коммуникационная сложность), число элементов в схеме из функциональных элементов (схемная сложность) и количество процессоров. В частности, теории сложности вычислений определяет практические ограничения на то, что компьютеры могут и что не могут делать.
Тесно связаны с теорий сложности вычислений анализ алгоритмов и теория вычислимости. Основное различие между теорией сложности вычислений и анализом алгоритмов является то, что последняя посвящена анализу объема ресурсов, необходимых определенному алгоритму, чтобы решить проблему, в то время как первая задает вопрос более общего характера о всех возможных алгоритмах, которые могут быть использованы чтобы решить ту же проблему. Более точно, теория сложности вычислений пытается классифицировать проблемы, которые могут или не могут быть решены надлежащим количеством ограниченных ресурсов. В свою очередь, введение ограничений на имеющиеся ресурсы — это то, что отличает теорию сложности вычислений от теории вычислимости: последняя спрашивает какие проблемы могут быть решены в принципе алгоритмически, не ограничивая вычислительные ресурсы.
Содержание |
Вычислительные проблемы
Экземпляры задач
Вычислительные проблемы(задачи) можно рассматривать как бесконечный набор пар: (экземпляр задачи, решение для данного экземпляра). Входной строкой для вычислительной проблемы является строка, описывающая экземпляр задачи. Выходная строка для вычислительной проблемы — описание решения для экземпляра задачи, описанного входной строкой. Например, проблема распознавания простоты числа: экземпляр задачи — число, для которого следует определить простое оно или нет, решение — строка «да», если это число простое и «нет» в противном случае. Теория сложности вычислений рассматривает только массовые задачи, т.е. требование о бесконечности набора экземпляров задач обязательно.
Представление задачи
При рассмотрении вычислительных задач описанием экземпляра задачи является строка над алфавитом. Как правило, алфавит берется бинарным(т. е. множество {0,1}). Различные математические объекты должны быть соответствующим образом закодированы. Так, например, целые числа могут быть представлены в двоичной системе счисления, и графы могут быть закодированы непосредственно через их матрицы смежности или через их кодирование списков смежности в двоичной системе.
Задачи распознавания
Задачи распознавания является одним из центральных объектов исследования в теории сложности вычислений. Задача распознавания является особым типом вычислительных проблемы, ответом на которую является либо "да" или "нет"(1 или 0). Задачу распознавания можно сформулировать в виде задачи принадлежности входной строки к некоторому подмножеству (языку) множества всех входных строк. Входная строка проблемы принадлежит соответствующему языку тогда и только тогда, когда ответом на эту строку является «да». Таким образом задача распознавания — это задача распознавания принадлежности входной строку к некоторому языку.
Пример задачи распознавания. Входная строка: описание произвольного графа. Проблема состоит в решении вопроса связен ли данный граф или нет. Язык связных графов — это множество описаний всех связных графов. Для получения точного определения этого языка, нужно решить, как графы кодируются как бинарных строки.
Задачи поиска
Задачей поиска является вычислительная задача, где выходное значение является более сложным, чем в задаче распознавания (то есть, это не просто «да» или «нет»).
Примером задачи поиска является задача коммивояжера. Задача коммивояжёра (коммивояжёр — бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Входная строка: описание взвешенного (т.е. с числовыми пометками на ребрах) графа. Выходная строка — описание оптимального маршрута коммивояжёра.
Существует парная зависимость между задачами распознавания и задачами поиска. Задачу поиска можно сформулировать в качестве задачи распознавания. Например, для задачи поиска «умножение двух чисел», соответствующая парная задача распознавания может быть представлена как множество троек (A, B, C) таких, что отношения A × B = C выполнено.
Измерение сложности
Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения, объём необходимой памяти и т.д.) в зависимости от размера входа и выхода.
Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размера входных данных, но и от самих данных. Например, количество операций алгоритма сортировки вставками значительно меньше в случае, если входные данные уже отсортированы. Чтобы избежать подобных трудностей, рассматривают понятие временной сложности алгоритма в худшем случае.
Временная сложность алгоритма (в худшем случае) — это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера. В задачах, где размер выхода не превосходит или пропорционален размеру входа, можно рассматривать временную сложность как функцию размера только входных данных.
Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).
По аналогии с временной сложностью, определяют пространственную сложность алгоритма, только здесь говорят не о количестве элементарных операций, а об объёме используемой памяти.
Несмотря на то, что функция временной сложности алгоритма в некоторых случаях может быть определена точно, в большинстве случаев искать точное её значение бессмысленно. Дело в том, что во-первых, точное значение временной сложности зависит от определения элементарных операций (например, сложность можно измерять в количестве арифметических операций или операций на машине Тьюринга), а во-вторых, при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным.
Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма. При этом алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных, за исключением лишь, возможно, данных малого размера.
Сложность определяется исходя из вычислительной модели, в которой проводят вычисления.
Вычислительные модели
Существует множество различных моделей вычислений: машина Поста, машина Минского, лямбда-исчисление, частично рекурсивные функции, нормальные алгоритмы Маркова, машины с произольным доступом к памяти (RAM машины) и др. Упомянем лишь наиболее популярную вычислительную модель — машину Тьюринга.
Машина Тьюринга
Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара (ленточный символ — состояние), для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.
Модель машины Тьюринга допускает различные расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями; машины, использующие источник случайности.
Машина Тьюринга является одной из основных моделей вычисления в теории сложности.
