„Rendszeroptimalizálás, 17. tétel” változatai közötti eltérés

(2 közbenső módosítás, amit 2 másik szerkesztő végzett, nincs mutatva)

1. sor:

~~{{GlobalTemplate|Infoszak|RopiTetel17}}~~

==Polinomiális approximációs séma a RÉSZÖSSZEG problémára==

==!! Polinomiális approximációs séma a =RÉSZÖSSZEG= problémára~~.==~~

~~__TOC__~~

~~===[http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=17258 Szkennelt leírás és bizonyítás az infositeon]=~~==

===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ó.

Ez nem mindig elég, mert ha a közelítő algoritmus lépésszáma 21/εn4, még mindig exponenciálisan hosszú ideig fut.

16. sor:

7. sor:

===Részösszeg probléma===

Adott _A_ = {a1, a2, ..., an} és _t_.

Kérdés: létezik-e B&sube;A úgy, hogy Σbi = _t_?

22. sor:

12. sor:

===Részösszeg optimalizálási probléma===

Adott _A_ = {a1, a2, ..., an} és _t_.

Keressük B&sube;A-t úgy, hogy Σbi maximális és Σbi ≤ _t_ legyen.

29. sor:

18. sor:

===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ő.

58. sor:

46. sor:

Def.: δ-val ritkítás

<pre>L növekvő sorrendbe rendezett halmaz.

foreach (~~~~l~~<big>~~∈~~</big>~~L~~~~) {

foreach (l'''∈L''') {

~~~~m~~~~ az ~~~~l~~~~-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.

''m'' az ''l''-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.

if (~~~~l~~&~~lt;m(1+~~~~δ~~~~)) ~~~~l~~~~-et kidobjuk.

if (''l''lt;m(1+''δ'')) ''l''-et kidobjuk.

}</pre>

87. sor:

75. sor:

-- [[PallosPeter|Peti]] - 2006.12.18.

[[Kategória:Mérnök informatikus MSc]]

[[~~Category~~:~~Infoszak~~]]

@@ 1. sor: / 1. sor: @@
-{{GlobalTemplate|Infoszak|RopiTetel17}}
+==Polinomiális approximációs séma a RÉSZÖSSZEG problémára==
-==!! Polinomiális approximációs séma a =RÉSZÖSSZEG= problémára.==
-__TOC__
-===[http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=17258 Szkennelt leírás és bizonyítás az infositeon]===
 ===Polinomiális approximációs séma===
 *Def.*: egy probléma polinomiális approximációs sémával közelíthető, ha &forall;&epsilon;>0-ra van rá (1+&epsilon;)-approximáció.
 Ez nem mindig elég, mert ha a közelítő algoritmus lépésszáma 2<sup>1/&epsilon;</sup>n<sup>4</sup>, még mindig exponenciálisan hosszú ideig fut. <br>
@@ 16. sor: / 7. sor: @@
 ===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>
 Kérdés: létezik-e <i>B</i>&sube;<i>A</i> úgy, hogy &Sigma;<i>b<sub>i</sub></i> = _t_? <br>
@@ 22. sor: / 12. sor: @@
 ===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>
 Keressük <i>B</i>&sube;<i>A</i>-t úgy, hogy &Sigma;<i>b<sub>i</sub></i> maximális és &Sigma;<i>b<sub>i</sub></i> &le; _t_ legyen. <br>
@@ 29. sor: / 18. sor: @@
 ===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ő.
@@ 58. sor: / 46. sor: @@
 Def.: &delta;-val ritkítás
 <pre><i>L</i> növekvő sorrendbe rendezett halmaz.
-foreach (<i>l</i><big>&isin;</big><i>L</i>) {
+foreach (l'''&isin;L''') {
-	<i>m</i> az <i>l</i>-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.
+	''m'' az ''l''-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.
-	if (<i>l</i>&lt;m(1+<i>&delta;</i>)) <i>l</i>-et kidobjuk.
+	if (''l''lt;m(1+''&delta;'')) ''l''-et kidobjuk.
 }</pre>
@@ 87. sor: / 75. sor: @@
 -- [[PallosPeter|Peti]] - 2006.12.18.
+[[Kategória:Mérnök informatikus MSc]]
-[[Category:Infoszak]]