Компьютерлік теорияда DSPACE – детерминистік Тьюринг машинасының жад көлемі. Алгоритмдерді шешу үшін қажет жад ресурсын анықтайды. Жадының күрделілігі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
цифрлік репозиторийлер
digital repositories
Есептеу күрделілігі теориясында DSPACE немесе SPACE — детерминистік Тьюринг машинасының жад кеңістігін сипаттайтын есептеу ресурсы. Ол берілген алгоритммен есептеу мәселесін шешу үшін "қалыпты" физикалық компьютерге қажетті жад кеңістігінің жалпы көлемін көрсетеді.
In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm.
Машина үлгілері
DSPACE дәстүрлі түрде детерминистік Тьюринг машинасымен өлшенеді. Бірнеше маңызды кеңістіктік күрделілік кластары сызықтық емес, яғни кіріс көлемінен кіші. Сондықтан, алгоритмді кіріс немесе шығыс көлеміне "есептеу" жад кеңістігін нақты түсірмейді. Бұл мәселе кіріс және шығыс таспаларына жазуға және оқуға рұқсат етілмейтін көп таспалы Тьюринг машинасының анықтамасымен шешіледі, бұл стандартты көп таспалы Тьюринг машинасының бір түрі. Бұл L (логарифмдік кеңістік) сияқты кіші кеңістік кластарын жұмыс таспаларының барлығы қолданатын кеңістік көлемі бойынша анықтауға мүмкіндік береді (арнайы кіріс және шығыс таспаларын есепке алмай). Әліпбидің тиісті дәрежесін қолдану арқылы көптеген символдарды бірге біріктіруге болатындықтан, барлық c ≥ 1 және f(n) ≥ 1 үшін c f(n) кеңістігінде танылатын тілдер класы f(n) кеңістігінде танылатын тілдер класымен сәйкес келеді. Бұл анықтамада үлкен О нотациясын қолдануды негіздейді.
DSPACE is traditionally measured on a deterministic Turing machine. Several important space complexity classes are sublinear, that is, smaller than the size of the input. Thus, "charging" the algorithm for the size of the input, or for the size of the output, would not truly capture the memory space used. This is solved by defining the multi tape Turing machine with input and output, which is a standard multi tape Turing machine, except that the input tape may never be written to, and the output tape may never be read from. This allows smaller space classes, such as L (logarithmic space), to be defined in terms of the amount of space used by all of the work tapes (excluding the special input and output tapes). Since many symbols might be packed into one by taking a suitable power of the alphabet, for all c ≥ 1 and f such that f(n) ≥ 1, the class of languages recognizable in c f(n) space is the same as the class of languages recognizable in f(n) space. This justifies usage of big O notation in the definition.
Басқа күрделілік сыныптарымен байланыс
DSPACE — детерминистік емес NSPACE-тің детерминистік аналогы, детерминистік емес Тьюринг машинасының жад кеңістігі класы. Савич теоремасы бойынша, NTIME келесідей DSPACE-ке қатысты: Кез келген уақыт бойынша құрастырылатын t(n) функциясы үшін:
DSPACE is the deterministic counterpart of NSPACE, the class of memory space on a non deterministic Turing machine. By Savitch's theorem, we have that
NTIME is related to DSPACE in the following way. For any time constructible function t(n), we have