https://vik.wiki/api.php?action=feedcontributions&feedformat=atom&user=Schnell+Henrik VIK Wiki - Felhasználó közreműködései [hu] 2026-05-18T21:30:24Z Felhasználó közreműködései MediaWiki 1.43.8 https://vik.wiki/index.php?title=Rendszeroptimaliz%C3%A1l%C3%A1s,_13._t%C3%A9tel&diff=186266 Rendszeroptimalizálás, 13. tétel 2015-06-12T08:38:58Z <p>Schnell Henrik: Részletes példa futás kidolgozásának hozzáadása</p> <hr /> <div>==A k-matroid partíciós probléma, ennek algoritmikus megoldása. A 2-matroid-metszet feladat visszavezetése matroid partíciós problémára.==<br /> ===k-matroid partíciós probléma===<br /> <br /> *MPP&lt;sub&gt;k&lt;/sub&gt;*: adott k matroid (M&lt;sub&gt;i&lt;/sub&gt;=(E,F&lt;sub&gt;i&lt;/sub&gt;), i=1...k). Kérdés: a matroidok összege a szabadmatroidot adja-e, vagyis E előáll-e E&lt;sub&gt;1&lt;/sub&gt;&amp;cup;...&amp;cup;E&lt;sub&gt;k&lt;/sub&gt; alakban úgy, hogy E&lt;sub&gt;i&lt;/sub&gt;&amp;isin;F&lt;sub&gt;i&lt;/sub&gt; &amp;forall;i-re. Feltehető, hogy az E&lt;sub&gt;i&lt;/sub&gt; halmazok diszjunktak, ezért hívják a feladatot matroid partíciós problémának.<br /> <br /> *Lemma*: MPP&lt;sub&gt;k&lt;/sub&gt; NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető. &lt;br&gt;<br /> *Lemma*: MPP&lt;sub&gt;k&lt;/sub&gt; coNP-beli, mert tanú rá egy X&amp;sube;E halmaz, ami biztosan összefüggő az összegben, azaz &amp;sum;r&lt;sub&gt;i&lt;/sub&gt;(X)&amp;lt;|X.<br /> <br /> ===Algoritmus===<br /> Induljunk ki az &amp;forall;i E&lt;sub&gt;i&lt;/sub&gt;=&lt;big&gt;&amp;empty;&lt;/big&gt; állapotból. Ekkor E&lt;sub&gt;i&lt;/sub&gt;&amp;isin;F&lt;sub&gt;i&lt;/sub&gt;.<br /> Az E&lt;sub&gt;i&lt;/sub&gt; halmazokat addig bővítjük, amíg az uniójuk E nem lesz, vagy ha nem bővíthető, mutatunk egy X tanút.<br /> <br /> A bővítéshez bevezetünk egy n+k pontú irányított segédgráfot, amelynek<br /> * Csúcsai E elemei &amp;cup; {p&lt;sub&gt;1&lt;/sub&gt;, ..., p&lt;sub&gt;k&lt;/sub&gt;}. p&lt;sub&gt;i&lt;/sub&gt; az E&lt;sub&gt;i&lt;/sub&gt; partíció segédpontja.<br /> * (x&amp;rarr;p&lt;sub&gt;i&lt;/sub&gt;) &amp;isin; E(G), ha x&amp;notin;E&lt;sub&gt;i&lt;/sub&gt; és E&lt;sub&gt;i&lt;/sub&gt;&amp;cup;{x}&amp;isin;F&lt;sub&gt;i&lt;/sub&gt;. &lt;br&gt; Az ilyen típusú élek azt jelképezi, hogy az E&lt;sub&gt;i&lt;/sub&gt; partícióba felvehető x a függetlenség megsértése nélkül.<br /> * (x&amp;rarr;y) &amp;isin; E(G), ha &amp;exist;i x&amp;notin;E&lt;sub&gt;i&lt;/sub&gt;, y&amp;isin;E&lt;sub&gt;i&lt;/sub&gt;, E&lt;sub&gt;i&lt;/sub&gt;&amp;cup;{x}&amp;notin;F&lt;sub&gt;i&lt;/sub&gt;, de E&lt;sub&gt;i&lt;/sub&gt;&amp;cup;{x}-{y}&amp;isin;F&lt;sub&gt;i&lt;/sub&gt;. &lt;br&gt; Az ilyen típusú élek azt jelentik, hogy az E&lt;sub&gt;i&lt;/sub&gt; partícióban az y elem kicserélhető x-re a függetlenség megsértése nélkül.<br /> <br /> # Megkeressük a legrövidebb irányított utat E-&lt;big&gt;&amp;cup;&lt;/big&gt;E&lt;sub&gt;i&lt;/sub&gt;-ből {p&lt;sub&gt;1&lt;/sub&gt;, ..., p&lt;sub&gt;k&lt;/sub&gt;}-ba.<br /> # Ha van ilyen út, javítunk az út mentén, azaz végrehajtjuk a cseréket. &lt;big&gt;&amp;cup;&lt;/big&gt;E&lt;sub&gt;i&lt;/sub&gt; 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.<br /> # Különben STOP, nemleges a válasz, és a tanú a E-&lt;big&gt;&amp;cup;&lt;/big&gt;E&lt;sub&gt;i&lt;/sub&gt;-ből irányított úton elérhető pontok halmaza.<br /> <br /> ===Példa===<br /> Az algoritmus futására itt egy részletesen bemutatott példa a jobb érthetőség kedvéért:&lt;br&gt;<br /> https://docs.google.com/document/d/1CbHAHJY4M3cxmBel0cgZ47GIgTOgQ4RJwn_MeOxbais<br /> <br /> ===2-matroid-metszet feladat===<br /> Lásd [[Rendszeroptimalizálás, 12. tétel | 12.tétel]]<br /> <br /> -- [[PallosPeter|Peti]] - 2007.01.02.<br /> <br /> Javítás: &amp;sum;r&lt;sub&gt;i&lt;/sub&gt;(X)&amp;lt;|E| helyett &amp;sum;r&lt;sub&gt;i&lt;/sub&gt;(X)&amp;lt;|X| !<br /> <br /> -- [[RendesGaborAntal|Gabo]] - 2008.01.04.<br /> <br /> [[Kategória:Mérnök informatikus MSc]]</div> Schnell Henrik