Время - вычисление
Cтраница 3
 |
Лента с несколькими уровнями. [31] |
Предположим, что время вычисления машины М не превосходит Кп. Такая машина, конечно, не может посетить более чем ( К -) п пустых квадратов ленты. Символы, которые могут встречаться теперь в квадратах новых лент, представляют упорядоченные комбинации из / С символов первоначальных лент, по одному символу на каждом уровне клетки ленты. Верхний уровень новой ленты используется для записи входного слова, в то время как оставшиеся К. Машина М начинает работу только с символов, которые встречаются в верхнем уровне ее ленты, и работает точно так же, как и М в начале своих вычислений. Однако, если М пытается выйти за пределы входной последовательности в пустую часть ленты, М возвращается обратно и работает в обратном направлении во втором уровне своей ленты. [32]
Покажите, что время вычисления транзитивной редукции ациклического графа имеет тот же порядок, что и время вычисления транзитивной редукции произвольного графа, если принять те же допущения, что и в упр. [33]
Изыскание путей сокращения времени вычислений - это актуальная задача, решению которой способствует создание эффективных алгоритмов преобразований. К таким алгоритмам относится БПФ. [34]
Значение N определяется временем вычислений. [35]
Необходимость введения компенсации на время вычисления возникает в тех случаях, когда время, необходимое для цифровой обработки, составляет значительную часть общего периода дискретизации ( см. § 2.2) или когда скорость изменения сигнала настолько высока, что даже незначительное время, потребное на обработку, приводит к значительным погрешностям в выходном сигнале. [36]
Первая величина здесь представляет время вычисления преобразований, а вторая - выполнения 2п умножений ( п log co-f - 1) - разрядных двоичных целых чисел. Наилучшее известное значение M ( k) равно k log k log log k ( разд. [37]
Эта минимизация выполняется во время вычисления изображения D ( 1), D ( 2), D ( 3) и D ( 4) в приведенном выше алгоритме. [38]
Все важные нижние оценки времени вычислений и объема памяти основаны на диагональных рассуждениях. Диагональные рассуждения использовались Тьюрингом и его современниками для доказательства того, что некоторые задачи алгоритмически неразрешимы. В 1960 г. Рабин [60] доказал, что для всякой разумной меры сложности, такой, как время вычисления или объем памяти, достаточное увеличение допустимого времени или объема памяти всегда позволяет вычислять большее число 0 - 1 функций. Примерно в то же время Ритчи в своей диссертации [65] определил специальную иерархию функций ( которая, как он показал, нетривиальна для 0 - 1 функций) в терминах объема доступной памяти. [39]
В определяется нижняя граница времени вычисления всякой машины, которая реализует это преобразование. Эти две границы сравниваются и обсуждаются в разд. [40]
Эффективность вычислений является функцией времени вычисления и используемой памяти. Часто эти параметры взаимосвязаны, так что уменьшение одного из них приводит к увеличению другого. Хеширование можно рассматривать как метод, уменьшающий время поиска и рационально использующий память. Таким образом, в настоящее время, когда стоимость ЗУ быстро снижается как в абсолютном, так и в относительном смысле, наблюдается тенденция постепенного расширения области применения хеширования. [41]
Вычислительные ресурсы ( память и время вычислений), необходимые для отыскания правильной интерпретации, не должны превышать определенный порог. Система распознавания, которая через пару дней выдаст результат, пусть и правильный, и потребует памяти объемом несколько гигабайт, вряд ли кому-нибудь будет нужна. [42]
К внешним функциям обращаются во время вычисления арифметических или логических выражений. [43]
N потребует значительного времени ( время вычисления qzad х ( т) пропорционально ты) и градиентные методы окажутся мало эффективными. Если же учитнвать организацию функции х, ( Т), то время вычислений может быть существенно сокращено. [44]
Другим ограничивающим фактором может стать время вычислений. Если в ситуации, когда превышается отведенное время счета, мы имеем полное решение, то оно, совместно с наименьшей нижней оценкой для вершин из активного множества, определяет границы точности нашего решения. [45]
Страницы: 1 2 3 4