Rendszeroptimalizálás ZH, 2006. december 9. forrásának megtekintése

{{GlobalTemplate|Infoszak|RopiZH061209}}


<ol>

<li> Döntsük el, hogy az x<sub>1</sub>=1, x<sub>2</sub>=2, x<sub>3</sub>=1, x<sub>4</sub>=0 választással
# bázismegoldását
# erős bázismegoldását
adtuk-e meg az alábbi egyenlőtlenségrendszernek:
<center><div style="display:table">
	x<sub>1</sub> + x<sub>2</sub> &le; 4 <br>
	x<sub>1</sub> + x<sub>3</sub> &le; 2 <br>
	x<sub>2</sub> + x<sub>4</sub> &le; 2 <br>
	x<sub>1</sub> + x<sub>2</sub> + x<sub>3</sub> + x<sub>4</sub> &le; 4
</div></center>

<li> Egy G irányított gráfban irányított körök egy {C<sub>1</sub>, C<sub>2</sub>, ..., C<sub>k</sub>} halmazát nevezzük ''irányított körfedésnek'', ha a C<sub>i</sub> körök páronként csúcsdiszjunktak és a gráf minden csúcsa rajta van valamelyik körön. Legyen adott egy G irányított gráf, amelyről tudjuk, hogy van benne irányított körfedés. Legyen adott továbbá egy <math> w : E(G) \mapsto \mathbb{R} </math> élsúlyozás. A feladatunk egy maximális összsúlyú irányított körfedés megtalálása. (Egy körfedés súlya a benne szereplő körök élei súlyának összege.) Bizonyítsuk be, hogy létezik polinomiális idejű algoritmus ennek a feladatnak a megoldására!

<li> Lehet-e olyan értékeket adni az _a_ paraméternek, hogy az alábbi mátrix oszlopai által a valós test felett koordinátázott M<sub>1</sub> matroid grafikus legyen?

<math>
  \begin{array}{@{}r@{}c@{}c@{}c@{}c@{}c@{}l@{}}
	 & \underline{x} & \underline{y} & \underline{u} & \underline{v} & \underline{w} \\
	 \left.\begin{array}{c}
		\\ \\ \\
	 \end{array}\right(
	 & \begin{array}{c} 1 \\ 0 \\ -2 \end{array}
	 & \begin{array}{c} 0 \\ 1 \\ 2 \end{array}
	 & \begin{array}{c} -2 \\ 0 \\ 4 \end{array}
	 & \begin{array}{c} 1 \\ 1 \\ 0 \end{array}
	 & \begin{array}{c} a \\ -2 \\ 4 \end{array}
	 & \left)\begin{array}{c}
		\\ \\ \\
	 \end{array}\right.
  \end{array}
</math>

<li> Az M<sub>2</sub> matroidot az alábbi mátrix koordinátázza a valós test fölött. Mutassuk meg, hogy az M<sub>1</sub><big>&or;</big>M<sub>2</sub> matroid (ahol M<sub>1</sub> az előző feladatbeli M<sub>1</sub>-gyel azonos) az _a_ paraméter bármely értéke esetén grafikus!

<math>
  \begin{array}{@{}r@{}c@{}c@{}c@{}c@{}c@{}l@{}}
	 & \underline{x} & \underline{y} & \underline{u} & \underline{v} & \underline{w} \\
	 \left.\begin{array}{c}
		\\ \\
	 \end{array}\right(
	 & \begin{array}{c} 1 \\ 0 \end{array}
	 & \begin{array}{c} 1 \\ 1 \end{array}
	 & \begin{array}{c} 1 \\ 2 \end{array}
	 & \begin{array}{c} 1 \\ 3 \end{array}
	 & \begin{array}{c} 1 \\ 4 \end{array}
	 & \left)\begin{array}{c}
		\\ \\
	 \end{array}\right.
  \end{array}
</math>

<li> Igaz-e, hogy mindig létezik a munkáknak olyan sorbarendezése, amely sorrendben a Graham-féle listás ütemező algoritmust végrehajtva optimális megoldást kapunk a P|C<sub>max</sub> feladatra?

<li> Mutassuk meg, hogy a ládapakolás feladatra adott First Fit algoritmus approximációs faktora nem jobb, mint 5/3.
</ol>

-- [[PallosPeter|Peti]] - 2007.08.01.


[[Category:Infoszak]]