Cтраница 1
Мера сложности приписана значениям и правилам. В рассматриваемой редакции системы эти меры являются статическими. Ясно, что возможность динамической модификации мер сложности и важности повысила бы гибкость рассматриваемого подхода. Хотя указанные меры некоторым образом взаимосвязаны, но из значения одной значение другой прямо не следует. [1]
Мерой сложности объекта является количество различных состояний. Оно также характеризует черный ящик. Необходимо воздействовать на объект такими способами, которые позволили бы получить то или иное различимое состояние объекта. Для этой цели служат факторы-входы. [2]
Существует мера сложности Ф и рекурсивная t, такие, что С. [3]
Эта мера сложности очень нетривиальна ( и особенно интересна) для одноэлементного мира U и бесконечного V. В этом случае она измеряет размер наиболее сжатого описания переменного конструктивного объекта в V. Эта мера сложности совершенно объективна, так как почти не зависит от любых произвольных выборов. Будучи невычислимой, она не может быть непосредственно использована в компьютерной науке. Однако она накладывает некоторые основные ограничения на различные меры сложности, подобные ограничениям, задаваемым законами сохранения в физике. [4]
Всякая мимеоинвариантная мера сложности является также и линейно-инвариантной. [5]
На меру сложности можно наложить дополнительные условия, чтобы более полно охватить некоторые специфические аспекты трудности вычисления, но установленные нами условия являются настолько естественными и основными для любого понятия сложности вычисления, что теперь общепринято, что они должны выполняться для любой меры сложности вычисления. Удивительный факт состоит в том, что они достаточны для доказательства многих интересных результатов о всех мерах сложности, для которых они выполняются. В остальной части статьи это будет некоторым образом проиллюстрировано, хотя мы рассмотрим и ряд специфических мер, чтобы расширить наши представления и проиллюстрировать некоторые специальные результаты. [6]
Ввести строгую меру сложности интуитивно-логических умозаключений принимающего решения не представляется возможным. Предельное число таких независимых переменных, которое может быть одновременно учтено при принятии решения в каком-либо звене СОИС, и будет порогом сложности. [7]
Двумя важными мерами сложности алгоритма являются временная и емкостная сложности, рассматриваемые как функции размера входа. Если при данном размере в качестве меры сложности берется наибольшая из сложностей ( по всем входам этого размера), то она называется сложностью в худшем случае. Если в качестве меры сложности берется средняя сложность по всем входам данного размера, то она называется средней ( или усредненной) сложностью. [8]
В качестве меры сложности чаще всего рассматривают две взаимосвязанные меры: число символов функций, входящих в формулу, либо число символов переменных. При этом как символы функций, так и символы переменных подсчитываются с теми кратностями, с которыми они встречаются в формуле. [9]
Из определения меры сложности вычисления получается много результатов. Первый результат состоит в том, что для любой меры существуют сколь угодно сложные рекурсивные функции. [10]
Координаты окрестности меры сложности класса задач можно определить величинами х и а при соответствующем значении критерия зс2 при 2 % - ном или 5 % - ном уровне значимости. [11]
В качестве меры сложности программы машины Тьюринга возьмем число ее активных состояний ( характеристика внутренней памяти), единственное пассивное состояние - заключительное qt, которое не может встречаться в левых частях команд. [12]
Связность является мерой сложности сети. [13]
Пусть т - мимеоинвариантная мера сложности и / - неограниченная неубывающая общерекурсивная функция, т-предельная в синтаксической области некоторой Б - грамматики. [14]
Коразмерность codim служит мерой сложности кри-тич. [15]