Cтраница 3
Мы видим, что уже зарождается теория сложности алгоритмов. Нужно отметить и чисто абстрактное направление в этой теории. Некоторые ученые мерой сложности алгоритма считают сложность наиболее простой из эквивалентных ему машин Тьюринга. [31]
Процесс проектирования систем управления на базе теории сложности состоит в формировании ПОС, множеств эквивалентностей, предпочтений и ЦПС, декомпозиции ЦПС по выбранной эквивалентности и сложности, поиск элементов минимальной или ограниченной сложности. Многие из перечисленных операций в настоящее время еще не формализованы в виде эффективных вычислительных процедур, что затрудняет применение теории в инженерных расчетах. [32]
Мы обсудили начальные понятия нового раздела теории сложности, который объединяет теоретический и численный анализ с целью изучения одного интересного приложения алгоритмов и автоматов и проливает некоторый свет на задачу моделирования неравномерно распределенных случайных величин. Хотя мы получили ответы на ряд вопросов, которые естественным образом возникают в рамках этой теории, многие проблемы остались открытыми. [33]
Рассматривая это предложение с точки зрения теории сложности, мы приходим к некоторым перспективным подходам к числу независимости и к другим NP-трудным задачам в общем случае. [34]
Свойство ( Ь) часто используется в теории сложности; оно явно контрастирует с тем фактом, что Ф ( ] ( х) у является неразрешимым предикатом. Так мы приходим к следующему определению. [35]
Полученные к настоящему времени оценки и результаты теории сложности в значительной мере определяют актуальные направления разработки математических проблем проектирования. [36]
Этим устанавливается двусторонняя связь между теорией аппроксимации и теорией аналитической сложности. [37]
Рабин описывает, какого рода задачи ставит перед собой теория сложности, тогда как Кук, пораженный тем, как много было сделано в этой области после лекции Рабина, дает обстоятельный отчет об исследованиях сложности задач в нескольких проблемных областях. В этих двух работах, вместе взятых, содержится более 90 ссылок на литературу. Наконец, Карп предлагает глубокое обсуждение некоторых важных направлений в контексте его собственной работы и работы его коллег в этой области. Все эти три работы вместе с дополнительным интервью с Карпом позволяют читателю почувствовать себя присутствующим при разработке этих фундаментальных проблем. [38]
Для иллюстрации того, в какой удивительной степени в теории сложности употребляются аналоги теории вычислимости, Ричард Карп построил эту концептуальную карту или головоломку. Чтобы собрать эту головоломку на плоскости, он использует алгоритм для плоских графов. Наиболее удаленные друг от друга части могут при первом рассмотрении казаться независимыми, но в конце концов теория NP-полноты собирает их вместе, говорит Карп. [39]
Недавно в науке начало развиваться новое направление, называемое теорией сложности, теорией эволюции систем, или теорией хаоса. Для понимания исторического процесса этот подход намного полезнее, чем традиционный аналитический. [40]
Этим - устанавливается двусторонняя связь между теорией аппроксимации и теорией аналитической сложности. [41]
Обсуждается метод обмана или соперничества для получения оценок снизу в теории аналитической сложности. В качестве иллюстрации показано, как используется этот метод при получении оценок снизу для алгоритмов отыскания максимума унимодальной функции, нуля скалярной функции, решения интегрального уравнения и аппроксимации скалярной функции. [42]
Наша постановка обладает общностью, позволяющей охватить как частные случаи теории сложности алгебраических и комбинаторных задач. По этому поводу обратите внимание на примеры 3.2 и 3.6 и на предваряющее их обсуждение, а также на § 4, где приводится другой пример того, как теория алгебраической сложности укладывается в нашу постановку. [43]
Количественные характеристики неопределенности, рассматриваемые в теории информации ( или в теории сложности), несомненно, влияют на принятие решений в условиях этой неопределенности. [44]
Возможности практического решения задач дискретного математического программирования ( ДМП) изучаются в теории сложности задач выбора, где показано, что задачи даже умеренного размера, относящиеся к классу NP-полных задач, в общем случае удается решать только приближенно. [45]