1632
правки
Изменения
м
'''Сложность алгоритма''' — величина, характеризующая длину описания алгоритма или громоздкость процессов его применения к исходным данным.
== История ==
Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
rollbackEdits.php mass rollback
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.
== Определения ==
В основных понятиях теории сложности используются такие величины , как время работы и объем затрачиваемой памяти.{{Определение|definition=<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.}}
{{Определение
|definition=
<tex>\mathrm{TS}(pm,x)</tex> — время работы программы р объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе х<tex>x</tex>.
}}
Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{SDTIME}(pf(n))</tex> {{---}} класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> выполнено <tex>\mathrm{T}(m,x) \leqslant f(n)</tex> (здесь <tex>n</tex> — объем памяти, требуемый программе р для выполнения на входе хдлина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{DTIMEDSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа машина Тьюринга <tex>pm</tex> такая, что <tex>L(pm)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{TS}(pm,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).<br>}}
{{Определение|definition=<tex>\mathrm{DSPACETS}(f(n),g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из выполнено <tex>L\mathrm{T}(p,x) = O(f(n))</tex> выполнено и <tex>\mathrm{S}(p,x) = O(fg(n))</tex> (здесь , где <tex>n</tex> — длина <tex>x</tex>)входа.
}}
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство в которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]]существует пара "ленточный символ - состояние", то есть из каждого состояния может быть несколько переходов по одному для которой существует 2 и тому же символу на входной лентеболее команд.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа НМТ <tex>pm</tex> такая, что <tex>L(pm)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).<br> <tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует недетерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(pm,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{TSNSPACE}(f,g(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа НМТ <tex>pm</tex> такая, что <tex>L(pm)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{TS}(pm,x) = O(f(n))</tex> и (здесь <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где — длина <tex>x</tex> — длина входа).
}}
== См. также ==* [[Класс P]]* [[Классы NP и Σ₁]] == Источники информации ==* [http://ru.wikipedia.org/wiki/Класс_сложности Википедия | Класс сложности]* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1. [[Категория: Теория сложности|*]][[Категория:Детерминированные и недетерминированные вычисления, сложность по памяти и времени|*]][[Категория:Базовые определения|*]][[Категория:Классы сложности|*]]
