Cтраница 1
Теория сложности вычислений касается измерения трудности вычислений. Чтобы перейти к этому, мы должны обсудить, что понимается под мерой сложности вычислений. [1]
Теория сложности вычисления рассматривает, в частности, время вычисления ( число шагов) и необходимый объем памяти. Для некоторых задач известные алгоритмы их решения состоят в последовательном переборе, напр. [2]
Теория сложности вычислений относится к количественным - аспектам решений вычислительных задач. Обычно имеется несколько возможных алгоритмов решения таких задач, как вычисление значений алгебраических выражений, сортировка файла или синтаксический анализ цепочки символов. С каждым из этих алгоритмов связаны некоторые важные функции стоимости, такие как число шагов вычислений ( как функция размера задачи), требуемый объем памяти для вычислений, раз - - мер программы и, в случае аппаратной реализации алгоритмов, - размер схемы и ее глубина. [3]
На развитие теории сложности вычислений дальнейшее влияние оказывали многие работы и результаты, которые не были явно использованы в этой статье. [4]
Мы сознательно не касаемся теории сложности вычислений - это большая и отдельная тема. [5]
Другим важным направлением в теории сложности вычислений является изучение классов с л о ж-л о с т и - множеств функций, для к-рых существуют вычисления со сложностью, не превышающей к. [6]
Очерчивается область исследований в теории сложности вычислений с акцентом на взаимосвязь между на первый взгляд различными задачами и методами. Приведены иллюстративные примеры, имеющие практическое и теоретическое значение. Обсуждаются направления новых исследований. [7]
Сипсер в своем учебнике по теории сложности вычислений, вместо этого лучше говорить mapping ге - ducibility ( сводимость с помощью отображений), сохраняя букву т в обозначении. [8]
ТеЪрия ЛФ-полноты, конечно, самое значительное достижение в теории сложности вычислений. Я не буду здесь на ней останавливаться, потому что это теперь хорошо известно и описано в учебниках. В частности, книга Гэри и Джонсона [31] - прекрасный источник сведений по этому вопросу. [9]
В защищенных линиях связи применяются некоторые схемы кодирования, и мы можем поставить основные вопросы теории сложности вычислений по отношению к таким системам. [10]
Может показаться, что с многообразными возможностями1 выбора меры сложности и разнообразными вопросами, которые могут возникать, теория сложности вычислений станет коллекцией изолированных результатов и не связанных друг с другом методов. [11]
Другая причина, по которой важны простые вычислительные модели ( таких моделей много - разные виды машин Тьюринга, адресные машины и т.п.), связана с теорией сложности вычислений, когда нас начинает интересовать время выполнения программ. Но этот вопрос выходит за рамки классической теории алгоритмов. [12]
Продолжение новой серии кибернетических сборников, публикация которой начата издательством Мир в 1965 г. В данном выпуске большой интерес представит обзорная статья известных ученых Хартманиса и Хопкрофта по теории сложности вычислений, а также статья Сэлтона, в которой излагаются некоторые новые результаты из области информационного поиска. [13]
Любопытно, что проблема конечного спектра ( приведенная в книге Кейслера и Чэна под номером 1 среди старых проблем теории моделей), неожиданно оказалась связана с центральной проблемой теории сложности вычислений - так называемой проблемой перебора. Проблема конечного спектра состоит в следующем: верно ли, что дополнение ( до N) к спектру любой формулы является спектром некоторой другой формулы. [14]
Предлагаемая читателю книга является первым в мировой литературе систематическим изложением принципов построения эффективных, или, как часто говорят, быстрых, алгоритмов - изложением, исходящим из принципов теории сложности вычислений. Авторы не углубляются в общую теорию, а уделяют основное внимание анализу конкретных задач. В книге собрана большая и наиболее интересная часть тех задач, в анализе сложности которых за последнее время достигнут заметный прогресс. Мы не будем останавливаться на содержании книги, оно ясно обрисовано в предисловии авторов, а коснемся лишь вопросов, относящихся к переводу. [15]