Cтраница 1
Принадлежность задачи о паросочетаниях классу NP очевидна: Мерлину достаточно разбить мальчиков и девочек на пары, после чего Артур сможет убедиться, что пар ровно п и все выбранные пары согласны танцевать. [1]
Принадлежность задачи множеству ЖР-трудпых задач является одной из важных ее характеристик. [2]
Принадлежность задачи классу NP требует, чтобы мы могли проверить предложенное решение за полиномиальное время. Видно, что описанный алгоритм действительно подсчитывает суммарный штраф. Анализ временной сложности показывает, что цикл while совершает не более N проходов; максимум достигается, если значение переменной currentPenalty не превышает предельное. [3]
Принадлежность задач 1 и 2 классу показана соответственно в примерах 10.4 и 10.3. Аналогично для каждой из остальных задач надо построить недетерминированную машину Тьюринга ( или, если читателю угодно, недетерминированную РАМ) полиномиальной сложности, которая угадывает решение и проверяет, что это действительно решение. Детали оставляем в качестве упражнения. [4]
Докажем принадлежность задачи ПРОСТОТА ЧИСЛА классу NP, построив для решения этой задачи недетерминированную машину Тьюринга JV, которая рекурсивно вызывает саму себя. [5]
Установление принадлежности задачи классам Р, NP или ее NP-полноты является важной характеристикой сложности задачи. Более того, полиномиальный алгоритм решения задачи ЛП на практике дает худшие результаты, чем симплекс-метод, обладающий экспоненциальной временной сложностью. Таким образом, состояние теории в настоящее время не позволяет указать универсальные количественные и даже качественные оценки эффективности вычислительных алгоритмов. Такие оценки дает лишь вычислительная практика. [6]
В ряде случаев, однако, оказывается необходимым не только определить принадлежность задачи к тому или иному подклассу, но и расчленить комплексную задачу на составные части. В этом проявляется наиболее сложная функция работы алгоритма-анализатора. [7]
Следует отметить, что в ряде случаев бывает достаточно трудно определить принадлежность задачи идентификации к одной из перечисленных выше категорий. Понятие достаточности экспериментального множества напрямую связано со сложностью системы, подлежащей идентификации. Проблема может быть решена путем последовательной многократной реализации всех этапов процедуры идентификации с целью получения наиболее полного представления о характеристиках исследуемой системы. [8]
Метод анализа, основанный на декомпозиции целей системы позволяет определить состав ее задач, принадлежность задач к определенным элементам функциональной структуры ( см. разд. [9]
На основе приведенных выше уравнений для теплового расчета теплообменных аппаратов, а также для определения коэффициентов теплоотдачи и теплопередачи, могут быть разработаны практические приемы решения различных задач теплового расчета трубчатых теплообменников. Все эти задачи могут быть сведены к трем основным типам, обозначаемым соответственно как задачи конструктивного, проверочного и режимного расчета. Принадлежность задачи к тому или иному типу определяется перечнем известных и искомых величин в дайной задаче, а их количество - структурой системы основных уравнений теплового расчета теплообменников при стационарном режиме. [10]
Любопытен открытый пока вопрос: верно ли, что R P. Заманчиво ответить на него да, исходя из философских соображений, что случайное бросание монеты не может принести много пользы, когда ответ должен быть определенным - да или нет. С ним связан другой вопрос: является ли вероятностный алгоритм ( показывающий принадлежность задачи классу R) для. В конце концов, вероятностные алгоритмы можно выполнять, используя генераторы псевдослучайных, чисел, имеющиеся для большинства компьютеров, и вероятность ошибки 2 - 100 пренебрежимо мала. [11]
Проектные работы начинаются с выявления перечня функциональных задач управления, в том числе подлежащих машинному решению. Устанавливается их назначение, выявляются входные и выходные характеристики, а также экономико-методологические принципы решения. Важно выделить задачи учета затрат на производство из задач других участков учета и подсистем. Разграничение задач не противоречит принципам интегрированной обработки данных. Наоборот, детальная классификация задач способствует организации слаженного взаимодействия информации, помогает избежать дублирования расчетов, осуществить об снован-ное раздельное проектирование, определить очередность разработок и внедрения проекта. Принадлежность задачи к той или иной классификационной группировке помогает определять характер ее взаимосвязей. [12]