https://vik.wiki/index.php?action=history&feed=atom&title=Rendszeroptimaliz%C3%A1l%C3%A1s%2C_19._t%C3%A9telRendszeroptimalizálás, 19. tétel - Laptörténet2026-05-17T17:54:21ZAz oldal laptörténete a wikibenMediaWiki 1.43.8https://vik.wiki/index.php?title=Rendszeroptimaliz%C3%A1l%C3%A1s,_19._t%C3%A9tel&diff=139683&oldid=prevUnknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel19}} <style> ol { margin-top: 0px; } td { padding: 0em 0.4em; text-align: center; } </style> ==!! Graham közelítő algoritmusai …”2012-10-22T09:43:51Z<p>Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel19}} <style> ol { margin-top: 0px; } td { padding: 0em 0.4em; text-align: center; } </style> ==!! Graham közelítő algoritmusai …”</p>
<p><b>Új lap</b></p><div>{{GlobalTemplate|Infoszak|RopiTetel19}}<br />
<br />
<style> <br />
ol { margin-top: 0px; }<br />
td { padding: 0em 0.4em; text-align: center; }<br />
</style><br />
<br />
==!! Graham közelítő algoritmusai a P|||C<sub>max</sub> és a P||prec||C<sub>max</sub> feladatokra (biz. nélkül). A P||prec, p<sub>j</sub>=1||C<sub>max</sub> feladat, Hu algoritmusa (biz. nélkül). A P<sub>2</sub>||prec, p<sub>j</sub>=1C<sub>max</sub> feladat: Coffman és Graham algoritmusa (biz. nélkül).==<br />
<br />
__TOC__<br />
<br />
===P|C<sub>max</sub>===<br />
<br />
Ez már volt a [[RopiTetel18#P_Cmax|18. tétel végén]].<br />
<br />
===P|precC<sub>max</sub>===<br />
<br />
*Tétel*: a listás ütemezés (ha van szabad gép, a sorban az első olyan jobot teszem fel rá, ami már elkezdhető) (2-1/m)-approximációs a P|precC<sub>max</sub> feladatra is.<br />
<br />
===P|prec, p<sub>j</sub>=1C<sub>max</sub>===<br />
<br />
A feladatosztály bonyolultsága<br />
* P|prec, p<sub>j</sub>=1C<sub>max</sub> NP-nehéz<br />
* P<sub>m</sub>|prec, p<sub>j</sub>=1C<sub>max</sub> bonyolultsága ismeretlen<br />
* P|prec, p<sub>j</sub>=1, in-treeC<sub>max</sub>-re a Hu-algoritmus polinom időben optimális megoldást ad.<br />
<br />
*Def.*: Az in-tree (be-fenyő) egy olyan irányított gyökeres fa, aminek az élei a gyökér felé vannak irányítva. <br><br />
*Hu-algoritmus*:<br />
# A precedencia gráf minden csúcsához határozzuk meg a gyökérbe vezető út hosszát.<br />
# Alkalmazzuk a listás ütemezést úthossz szerint csökkenő sorrendben.<br />
<br />
===P<sub>2</sub>|prec, p<sub>j</sub>=1C<sub>max</sub>===<br />
<br />
*Coffman-Graham algoritmus*:<br />
# Végezzünk a precedencia gráfok tranzitív redukciót: ha &exist;a&rarr;b él és ettől különböző a&rarr;b út, töröljük az élt.<br />
# Minden csúcshoz hozzárendelünk egy sorszámot és egy listát.<br />
# A nyelők az 1,2,3,... sorszámokat kapják valamilyen sorrendben, és üres lista tartozik hozzájuk.<br />
# Amint egy csúcs összes kimenő szomszédjának van sorszáma, kitöltjük a hozzá tartozó listát a kimenő szomszédok sorszámával csökkenő sorrendben.<br />
# Ha nincs kitölthető lista, a lexikografikusan legkisebb listával rendelkező számozatlan csúcs kapja a következő sorszámot.<br />
# A csúcs sorszámok szerint csökkenő sorrendben kell listás ütemezést végrehajtani.<br />
<br />
*Tétel*: a Coffman-Graham algoritmus optimális ütemezést ad az a P<sub>2</sub>|prec, p<sub>j</sub>=1C<sub>max</sub> feladatra.<br />
<br />
*Megj.*: a könyvben el van szúrva a példa, a 4.7a ábra helyesen<br />
<br />
{| border="1"<br />
|A||C||F||G||I<br />
|-<br />
|B||D||E||J||H<br />
|}<br />
<br />
-- [[PallosPeter|Peti]] - 2007.01.03.<br />
<br />
<br />
[[Category:Infoszak]]</div>Unknown user