|
|
| Строка 1: |
Строка 1: |
| − | '''Полностью полиномиальной аппроксимационной схемой''' (PTAS, ''Polynomial-time approximation scheme'') называется приближенный алгоритм, в котором уровень точности <m>\varepsilon</m>
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | выступает в качестве нового параметра, и алгоритм находит
| + | |
| − | <m>\varepsilon</m>-оптимальное решение за время, ограниченное полиномом от
| + | |
| − | длины входа и величины <m>\frac{1}{\varepsilon}</m>.
| + | |
| − | | + | |
| − | Например, алгоритм [[Задача о рюкзаке:PTAS]].
| + | |
| − | | + | |
| − | [[Category:Теория сложности]]
| + | |
| − | {{replicate-from-custiswiki-to-lib}} | + | |
