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