„Rendszeroptimalizálás, 17. tétel” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
|||
| (Egy közbenső módosítás ugyanattól a felhasználótól nincs mutatva) | |||
| 1. sor: | 1. sor: | ||
==Polinomiális approximációs séma a RÉSZÖSSZEG problémára== | |||
== | |||
===Polinomiális approximációs séma=== | ===Polinomiális approximációs séma=== | ||
*Def.*: egy probléma polinomiális approximációs sémával közelíthető, ha ∀ε>0-ra van rá (1+ε)-approximáció. | *Def.*: egy probléma polinomiális approximációs sémával közelíthető, ha ∀ε>0-ra van rá (1+ε)-approximáció. | ||
Ez nem mindig elég, mert ha a közelítő algoritmus lépésszáma 2<sup>1/ε</sup>n<sup>4</sup>, még mindig exponenciálisan hosszú ideig fut. <br> | Ez nem mindig elég, mert ha a közelítő algoritmus lépésszáma 2<sup>1/ε</sup>n<sup>4</sup>, még mindig exponenciálisan hosszú ideig fut. <br> | ||
| 16. sor: | 7. sor: | ||
===Részösszeg probléma=== | ===Részösszeg probléma=== | ||
Adott _A_ = {<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>} és _t_. <br> | Adott _A_ = {<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>} és _t_. <br> | ||
Kérdés: létezik-e <i>B</i>⊆<i>A</i> úgy, hogy Σ<i>b<sub>i</sub></i> = _t_? <br> | Kérdés: létezik-e <i>B</i>⊆<i>A</i> úgy, hogy Σ<i>b<sub>i</sub></i> = _t_? <br> | ||
| 22. sor: | 12. sor: | ||
===Részösszeg optimalizálási probléma=== | ===Részösszeg optimalizálási probléma=== | ||
Adott _A_ = {<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>} és _t_. <br> | Adott _A_ = {<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>} és _t_. <br> | ||
Keressük <i>B</i>⊆<i>A</i>-t úgy, hogy Σ<i>b<sub>i</sub></i> maximális és Σ<i>b<sub>i</sub></i> ≤ _t_ legyen. <br> | Keressük <i>B</i>⊆<i>A</i>-t úgy, hogy Σ<i>b<sub>i</sub></i> maximális és Σ<i>b<sub>i</sub></i> ≤ _t_ legyen. <br> | ||
| 29. sor: | 18. sor: | ||
===Közelítő algoritmus a részösszeg optimalizálási problémára=== | ===Közelítő algoritmus a részösszeg optimalizálási problémára=== | ||
*Tétel*: a probléma teljesen polinomiális sémával közelíthető. | *Tétel*: a probléma teljesen polinomiális sémával közelíthető. | ||
| 87. sor: | 75. sor: | ||
-- [[PallosPeter|Peti]] - 2006.12.18. | -- [[PallosPeter|Peti]] - 2006.12.18. | ||
[[Kategória:Mérnök informatikus MSc]] | |||
[[ | |||