Образовательный портал «Кафедра онлайн» НИЯУ «МИФИ», Обнинск"

Главная » Рубрики » Блог студентов » Теория алгоритмов и сложность вычислений

Теория алгоритмов и сложность вычислений

Д.К. Легчиков,  магистрант ИАТЭ НИЯУ «МИФИ», Обнинск

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив кару города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы.
Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.
Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.

О-нотация

Для оценивания трудоемкости алгоритмов была введена специальная система обозначений – так называемая О-нотация.  Эта нотация позволяет учитывать в функции f (n) лишь наиболее значимые элементы, отбрасывая второстепенные.
Например, в функции  f (n) = 2n2 + n – 5 при достаточно больших  n  компонента  n2  будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида  О(n2 ).
Аналогично, для функции  f (n) = 2n + 3n3 – 10  начиная с некоторого  n  первое слагаемое будет превосходить второе и поэтому данную функцию можно описать оценкой  О(2n).
Важность О-оценивания состоит в том, что оно позволяет описывать характер поведения функции f(n) с ростом n: насколько быстро или медленно растет эта функция.
О-оценка позволяет разбить все основные функции на ряд групп в зависимости от скорости их роста:

  1. постоянные функции типа О(1), которые с ростом n НЕ растут (в оценивании алгоритмов этот случай встречается крайне редко, но все-таки встречается!)
  2. функции с логарифмической скоростью роста О(log 2 n)
  3. функции с линейной скоростью роста О(n)
  4. функции с линейно–логарифмической скоростью роста О(n*log 2 n)
  5. функции с квадратичной скоростью роста О(n2 )
  6. функции со степенной скоростью роста  О(na) при а>2
  7. функции с показательной или экспоненциальной скоростью роста  О(2n)
  8. функции с факториальной степенью роста  О(n!)

 

Отсюда можно сделать несколько выводов.

  1. При выборе однотипных алгоритмов предпочтение (при прочих равных условиях) следует отдавать алгоритмам с наименьшей скоростью роста трудоемкости, поскольку они позволят за одно и то же время решить задачи с большей размерностью
  2. Если заранее известно, что размерность решаемых задач невелика, но зато число их повторений очень большое, имеет смысл рассмотреть возможность использования алгоритмов не с самой лучшей оценкой, поскольку при малых n “лучшие” алгоритмы могут вести себя хуже, чем “плохие” (это можно заметить по графику в области начала координат)
  3. Алгоритмы класса О(2n) и О(n!) следует использовать с большой осторожностью, учитывая катастрофический рост их трудоемкости уже при n>100. Например, если число базовых операций определяется соотношением 2n, то при n=100 это число будет примерно равно 1030, и если одна базовая операция выполняется за 1 микросекунду, то это потребует около 1024 секунд, т.е. порядка 1016 лет. К сожалению, задачи с подобной трудоемкостью довольно часто встречаются на практике и их точное решение пока невозможно даже на сверхбыстрых суперкомпьютерах!
Сложность вычислений

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

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

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

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

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

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

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

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

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

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

Класс P

Класс P (от англ. polynomial) — множество задач распознавания, которые могут быть решены на детерминированной машине Тьюринга за полиномиальное от длины входа время. Аналогично, для задач поиска определяется класс FP (от англ. functional polynomial).

Примерами задач из класса P являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, выяснение связности графов, сортировка множества из n чисел, нахождение эйлерова цикла на графе из m рёбер, обнаружение в тексте длиной n некоторого слова, построение покрывающего дерево минимальной стоимости, линейное программирование и некоторые другие.

Класс NP

Классом NP (от англ. non-deterministic polynomial) называют множество задач распознавания, время решения которых существенно зависит от размера входных данных; в то же время, существует алгоритм, который, получив наряду с описанием входных значений, некоторые дополнительные сведения (свидетеля решения), может достаточно быстро (за время, не превосходящее полинома от размера данных) решить задачу.

Можно привести много задач, про которые на сегодняшний день неизвестно, принадлежат ли они P, но известно, что они принадлежат NP. Среди них:

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

Среди всех задач класса NP можно выделить «самые сложные» — NP-полные задачи. Если удастся решить любую из них за полиномиальное время, то все задачи класса NP также можно будет решить за полиномиальное время.

Проблема равенства классов P и NP

В конечном счете проблема равенства классов P и NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время)?

Из определения классов P и NP сразу вытекает следствие: P \subseteq NP. Однако до сих пор ничего не известно о строгости этого включения, т.е. существует ли алгоритм, лежащий в NP, но не лежащий в P. Если такого алгоритма не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду с вычислительной точки зрения. Сейчас самые сложные NP-задачи (так называемые NP-полные задачи) можно решить за экспоненциальное время, что почти всегда неприемлемо.

Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. В настоящее время большинство математиков считают, что эти классы не равны. Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение.

Щелкните здесь мышкой, чтобы увидеть полный текст публикации.

1 комментарий

Похожие публикации
 
 

1 комментарий

  1. Дмитрий Легчиков. Теория алгоритмов и сложность вычислений.

 
 

Вы можете оставить комментарий

 





 
 

Выполните простое задание (антиспам). Картинки можно сибирать приблизительно, без точной подгонки фрагментов.


 
 
 

Наверх