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