27
правок
Изменения
Новая страница: «В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для...»
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.
Сложность алгоритма - величина, характеризующая длину описания алгоритма или громоздкость процессов его применения к исходным данным.
В основных понятиях теории сложности используются такие величины как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы р на входе х.
}}
{{Определение
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе р для выполнения на входе х.
}}
Введём понятия <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex>, аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму, а <tex>\mathrm{N}</tex> — недетерминизму). Через них будет дано определение многим сложностным классам.
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}
[[Категория: Теория сложности]]
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Классы NP и Σ₁|NP]] и т.д.
Сложность алгоритма - величина, характеризующая длину описания алгоритма или громоздкость процессов его применения к исходным данным.
В основных понятиях теории сложности используются такие величины как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы р на входе х.
}}
{{Определение
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе р для выполнения на входе х.
}}
Введём понятия <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex>, аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex> (префикс <tex>\mathrm{D}</tex> соответствует детерминизму, а <tex>\mathrm{N}</tex> — недетерминизму). Через них будет дано определение многим сложностным классам.
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(p,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}
[[Категория: Теория сложности]]
