https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9F%D0%BE%D0%BB%D0%BD%D0%BE%D1%81%D1%82%D1%8C%D1%8E_%D0%BF%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B0%D0%BF%D0%BF%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0Полностью полиномиальная аппроксимационная схема - История изменений2026-04-26T23:02:18ZИстория изменений этой страницы в викиMediaWiki 1.26.4https://discopal.ispras.ru/index.php?title=%D0%9F%D0%BE%D0%BB%D0%BD%D0%BE%D1%81%D1%82%D1%8C%D1%8E_%D0%BF%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%B0%D0%BF%D0%BF%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0&diff=1276&oldid=prevWikiSysop: 1 версия2008-10-23T16:48:17Z<p>1 версия</p>
<p><b>Новая страница</b></p><div>'''Полностью полиномиальной аппроксимационной схемой''' (PTAS, ''Polynomial-time approximation scheme'') называется приближенный алгоритм, в котором уровень точности <m>\varepsilon</m><br />
выступает в качестве нового параметра, и алгоритм находит<br />
<m>\varepsilon</m>-оптимальное решение за время, ограниченное полиномом от<br />
длины входа и величины <m>\frac{1}{\varepsilon}</m>.<br />
<br />
Например, алгоритм [[Задача о рюкзаке:PTAS]].<br />
<br />
[[Category:Теория сложности]]<br />
{{replicate-from-custiswiki-to-lib}}</div>WikiSysop