Rendszeroptimalizálás ZH, 2006. december 9.

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

1. Döntsük el, hogy az x₁=1, x₂=2, x₃=1, x₄=0 választással
   1. bázismegoldását
   2. erős bázismegoldását
   adtuk-e meg az alábbi egyenlőtlenségrendszernek:

   x₁ + x₂ ≤ 4
   x₁ + x₃ ≤ 2
   x₂ + x₄ ≤ 2
   x₁ + x₂ + x₃ + x₄ ≤ 4

2. Egy G irányított gráfban irányított körök egy {C₁, C₂, ..., C_k} halmazát nevezzük irányított körfedésnek, ha a C_i 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!
3. 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₁ 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]
4. Az M₂ matroidot az alábbi mátrix koordinátázza a valós test fölött. Mutassuk meg, hogy az M₁∨M₂ matroid (ahol M₁ az előző feladatbeli M₁-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]
5. 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_max feladatra?
6. Mutassuk meg, hogy a ládapakolás feladatra adott First Fit algoritmus approximációs faktora nem jobb, mint 5/3.

-- Peti - 2007.08.01.