<<
>>

5.4. Характеристики сложности вычислений

В общей теории алгоритмов изучаются лишь принципиальная возможность алгоритмического решения задачи. При рассмотрении конкретных задач не обращается внимания на ресурсы времени и памяти для соответствующих им разрешающих алгоритмов.

Однако нетрудно понять, что принципиальная возможность алгоритмического решения задачи еще не означает, что оно может быть практически получено. Поэтому возникает потребность уточнить понятие алгоритмической разрешимости, введя характеристики сложности алгоритмов, позволяющие судить об их практической реализуемости.

В качестве модели вычислительного устройства выберем МТ. Пусть МТ вычисляет функцию f(x). Определим функцию tT(x), равную числу шагов машины Т, выполненному при вычислении f(x), если f(x) определено. Если f(x) не определено, то значение tT(x) считается неопределенным. Функция tT(x) называется временной сложностью.

Активной зоной при работе машины Т на слове х называется множество всех ячеек ленты, которые либо содержат непустые символы, либо посещались в процессе вычисления f(x) устройством машины Т. Определим функцию sT(x), равную длине активной зоны при работе машины Т на слове х, если f(x) определено. Если f(x) не определено, то значение ST(x) считается неопределенным. Функция ST(x) называется емкостной (ленточной) сложностью.

Введенные функции ST(x) и tT(x) являются словарными.

Удобно ввести для рассмотрения функции натурального аргумента

Они также называются функциями временной и емкостной

сложности (по худшему случаю).

<< | >>
Источник: Викентьева О. Л.. Математическая логика и теория алгоритмов. Конспект лекций для студентов специальностей АСУ, ЭВТ, КЗИ. Пермь, 2007г.. 2007

Еще по теме 5.4. Характеристики сложности вычислений:

  1. 1.1. Уголовно-правовая характеристика хулиганства
  2. §2. Содержание криминалистической характеристики детоубийств. Обстоятельства, подлежащие доказыванию
  3. 1.3. Характеристика основных этических категорий
  4. 3.3. ПРОЕКТИРОВАНИЕ СКЛАДСКОЙ СИСТЕМЫ
  5. 2.3. Разработка методики оценки характеристик достоверности прн использовании алгоритмов диагностирования с учетом методической составляющей погрешности, погрешности измерения н дополнительной погрешности.
  6. 4.5 Поля Янга-Миллса
  7. 3.2 Рсгуляризирующин алгоритм обработки навигационных измерений
  8. в главе проводится анализ влияния взаимного расположения НКА и созвездия НС, участвующего в сеансе навигационных определений, на корреляционные характеристики навигационных векторов, поступающих из НП. Проводится анализ влияния на точность навигационной оценки использования ковариационных матриц в диагональном виде без учета корреляционных характеристик ошибок векторов навигационных измерений. Показано, что существует резерв в повышении точности навигационных оценок на коротких интервалах про
  9. 4.2 Анализ влияния статистических характеристик входной навигационной информации на точность навигационной оценки
  10. 3.3.1 Оцениваемые характеристики
  11. 2.4. Блочные коды и их характеристики
  12. § 3. Институт — кибернетическая система
  13. Кинематические характеристики движения
  14. Матричный метод решения систем линейных уравнений.
  15. Интегрирование биноминальных дифференциалов.
  16. Численные методы решения дифференциальных уравнений.
  17. 4.2. Методические указания к выполнению лабораторных работ
  18. 5.4. Характеристики сложности вычислений
  19. «сложность» и «сложные системы» с позиции самоорганизации и теории самоорганизации
  20. Система сертификации средств защиты информации