Operacijske raziskave - vaje 6.4.2020

--- tags: vaje, or, dinamicno programiranje hackmd: https://hackmd.io/bwoGbg4uSdaXRyE-1DjvMQ plugins: mathjax, mermaid --- # Operacijske raziskave - vaje 6.4.2020 --- ## Dinamično programiranje ### Naloga 1 Dan je niz $S = a_1 a_2 \dots a_n$, kjer so $a_i$ ($1 \le i \le n$) elementi neke končne abecede. Nizu $a_j a_{j+1} \dots a_k$, kjer je $1 \le j \le k \le n$, pravimo *strnjen podniz* niza $S$. S pomočjo dinamičnega programiranja napiši algoritem, ki določi najdaljši palindromski strnjen podniz v $S$. ---- $$ \begin{aligned} p_{ij} &\dots \text{ali je strnjen podniz $a_i \dots a_{j-1}$ palindrom} \\[1ex] p_{ii} &= \top \\ p_{i,i+1} &= \top \\ p_{ij} &= (a_i = a_{j-1}) \land p_{i+1, j-1} \quad (j > i+1) \\ (\ell^*, i^*, j^*) &= \max\{(j-i, i, j) \mid 1 \le i \le j \le n, p_{ij} = \top\} \end{aligned} $$ Vrstni red računanja: naraščajoče po $j-i$, $i$ ```python def palindrom(s): n = len(s) if n == 0: # prazen niz je palindrom return (0, 0, 0) p = {} for i in range(n): p[i, i] = True for i in range(n-1): p[i, i+1] = True d = [True, True] ll, ii, jj = 1, n-1, n for l in range(2, n+1): if not (d[l-2] or d[l-1]): # če ni bilo palindromov break # prejšnjih dveh dolžin, končamo d.append(False) for i in range(n-l+1): p[i, i+l] = (s[i] == s[i+l-1]) and p[i+1, i+l-1] if p[i, i+l]: # imamo palindrom, zabeležimo d[l] = True ll, ii, jj = l, i, i+l return ll, ii, jj ``` Časovna zahtevnost: $O(n^2)$ --- ### Naloga 2 Dana je matrika $A = (a_{ij})_{i,j=1}^{m,n}$. Poiskati želimo strnjeno podmatriko matrike $A$ z največjo vsoto komponent. 1. Reši problem za matriko $$ A = \begin{pmatrix} 1 & -1 & 2 & 4 \\ -3 & -2 & 8 & 2 \\ -3 & 2 & -2 & 4 \\ 1 & -5 & -1 & -2 \end{pmatrix} . $$ 2. Napiši rekurzivne enačbe za opisani problem. 3. Napiši algoritem, ki reši opisani problem. Oceni tudi njegovo časovno zahtevnost v odvisnosti od $m$ in $n$. ---- $$ \begin{aligned} v_{hij} &\dots \text{največja vsota elementov od vrstic $h+1$ do $i$ z zadnjim stolpcem $j$} \\ c_{hij} &\dots \text{vsota števil od vrstic $h+1$ do $i$ v $j$-tem stolpcu} \\ s_{ij} &\dots \text{vsota števil do $i$-te vrstice v $j$-tem stolpcu} \\[1ex] s_{0j} &= 0 \\ s_{ij} &= s_{i-1, j} + a_{ij} \quad (i > 0) \\[1ex] c_{hij} &= s_{ij} - s_{hj} \\[1ex] v_{hi0} &= 0 \\ v_{hij} &= s_{ij} - s_{hj} + \max\{v_{h,i,j-1}, 0\} \\[1ex] v^* &= \max\{v_{hij} \mid 0 \le h \le i \le m, 0 \le j \le n\} \end{aligned} $$ Vrstni red računanja: $s_{ij}$ naraščajoče po $i$, $j$; $v_{hij}$ naraščajoče po $h \le i$, $j$ Časovna zahtevnost: $O(mn) + O(m^2 n) = O(m^2 n)$ --- ### Naloga 3 Na ulici je $n$ vrstnih hiš, pri čemer je v $i$-ti hiši $c_i$ denarja. Tat se odloča, katere izmed hiš naj oropa. Vsak oropan stanovalec to sporoči svojim sosedom, zato tat ne sme oropati dveh sosednjih hiš. Ker je tat poslušal predmet Operacijske raziskave, pozna dinamično programiranje. Pokaži, kako naj tat določi, katere hiše naj oropa. $$ \begin{aligned} v_i &\dots \text{max vrednost do $i$-te hiše} \\[1ex] v_0 &= 0 \\ v_1 &= c_1 \\ v_i &= \max\{c_i + v_{i-2}, v_{i-1}\} \quad (i > 1) \\[1ex] v^* &= v_n \end{aligned} $$ Vrstni red računanja: naraščajoče po $i$ Časovna zahtevnost: $O(n)$ --- ### Naloga 4 Imamo hlod dolžine $\ell$, ki bi ga radi razžagali na $n$ označenih mestih $0 < x_1 < x_2 < \dots < x_n < \ell$. Eno rezanje stane toliko, kolikor je dolžina hloda, ki ga režemo. Ko hlod prerežemo, dobimo dva manjša hloda, ki ju režemo naprej. Poiskati želimo zaporedje rezanj z najmanjšo ceno. 1. Reši problem pri podatkih $\ell = 10$ in $(x)_{i=1}^4 = (3, 5, 7, 8)$. 2. S pomočjo dinamičnega programiranja reši problem v splošnem. Oceni tudi njegovo časovno zahtevnost. $$ \begin{aligned} x_0 &= 0 \\ x_{n+1} &= \ell \\[1ex] c_{ij} &\dots \text{optimalna cena rezanja hloda od $x_i$ do $x_j$} \\[1ex] c_{i, i+1} &= 0 \\ c_{ij} &= x_j - x_i + \min\{c_{ih} + c_{hj} \mid i+1 \le h \le j-1\} \quad (j > i+1) \\[1ex] c^* &= c_{0, n+1} \end{aligned} $$ Vrstni red: $c_{ij}$ naraščajoče po $j-i$, $i$ Časovna zahtevnost: $O(n^3)$ $$ \begin{alignedat}{3} c_{01} &= c_{12} = c_{23} = c_{34} = c_{45} = 0 \\[1ex] c_{02} &= 5 \\ c_{13} &= 4 \\ c_{24} &= 3 \\ c_{35} &= 3 \\[1ex] c_{03} &= 7 + \min\{4, 5\} &&= 11 &&\quad \text{režemo na $x_1$} \\ c_{14} &= 5 + \min\{3, 4\} &&= 8 &&\quad \text{režemo na $x_2$} \\ c_{25} &= 5 + \min\{3, 3\} &&= 8 \\[1ex] c_{04} &= 8 + \min\{8, 5+3, 11\} &&= 16 &&\quad \text{režemo na $x_1$ ali $x_2$} \\ c_{15} &= 7 + \min\{8, 4+3, 8\} &&= 14 &&\quad \text{režemo na $x_3$} \\[1ex] c_{05} &= 10 + \min\{14, 5+8, 11+3, 16\} &&= 23 &&\quad \text{režemo na $x_2$} \end{alignedat} $$ Optimalno rezanje: ```mermaid graph TD 05[0-10: 23] --- 02[0-5: 5] 05 --- 25[5-10: 8] 02 --- 01[0-3: 0] 02 --- 12[3-5: 0] 25 --- 23[5-7: 0] 25 --- 35[7-10: 3] 35 --- 34[7-8: 0] 35 --- 45[8-10: 0] ``` --- ### Naloga 5 Na voljo imamo kovance z vrednostmi $1 = v_1 < v_2 < \cdots < v_n$ in vsoto $C$, ki jo želimo izplačati s kovanci. Predpostavljamo, da imamo dovolj velik nabor kovancev. 1. Poišči izplačilo z najmanjšim številom kovancev za $C = 25$, $n = 4$ in $(v_i)_{i=1}^n = (1, 2, 5, 7)$. 2. S pomočjo dinamičnega programiranja reši problem v splošnem. --- ### Naloga 6 Imamo zaporedje $n$ polj, pri čemer je na $i$-tem polju zapisano število $a_i$. Na voljo imamo še $\lfloor n/2 \rfloor$ domin, z vsako od katerih lahko pokrijemo dve sosednji polji. Vsaka domina je sestavljena iz dveh delov: na enem je znak $+$, na drugem pa znak $-$. Posamezno polje lahko pokrijemo z le eno domino; če sta pokriti dve sosednji polji, morata biti pokriti z različnima znakoma (bodisi z iste, bodisi z druge domine). Iščemo tako postavitev domin, ki maksimizira vsoto pokritih števil, pomnoženih z znakom na delu domine, ki pokriva število. Pri tem ni potrebno, da uporabimo vse domine. ---- **Primer** dopustnega (ne nujno optimalnega) pokritja: | | [+ | -] | | | [- | +] | [- | +] | | -- | -- | -- | -- | -- | -- | -- | -- | -- | | 6 | 3 | -4 | 2 | -3 | 5 | 9 | 1 | 2 | Vsota tega pokritja je $3 - (-4) - 5 + 9 - 1 + 2 = 12$. Če bi eno od zadnjih dveh domin obrnili (zamenjala bi se znaka), dobljeno pokritje ne bi bilo dopustno, saj bi dve zaporedni polji bili pokriti z enakima znakoma. ---- 1. Zapiši rekurzivne enačbe za reševanje danega problema. Razloži, kaj predstavljajo spremenljivke, v kakšnem vrstnem redu jih računamo, ter kako dobimo optimalno rešitev. **Namig:** posebej obravnavaj dva primera glede na postavitev zadnje domine. 2. Oceni časovno zahtevnost algoritma, ki sledi iz zgoraj zapisanih enačb. 3. S svojim algoritmom poišči optimalno pokritje za zgornji primer.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.