Cтраница 3
Следует отметить, что принадлежность массовой задачи к классу NP вовсе не означает, что конкретные задачи ( называемые в общей теории сложности индивидуальными задачами или индивидуальными реализациями) не могут быть решены точно или приближенно с любой заранее заданной точностью. При оценке временной сложности приходится рассчитывать на наихудшую из индивидуальных задач. [31]
В частности, группы внешних гомологии и когомологий не образуют гомологического ( когомологического) функтора, что делает их вычисление на настоящий момент достаточно индивидуальной задачей. С другой стороны, существенная часть геометрической информации содержится именно во внешних когомологиях, как показывает один из основных результатов работы ( теорема 3.4): классы Черна неприводимых представлений конечной группы G содержатся во внешних когомологиях группы G, более точно - в их образе при каноническом гомоморфизме. [32]
Всем пригодятся более легкий доступ к информации, способность гибкого переноса данных из приложения в приложение, процессы и процедуры, приспособленные к решению индивидуальных задач. [33]
На наш взгляд, это должно облегчить химику-аналитику подбор интересующей его оригинальной литературы, ознакомление с которой необходимо для решения сложных, в каждом случае индивидуальных задач современной аналитической химии. [34]
Коллективный и динамичный характер труда проектировщиков в ряде случаев делает необходимой интерактивную групповую работу пользователей с КТС САПР в процессе решения общей задачи или при одновременном решении нескольких индивидуальных задач. [35]
Саймоном и широко используемое в современной теории организации для обозначения процесса, в результате которого работник, вновь поступивший в развитую организацию, через определенное время принимает ее цели, начинает рассматривать индивидуальные задачи через их призму и проявляет готовность добровольно, самостоятельно и без принуждения извне предпринимать действия или принимать решения, направленные на удовлетворение интересов и достижение целей организации. При этом принятые им решения он воспринимает не как навязанные, а как соответствующие его побуждениям и собственной мотивации. [36]
Для нас, однако, важнее математические задачи, встающие перед исследователем, желающим вычислить тайный ключ для дешифровки по явному ключу для шифровки, поскольку даже при неизвестном или отсутствующем общем алгоритме индивидуальные задачи могут поддаваться эффективному решению. [37]
С учетом компьютерных технологий, освоенных студентами, и в силу широкого хождения в студенческой среде характерных вариантов дипломных проектов, выполненных в университете в течение последних трех - пяти лет, особое значение для формирования инженерного статуса выпускника приобретает разработка и решение студентами в ходе дипломного проектировании индивидуальных задач, направленных на совершенствование технологических процессов. [38]
Из результатов теории сложности следуют важные практические рекомендации: 1) приступая к решению некоторой комбинаторной задачи, необходимо сначала проверить, не принадлежит ли она к классу NP-полных задач, и если это так, то не следует тратить усилия на разработку алгоритмов и программ точного решения; 2) отсутствие эффективных алгоритмов точного решения массовой задачи выбора отнюдь не означает невозможности эффективного решения индивидуальных задач из класса NP-полных или невозможности получения приближенного решения по эвристическим алгоритмам за полиномиальное время. [39]
Например, недетерминированный алгоритм решения задачи коммивояжер можно было бы построить, используя в качестве стадии угадывания просто выбор произвольной последовательности городов, а в качестве стадии проверки упомянутую, полиномиальную процедуру и проверку доказательства для задачи коммивояжер. Очевидно, для любой индивидуальной задачи / найдется такая догадка S, что результатом работы стадии проверки на входе ( /, 5) будет да в том и только в том случае, если для индивидуальной задачи / существует маршрут искомой длины. [40]
По крайней мере один из параметров переборной задачи ( например, ее размерность) неограничен. Таким образом, число индивидуальных задач в классе бесконечно. Индивидуальные задачи класса - переборной задачи - различаются исходными данными - значениями численных параметров условий задачи. [41]
Стало быть, динамическое планирование могло теперь быть применено к отдельным задачам одной программы. Смесь планируемых исполняемых единиц могла включать индивидуальные задачи или подмножества задач различных программ, возможно, принадлежащих к разным заданиям. [42]
Клинтон постоянно заявляет, что обязанностью каждого американца является рост над собой. Тем самым происходит как бы социализация индивидуальных задач, в результате чего общественный климат становится более позитивным как для самого лидера, так и для отдельного человека. [43]
Вторая ситуация может возникнуть, например, если в задаче коммивояжера в качестве дополнительного параметра фигурирует число В и требуется найти все маршруты длины, не превосходящей В. Для этого достаточно легко можно построить индивидуальную задачу коммивояжера, в которой имеется экспоненциальное число маршрутов, длина которых не превосходит В. Тогда, положив В md ( Ck, С /), получим искомый пример. Следовательно, в этой ситуации не существует алгоритма с полиномиальной временной сложностью, который перечисляет все решения. [44]
Теория информационной сложности класса задач предусматривает идентификацию индивидуальной задачи класса в процессе Диалога. Число шагов диалога, позволяющее выделить любую индивидуальную задачу класса, и определяет информационную сложность класса. В теории информационной сложности задача класса считается решенной, как только она идентифицирована. Каждой задаче класса соответствует решение, записанное, например, в таблице, входами которой служат исходные данные задачи. [45]