Главная
Проблема исчисления предикатов
Процедура унификации
Отношения на функциях принадлежности
Неразрешимые алгоритмические проблемы МТ
Полнота и непротиворечивость
NP-полные (универсальные) задачи
Стандартизация услуг
Стандартизация и экология
Организационные и методические принципы сертификации в России
Программа сертификации
Метрологический надзор
Структура кристаллов
Судьбы крестьянские
Еще одна фальшивая ценность
Такая судьба
Соприкосновение с рынком
Мой театр, мои коллеги
Гастроли
И жизнь и слезы и любовь
Возвращение из Томска
Реклама:
|
|
Полнота и непротиворечивость
ожно однозначное декодирование e-1,
e и e-1 полиномиально вычислимы, то есть существуют эффективные алгоритмы кодировки и декодирования.
кодировка неизбыточна. Неизбыточная кодировка сопоставляет код наименьшей длины. Например, двоичный код. Унарная кодировка избыточна.
Временная сложность. Обозначим ta(s) – время переработки алгоритмом решения массовой задачи П индивидуальной задачи I, с начальной конфигурацией К1=q1s, в конечную Кz=qzИs. При этом s кодирует задачу из подмножества Y. То есть задачу, для которой МТ останавливается за конечное время с результатом И. Тогда временная сложность Ta(n) массовой задачи П, есть максимальное время решения любой I?П, размерность которой не превосходит n.
Ta(n)=max(ta(s)), |s|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
