Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiZH061209}}

Döntsük el, hogy az x₁=1, x₂=2, x₃=1, x₄=0 választással # bázisme…”

2012-10-22T09:44:52Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiZH061209}} <ol> <li> Döntsük el, hogy az x1=1, x2=2, x3=1, x4=0 választással # bázisme…”

Új lap

{{GlobalTemplate|Infoszak|RopiZH061209}}

<ol>

<li> Döntsük el, hogy az x1=1, x2=2, x3=1, x4=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">
x1 + x2 ≤ 4 
x1 + x3 ≤ 2 
x2 + x4 ≤ 2 
x1 + x2 + x3 + x4 ≤ 4
</div></center>

<li> Egy G irányított gráfban irányított körök egy {C1, C2, ..., Ck} halmazát nevezzük ''irányított körfedésnek'', ha a Ci 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 M1 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 M2 matroidot az alábbi mátrix koordinátázza a valós test fölött. Mutassuk meg, hogy az M1<big>&or;</big>M2 matroid (ahol M1 az előző feladatbeli M1-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|Cmax 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]]

Rendszeroptimalizálás ZH, 2006. december 9. - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiZH061209}} Döntsük el, hogy az x1=1, x2=2, x3=1, x4=0 választással # bázisme…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiZH061209}}

Döntsük el, hogy az x₁=1, x₂=2, x₃=1, x₄=0 választással # bázisme…”