Cтраница 1
Теория вычислительной сложности является относитель новой областью исследования; мы представим небольшое чис результатов, связанных с поставленными выше вопросам В конце главы мы дадим рекомендации читателю, желающей подробнее изучить этот предмет. [1]
В теории вычислительной сложности формируется пара А, s, составленная из алгоритма А, предназначенного для решения семейства задач 5 и, в частности, конкретной ( индивидуальной) задачи s из семейства S. Для любой пары сложность можно оценивать системой показателей, каждый из которых называют сигнализирующей функцией. [2]
Основная задача теории вычислительной сложности - это определение того, какие преимущества дает вычисление на k - ленточной машине по сравнению с &2 - ленточной машиной. Эта задача интересна не только сама по себе, так как от скорости, с которой машина с фиксированным числом лент имитирует последовательность машин с произвольным числом лент, зависит проведение известных доказательств, основанных на канторов-ском диагональном методе. Такие приложения исследуются нами ниже при рассмотрении конкретных моделей. [3]
В центре внимания теории вычислительной сложности в настоящее время находится специальный особо важный для приложений класс массовых задач - так называемые переборные задачи. [4]
Помимо сигнализирующей времени в теории вычислительной сложности формируют следующие функции сложности: сигнализирующая емкости - число ячеек оперативной памяти, необходимых для решения задачи SE S алгоритмом А; сигнализирующая колебаний ( поворотов) - количество циклов в программе для реальной ЭВМ, которые изменяют типовую последовательность вычислений; сигнализирующая режима - число обращений к долговременным запоминающим устройствам. [5]
Приведенное ниже изложение основ теории вычислительной сложности носит интуитивный описательный характер. Формальные уточнения и аргументация требуют привлечения аппарата математической логики. [6]
Теория информационной сложности задач управления и теория вычислительной сложности переборных задач отражают разные аспекты сложности классов задач. [7]
По утверждению авторов теория е-сложности отличается принципиально от теории вычислительной сложности тем, что в ней изучают сложность задач, решаемых на основе неполной, неточной или платной информации; в теории же вычислительной сложности оперируют с точной, полной и бесплатной информацией. Центральную роль в теории е-сложности играет понятия информация и реализуемый алгоритм. Точные нижние оценки погрешности решения в данной теории определяют без введения нормы, используя радиусы или диаметры информации, которые формируются различно для задач с полной или приближенной информацией и для класса реализуемых алгоритмов. [8]
Основным экспериментальным материалом, на котором развивалась и апробировалась теория вычислительной сложности, были и являются экстремальные задачи комбинаторного типа и задачи теории графов. С тех пор основные усилия в теории вычислительной сложности были направлены на поиски алгоритмов полиномиальной сложности для задач экспоненциальной сложности и на доказательство сводимости или несводимости конкретных задач к задачам полиномиальной сложности. [9]
Труды симпозиума, проведенного в 1975 г. Содержится 13 статей по теории аналитической вычислительной сложности. [10]
В то же время нельзя согласиться с тем, что проблема построения алгоритмов принятия оперативных решений в рамках теории вычислительной сложности решена. Необходимы специальные исследования для сопоставления по времени счета различных алгоритмов, однако проблема построения гибких алгоритмов в рамках этой теории даже не поставлена. [11]
Параллельно с развитием событий в области комбинаторных алгоритмов набирал силу в течение 60 - х годов другой важный поток исследований - теория вычислительной сложности. Основы этого предмета были заложены в 30 - е годы группой логиков, включающей Аллана Тьюринга, которых заинтересовало существование или несуществование автоматических процедур для установления того, истинны или ложны математические утверждения. [12]
В данной книге представлены математические основания общей теории оптимальных алгоритмов для задач, которые решаются приближенно. Эта теория называется теорией аналитической вычислительной сложности. Предмет этой области науки обсуждается подробнее в § 4 гл. [13]
Заметим, что при доказательстве теоремы 1.4 мы использовали только свойства t, данные леммой 1.2. Таким образом, теорема 1.4 выполняется для любой меры вычислительной сложности. Имеется много других результатов в теории вычислительной сложности, которые не зависят от какой бы то ни было конкретной меры сложности. [14]
Основным экспериментальным материалом, на котором развивалась и апробировалась теория вычислительной сложности, были и являются экстремальные задачи комбинаторного типа и задачи теории графов. С тех пор основные усилия в теории вычислительной сложности были направлены на поиски алгоритмов полиномиальной сложности для задач экспоненциальной сложности и на доказательство сводимости или несводимости конкретных задач к задачам полиномиальной сложности. [15]