Cтраница 1
Переборные задачи возникают в различных областях дискретной математики и формулируются на языке той области, в которой они изучаются. Для удобства анализа целесообразно кодировать дискретные задачи ( математические объекты и отношения между ними) словами в некотором алфавите. Чаще всего для этого используется двоичная система счисления. Число символов, необходимых для записи условий задачи, - определяет размерность задачи. [1]
Переборными задачами оказываются также задачи выяснения: совместности системы целочисленных линейных неравенств ( как в смысле существования целочисленного, так и вещественного, решений), задача коммивояжера и многие другие - грубо говоря, все дискретные задачи. [2]
Решение переборной задачи не предусматривает диалога для выделения индивидуальной задачи. За один вопрос или за 1 ( х) вопросов конкретная задача идентифицируется, и остается обратиться к таблице, где перечислены ответы. [3]
Различают два типа переборных задач: экстремальные задачи и задачи распознавания свойств. Требуется найти значение x G, при котором / () достигает экстремума. В задачах распознавания свойств требуется определить, обладает ли функция f ( x) дискретного переменного л некоторым фиксированным свойством. Поскольку область G определения экстремальной задачи задается некоторым свойством х, описываемым, например, системой равенств или неравенств, то распознавание свойств является этапом решения экстремальной задачи. [4]
В процессе декомпозиции приходится решать и переборные задачи. В настоящее время в CONGEN включена возможность генерации всех стереоизомеров заданной структуры. [5]
По крайней мере один из параметров переборной задачи ( например, ее размерность) неограничен. Таким образом, число индивидуальных задач в классе бесконечно. Индивидуальные задачи класса - переборной задачи - различаются исходными данными - значениями численных параметров условий задачи. [6]
Показано, кроме того, что много естественных переборных задач ( например, задача коммивояжера, классические задачи теории расписаний, задача о раскраске, задача о покрытии и ряд других известных комбинаторных и дискретных экстремальных задач) являются универсальными. В работе Л. А. Левина [49] было приведено шесть универсальных задач. В последние годы число задач, универсальность которых была установлена, быстро увеличивалось. В настоящее время известно более 2000 универсальных задач. Четко изложенная в [36] техника полиномиальной сводимости позволяет надеяться на то, что класс универсальных задач вскоре еще более расширится. [7]
Проблема выяснения простоты числа N считается пока переборной задачей. [8]
В общем случае это может оказаться достаточно сложной переборной задачей. [9]
Теория информационной сложности задач управления и теория вычислительной сложности переборных задач отражают разные аспекты сложности классов задач. [10]
Ясно, что нет проблемы в построении алгоритма решения; переборной задачи А. В результате после просмотра конечного числа слов у будет найдено, решение либо можно будет убедиться, что его нет. При сколько-нибудь заметных 1 ( х) это число фантастически велико и указанный перебор практически неосуществим. С полным основанием можно считать, что только полиномиальные, алгоритмы ( да и то не все) могут претендовать на практическую ценность. Поэтому основной вопрос, возникающий при теоретическом исследовании переборной задачи, - этот вопрос о том, является ли она полино. [11]
Единственное нетривиальное использование квантовых свойств для вычислений, которое мы уже рассмотрели, - это решение универсальной переборной задачи алгоритмом Гровера, изложенным в разделе 8.1. К сожалению, при этом достигается лишь полиномиальное ускорение. Поэтому никаких серьезных следствий для теории сложности вычислений ( типа BQP D ВРР) алгоритм Гровера не дает. В настоящее время нет доказательства того, что квантовые вычисления превосходят по скорости классические вероятностные. Но есть косвенные свидетельства в пользу такого утверждения. Первое из них - пример задачи с оракулом ( т.е. процедурой типа черного ящика), для которой существует полиномиальный квантовый алгоритм, в то время как любой классический вероятностный алгоритм экспоненциален. В дальнейшем мы решим также задачу о скрытой подгруппе в TLk, обобщающую все результаты из этого раздела. [12]
Алгоритмы ветвей и границ, как и большая часть алгоритмов, описанных ранее, применяются для решения переборных задач. В целях упрощения понимания сути алгоритмов такого рода рассмотрим одну конкретную задачу, в которой такой алгоритм весьма хорошо работает и достаточно прост в понимании. [13]
Подчеркнем, что центральный теоретический вопрос, возникающий в связи со сказанным, вопрос о том, существуют ли полиномиально неразрешимые переборные задачи или все переборные задачи полиномиально разрешимы, до сих пор не решен. Практическое значение решения этого вопроса трудно переоценить. [14]
Подчеркнем, что центральный теоретический вопрос, возникающий в связи со сказанным, вопрос о том, существуют ли полиномиально неразрешимые переборные задачи или все переборные задачи полиномиально разрешимы, до сих пор не решен. Практическое значение решения этого вопроса трудно переоценить. [15]