„Rendszeroptimalizálás, 13. tétel” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
|||
| (2 közbenső módosítás, amit 2 másik szerkesztő végzett, nincs mutatva) | |||
| 5. sor: | 5. sor: | ||
*Lemma*: MPP<sub>k</sub> NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető. <br> | *Lemma*: MPP<sub>k</sub> NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető. <br> | ||
*Lemma*: MPP<sub>k</sub> coNP-beli, mert tanú rá egy X⊆E halmaz, ami biztosan összefüggő az összegben, azaz ∑r<sub>i</sub>(X)<|X. | *Lemma*: MPP<sub>k</sub> coNP-beli, mert tanú rá egy X⊆E halmaz, ami biztosan összefüggő az összegben, azaz ∑r<sub>i</sub>(X)<|X|. | ||
===Algoritmus=== | ===Algoritmus=== | ||
| 19. sor: | 19. sor: | ||
# Ha van ilyen út, javítunk az út mentén, azaz végrehajtjuk a cseréket. <big>∪</big>E<sub>i</sub> mérete 1-gyel nő. Azért kell a legrövidebb úton végigmenni, mert különben nem garantált, hogy a cserék során nem sérül a partíciók függetlensége. | # Ha van ilyen út, javítunk az út mentén, azaz végrehajtjuk a cseréket. <big>∪</big>E<sub>i</sub> mérete 1-gyel nő. Azért kell a legrövidebb úton végigmenni, mert különben nem garantált, hogy a cserék során nem sérül a partíciók függetlensége. | ||
# Különben STOP, nemleges a válasz, és a tanú a E-<big>∪</big>E<sub>i</sub>-ből irányított úton elérhető pontok halmaza. | # Különben STOP, nemleges a válasz, és a tanú a E-<big>∪</big>E<sub>i</sub>-ből irányított úton elérhető pontok halmaza. | ||
===Példa=== | |||
Az algoritmus futására itt egy részletesen bemutatott példa a jobb érthetőség kedvéért:<br> | |||
https://docs.google.com/document/d/1CbHAHJY4M3cxmBel0cgZ47GIgTOgQ4RJwn_MeOxbais | |||
===2-matroid-metszet feladat=== | ===2-matroid-metszet feladat=== | ||
| 29. sor: | 33. sor: | ||
-- [[RendesGaborAntal|Gabo]] - 2008.01.04. | -- [[RendesGaborAntal|Gabo]] - 2008.01.04. | ||
[[ | [[Kategória:Mérnök informatikus MSc]] | ||