Вычислительная сложность

Cтраница 2

Упрощенная структура алгоритма Фано [ Jordan ( 1966, 19661ЕЕЕ. [16]

Исследования вычислительной сложности и требований к памяти для последовательного декодирования вызывают интерес, и они все еще продолжаются. В противовес алгоритму Витерби, который сохраняет траектории 2 ( / v A путей и соответствующих метрик, стек-алгоритм последовательного декодирования работает с несколькими путями и их соответствующими метриками. В стек-алгоритме более вероятные пути упорядочиваются согласно их метрик, причем в верхней части ( в голове стека) располагается путь, имеющий наибольшую метрику. На каждом шаге алгоритма только путь в голове стека проверяется по разветвлению. Это приносит 2 продолжений и их соответствующих метрик. Эти 2; продолжения вместе с другими путями затем упорядочиваются согласно величинам их метрик, и все пути с метриками, которые располагаются ниже некоторой выбранной величины от метрики главного пути, отбрасываются. Затем процесс продолжения путей с наибольшими метриками повторяется. [17]

Анализ вычислительной сложности задач позволяет выделить классы задач, для которых существуют эффективные алгоритмы, и выявить универсальность некоторых других задач. [18]

Оценим теперь вычислительную сложность этого алгоритма. К этому следует прибавить суммарную длину всех циклов. [19]

Граф и эйлеров цикл в этом графе, найденный с помощью алгоритма. [20]

Оценим теперь вычислительную сложность нашего алгоритма. Для этого отметим, что каждая итерация главного цикла ( строка 5) либо помещает вершину в стек СТЕК, и удаляет ребро из графа, либо переносит вершину из стека СТЕК в стек СЕ. В свою очередь число шагов в каждой итерации ограничено константой. [21]

Следовательно, вычислительная сложность определяется как ЗК умножений на символ ( бит), причем она не зависит от длины блока N и линейно связана с К. [22]

В теории вычислительной сложности формируется пара А, s, составленная из алгоритма А, предназначенного для решения семейства задач 5 и, в частности, конкретной ( индивидуальной) задачи s из семейства S. Для любой пары сложность можно оценивать системой показателей, каждый из которых называют сигнализирующей функцией. [23]

Параметры ИКИХ-фильтра в зависимости от ширины переходной полосы при разных значениях ширины полосы пропускания. ( а максимальное уменьшение объема вычислений в процентах. ( Ь оптимальные значения коэффициентов расширения. [24]

Рассмотренное уменьшение вычислительной сложности ИКИХ-фильтров основано на предположении, что фильтры реализуются в виде двух отдельных субфильтров, как показано на рисунке 7.34. Мы не поддались искушению объединить эти два фильтра в один, коэффициенты которого являются сверткой импульсных характеристик субфильтров. [25]

Мы анализируем вычислительную сложность определения того, является ли выполнимой формула F классического исчисления предикатов, удовлетворяющая определенным синтаксическим ограничениям. Нижние границы устанавливаются с использованием проблем допустимости для машин Тьюринга с ограниченным временем работы, альтернирующих магазинных автоматов и стековых автоматов. [26]

Интересно сравнить вычислительную сложность рассматриваемой задачи относительно классического и квантового компьютеров. В классическом случае, полиномиальная эквивалентность в теории сложности ( Гэри и Джонсон, 1979) основана на моделях детерминированных ( DTM) и недетерминированных ( NDTM) машин Тьюринга. Сперва отметим один важный результат ( обозначаемый далее ()), что для любого классического решения нашей задачи, используя DTM, существует функция /: Z2jv - 225 которая требует, по крайней мере, N 1 вызовов оракула. Чтобы показать это, предположим, что DTM может решить задачу для каждой такой функции /, используя только М N вызовов. [27]

Ключом к оценке вычислительной сложности этого алгоритма является определение количества повторений внутреннего цикла и, следовательно, количества рекурсивных вызовов. [28]

Основная задача теории вычислительной сложности - это определение того, какие преимущества дает вычисление на k - ленточной машине по сравнению с &2 - ленточной машиной. Эта задача интересна не только сама по себе, так как от скорости, с которой машина с фиксированным числом лент имитирует последовательность машин с произвольным числом лент, зависит проведение известных доказательств, основанных на канторов-ском диагональном методе. Такие приложения исследуются нами ниже при рассмотрении конкретных моделей. [29]

Следует подчеркнуть, что вычислительная сложность не всегда монотонно возрастает с ростом числа неизвестных параметров. Например, для модели АШЗ) с тремя неизвестными параметрами требуется гораздо меньше вычислений, чем для модели МА ( 1) с единственным неизвестным параметром. Ясно, что в этих случаях использование принципа экономичности не может быть обосновано соображениями только вычислительной сложности. [30]

Страницы: 1 2 3 4