Porgramozási tételek
Összegzés
Adott \(f:\Z\to\Z\)
\(A=\big(m:\Z,\;n:\Z,\;d:\N\big)\)
\(B=\big(m':\Z,\;n':\Z\big)\)
\(Q=\big(m=m'\land n=n'\land m\le n+1\big)\)
\(R=\Big(Q\land s= \underset{i=m}{\overset{n}{\large{\sum}}}\,f(i)\Big)\)
\(P=\Big(Q\land s = \underset{i=m}{\overset{k}{\large{\sum}}}f(i)\;\land\;k\in[m-1\;..\,n] \Big)\)
\(Q'=\Big(Q\,\land\,k=m-1\,\land\,s=0\Big)\)
\(Q''=\Big(P^{k\leftarrow k+1}\,\land\,n-k=t_0\Big)\)
\(\pi=(k\ne n)\)
\(t=(n-k)\)
Megszámlálás
\(\beta:\Z\to\mathbb{L}\)
\({\large\chi}:\;\mathbb{L}\to\{1,0\}\)
\(A=\big(m:\Z,\;n:\Z,\;d:\N\big)\)
\(B=\big(m':\Z,\;n':\Z\big)\)
\(Q=\big(m=m'\land n=n'\land m\le n+1\big)\)
\(R=\Big(Q\land s= \underset{i=m}{\overset{n}{\large{\sum}}}\,f(i)\Big)\)
\(P=\Big(Q\,\land\,d=\underset{i=m}{\overset{k}{\large{\sum}}}\,{\large{\chi}}\big(\beta(i)\big)\,\land\,k\in[m-1\,..\,n]\Big)\)
\(k\in\Z\)
\(Q'=\Big(Q\,\land\,k=m-1\,\land\,d=0\Big)\)
\(Q''=\Big(P^{k\leftarrow k+1}\land n-k = t_0\Big)\)
\(\pi=(k\ne n)\)
\(t=(n-k)\)
Maximumkeresés
Adott \(f:\Z\to H\)
Ahol \(H\) teljesen rendezett
\(A=\big(m:\Z,\;n:\Z,\;\max:H,\;i:\Z\big)\)
\(B=\big(m':\Z,\;n':\Z\big)\)
\(Q=\big(m=m'\land n=n'\land m\le n\big)\)
\(R=\Big(Q\land\,i\in[m\,..\,n]\land\max=f(i)\land\forall j \in[m\,..\,n]:\;f(j)\le f(i)\Big)\)
\(P=\Big(Q\land\,i\in[m\,..\,k]\land\max=f(i)\land\forall j \in[m\,..\,k]:\;f(j)\le f(i)\land k\in[m\,..\,n]\Big)\)
\(Q'=\Big(Q\land k=m \land i = m \land \max = f(m)\Big)\)
\(Q''=\Big(P^{k\leftarrow k+1}\land n-k =t_0\Big)\)
\(\pi= (k\ne n)\)
\(t=(n-k)\)
\(\pi_1= (f(k+1)\ge \max)_{i,max:=k+1,f(k+1)}\)
\(\pi_2= (f(k+1)\le \max)_{SKIP}\)
Lineáris keresés
Zavar az erőben :flushed:
Lineáris keresés - 1
- Feltételezzük, hogy a keresett elem benne van a tömbben
- \(\Beta:\Z\to\mathbb{L}\)
- Keressük az első \(m\)-nél kissebb egészet, ahol \(\beta\) teljesül (előtte semmire nem teljesül)
\(A=\big(m:\Z,\;i:\Z\big)\)
\(B=\big(m':\Z\big)\)
\(Q=\big(m=m'\land \exists j \ge m: \beta(j))\)
\(R=\big(Q\land i\ge m\land\beta(i)\land \forall j \in[m..i-1]:\neg\beta(j)\big)\)
\(P=\big(Q\land i\ge m\land \forall j \in[m..i-1]:\neg\beta(j)\big)\)
\(Q'=\big(Q\land i=m\big)\)
\(t = N-i\)
\(\pi= \neg\beta(i)\)
Lineáris keresés - 2
\(\beta: \Z\to\mathbb{L}\) helyettesítése \(\pi\) feltétellel
\(A=\big(m:\Z,\;i:\Z\big)\)
\(B=\big(m':\Z\big)\)
\(Q=\big(m=m'\land \exists j \ge m: \beta(j))\)
\(R=\big(Q\land i\ge m\land\beta(i)\land \forall j \in[m..i-1]:\neg\beta(j)\big)\)
\(P=\Big(Q\land i\ge m\land \forall j \in[m..i-1]:\neg\beta(j)\green{\land \ell=\big(\exists j\in[m..i-1]:\beta(i)\big)}\Big)\)
\(Q'=\big(Q\land i=m-1\land \ell = \bot\big)\)
\(Q''=\Big(Q\land i+1\ge m-1 \land \forall j \in [m..i]:\green\neg\beta(j)\land \green{\ell=\big(\exists j \in [m..i+1]:\beta(j)\big)\land N-i=t_0}\Big)\)
\(\pi=\neg\ell\)
\(t=N-i\)
Lineáris keresés - 3
- \(\gamma:\Z\to\mathbb{L}\) keresett tulajdonság
- \(\delta:\Z\to\mathbb{L}\) korlátozó tulajdonság
- Keressük az első \(\gamma\)-nak megfelelő indexet követő első \(\delta\)-nak megfelelő indexet
\(A=\big(m:\Z,\;i:\Z\big)\)
\(B=\big(m':\Z\big)\)
\(Q=\big(m=m'\land \exists j \ge m: \delta(j))\)
\(R=\Big(Q\land \ell = \big(\exists j \ge m: \gamma(j)\land\forall k\in [m..j-1]:\neg\delta(k)\big) l\to \big(i\ge m \land\gamma(i)\land\forall j\in[m..i-1]:(\neg \gamma(j)\land\neg\delta(j))\big)\Big)\)
\(P=\Big(Q\land \ell = \big(\exists j \ge m: \forall k\in [m..j-1]:\neg\delta(k)\big)\land\ell=\big(\exists j\in[m..i] \gamma(j)\big)\land n=\big(\exists j \in [m..i]: \delta(j) \big)\land i\ge m-1\Big)\)
\(Q'= \big(Q\land i=m-1\land\ell=\bot\land n= \bot\big)\)
\(\pi=\neg\ell\)
\(t = m-i\)
not sure