# AiSD Lista 3
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| 1 | 2 | 1.5 | 2 | :0 | :0 | 2 | 1.8 | :0 |
| 1 | 2 | 1.5 | 2 lub Z-2.5 | Z-1.5 | Z-2 | 2 | 1.8 lub Z-2 | 2 |
## Zadanie 1
```cpp=
int gcd (int a, int b)
{
if (a == b) return a;
if (a < b) return gcd(b, a);
if (b == 0) return a;
if (b == 1) return 1;
if(a%2 == 1)
{
if (b%2 == 1)
{
// a i b nieparzyste
return gcd((a-b)/2, b);
}
else
{
//a nieparzyste, b parzyste
return gcd(a, b/2);
}
}
else
{
if (b%2 == 0)
{
// a i b parzyste
return 2*gcd(a/2, b/2);
}
else
{
//a parzyste, b nieparzyste
return gcd(a/2, b);
}
}
}
```
Zauważmy, że w każdym kroku co najmniej jedna z liczb a, b zmiejsza się co najmniej dwukrotnie:
- Jeśli a i b nieparzyste, to a zmiejsza się co najmniej dwukrotnie ($\frac{(a-b)*b}{2}$ < $\frac{a*b}{2}$).
- Jeśli a i b parzyste, to obie liczby zmiejszają się o połowę ($\frac{a*b}{4}$ < $\frac{a*b}{2}$).
- Jeśli a nieparzyste, b parzyste to b zmniejsza się o połowę ($\frac{a*b}{2}$ = $\frac{a*b}{2}$).
- Jeśli a parzyste, b nieparzyste to a zmniejsza się o połowę ($\frac{a*b}{2}$ = $\frac{a*b}{2}$).
Złożoność algorytmu: $O(log\ a\ +\ log\ b) = O(log\ ab)$
Algorytm Euklidesa
```cpp=
int Euklides (int a, int b)
{
if (a < b) return Euklides(b, a);
if (b == 0) return a;
return Euklides (b, a%b);
}
```
----------------
Zauważmy, że $a\%b$ jest z zakresu od 0 do (b-1)
Rozpatrzmy dwa przypadki:
- ${b \in [0;\frac{a}{2}]}$
wówczas $a' = b \leq \frac{a}{2}$
($b' = a \% b < b$)
czyli $a' * b' < (\frac{a}{2} * b = \frac{a*b}{2})$
$(a \% b)*b < \frac{a*b}{2}$
- ${b \in (\frac{a}{2};a]}$
wówczas $a' = b \leq a$
$b' = a\%b$, ale wiemy, że ${b \in (\frac{a}{2};a]}$, więc $b' \in [0, \frac{a}{2})$
czyli $a' * b' < (b * \frac{a}{2} = \frac{a*b}{2})$
$(a \% b)*b < \frac{a*b}{2}$
Złożoność algorytmu: $O(log\ a\ +\ log\ b) = O(log\ ab)$
## Zadanie 2
#### PODPUNKT 1
---------
***Rozpiszmy skąd dokładnie wzieło się to (${ \lceil \frac{3}{2}n-2 \rceil}$):***
(dla ułatwienia zakładamy, że $n = 2^{k},\ k \in \mathbb{N}$)
$$ T(n) = \begin{cases}
0 & \text{dla }\ n=1 \\ 1 & \text{dla}\ n=2 \\ 2T(\frac{n}{2})+2 & \text{dla}\ n>2
\end{cases}
$$
$T(n) = 2*T(\frac{n}{2})+2=2*[2*T(\frac{n}{4})+2]+2=4*T(\frac{n}{4})+4+2=...=16*T(\frac{n}{16})+16+8+4+2=...=$
$=2^{k-1}*T(\frac{n}{2^{k-1}})+2^{k-1}+2^{k-2}+...+2^{3}+2^{2}+2^{1}=2^{k}*2^{-1}*T(\frac{n}{2^{k-1}})+2^{k-1}+2^{k-2}+...+2^{3}+2^{2}+2^{1}=$
Zuważmy że $2^{k-1}+2^{k-2}+...+2^{3}+2^{2}+2^{1}$ to suma ciągu geometrycznego
$=n*\frac{1}{2}*T(2)+2*\frac{1-2^{k-1}}{1-2}=\frac{1}{2}*n*1+2(-1+2^{k-1})= \frac{1}{2}*n-2+n = \frac{3}{2}*n-2$
Wzór na sumę ciągu geometrycznego:
-
Zatem widzimy, że ${ \lceil \frac{3}{2}n-2 \rceil}$ porównań będzie wykonywanych, jeśli n będzie potęgą dwójki, bo w każdym kroku dzielimy tablicę na dwie równe części i każda z nich nadal bedzie podzielna na dwa i tak aż do momentu kiedy dojdziemy do tablic wielkości 2, a wtedy wukona się operacja $return\ (max(a_{1}, a_{2}),\ min(a_{1}, a_{2}))$, która wykonuje tylko jedno porównanie.
Ale czy są te jedyne dane dla, których wykona się ${ \lceil \frac{3}{2}n-2 \rceil}$ porównań?
Zapiszmy $2T(\frac{n}{2})+2$ jako $T(\lceil\frac{n}{2}\rceil)+T(\lfloor\frac{n}{2}\rfloor)+2$ oraz $n$ jako $n = 2_{k}+r$ gdzie $r < 2_{k}$.
**Wzór jawny:**
$$ T'(n) = \begin{cases}
0 & \text{dla }\ n=1 \\ 1 & \text{dla }\ n=2 \\ \frac{3}{2}*2^{k}+2r-2 & \text{dla}\ n>2 \wedge r \in [0, 2^{k-1}] \\ 2*2^{k}+r-2 & \text{dla}\ n>2 \wedge r \in (2^{k-1},2^{k})
\end{cases}
$$
Dowód wzoru jawnego:
**1) Podstawa indukcyjna:**
dla n = 1 wykonamy zero porównań
dla n = 2 wykonamy jedno porównanie
**2) krok indukcyjny:**
$n = 2^{k} + r$
Weźmy dowolne $k \in \mathbb{N}$ i załóżmy, że dla każdego $k' <= k$ teza działa. Pokażemy, że dla k+1 również działa.
1) $r \in [0,2^{k-1}]$
Dążymy do przekształcenia wzoru $T(n)=T(\lfloor \frac{2^{k}+r}{2} \rfloor) + T(\lceil \frac{2^{k}+r}{2} \rceil) + 2$ na $T'(n) = \frac{3}{2}*2^{k}+2r-2$.
Skoro $r \in [0, 2^{k-1}]$, to $\lceil r/2 \rceil, \lfloor r/2 \rfloor \in [0, 2^{k-2}]$.
$T(n) = T(2^{k}+r)=T(\lfloor \frac{2^{k}+r}{2} \rfloor) + T(\lceil \frac{2^{k}+r}{2} \rceil) + 2 = T( 2^{k-1}\lfloor \frac{r}{2} \rfloor) +T( 2^{k-1}\lceil\frac{r}{2} \rceil) + 2$
$=(\frac{3}{2}*2^{k-1}+2* \lfloor \frac{r}{2} \rfloor - 2) + (\frac{3}{2}*2^{k-1}+2* \lceil \frac{r}{2} \rceil - 2) + 2= 2*\frac{3}{2}*2^{k-1} + 2*(\lfloor \frac{r}{2} \rfloor + \lceil \frac{r}{2} \rceil) -2$
$=\frac{3}{2}*2^{k} + 2r -2=T'(2^{k+1}+r) = T'(n)$
2) $r \in (2^{k-1}, 2^{k})$
Dążymy do przekształcenia wzoru $T(n)=T(\lfloor \frac{2^{k}+r}{2} \rfloor) + T(\lceil \frac{2^{k}+r}{2} \rceil) + 2$ na $T'(n) = 2*2^{k}+r-2$.
$T(n) =T(2^{k}+r)= T(\lfloor \frac{2^{k}+r}{2} \rfloor) + T(\lceil \frac{2^{k}+r}{2} \rceil) + 2 =$
$=(2* 2^{k-1} -2+\lfloor \frac{r}{2} \rfloor) + (2* 2^{k-1} -2+\lceil \frac{r}{2} \rceil) + 2 = 2*2^{k}+r-2 = T'(n)$
--------
Do znalezienia wzoru, wyrażającego wszystkie możliwe moce zbiorów dla których zostanie wykonanych optmalna ilość porównań ($\lceil \frac{3}{2}n-2 \rceil$) wykorzystamy wzór jawny.
$\lceil \frac{3}{2}n-2 \rceil = \lceil \frac{3}{2}(2^k+r)-2 \rceil = \lceil \frac{3}{2}*2^k+\frac{3}{2}*r-2 \rceil = \frac{3}{2}*2^k-2+\lceil \frac{3}{2}*r\rceil$
Rozpatrzmy przypadki:
- $0 \leq r \leq 2^{k-1}$
$\frac{3}{2}*2^{k} - 2 + 2r = \frac{3}{2}*2^{k} - 2 + \lceil \frac{3}{2}r \rceil$
$2r = \lceil \frac{3}{2}r \rceil$
$2r = r + \lceil \frac{r}{2} \rceil$
$r = \lceil \frac{r}{2} \rceil$
$r=0 \lor r=1$
- $2^{k} > r> 2^{k-1}$
$2*2^{k} - 2+r =\frac{3}{2}*2^{k} - 2 + \lceil \frac{3}{2}r \rceil$
$2*2^{k}+r = \frac{3}{2} * 2^{k} +r+\lceil \frac{r}{2} \rceil$
$2^{k+1} = 3 * 2^{k-1} +\lceil \frac{r}{2} \rceil$
$2^{k+1}-3 * 2^{k-1} =\lceil \frac{r}{2} \rceil$
$2^{k-1}(2^{2}-3)=\lceil \frac{r}{2} \rceil$
$2^{k-1} = \lceil \frac{r}{2} \rceil$
Szukamy takiego $r$, dla którego powyższe równanie będzie spełnione:
$2^{k-1} = \lceil \frac{2^{k}-1}{2} \rceil$
$2^{k-1} = \lceil 2^{k-1}-\frac{1}{2} \rceil$
$2^{k-1} = 2^{k-1}-0$
$r=2^{k}-1$
zatem $n = 2^{k}+2^{k}-1=2^{k+1}-1$
Rozpatrujemy przypadki dla $r \in [0, 2^{k})$. Zauważmy jednak, że możemy nieco uprościć sobie dalsze obliczenia stosując skrót $r=-1$ dla k+1.
-------
***Dowód indukcyjny***
**Teza**
Dla dowolnego $n \in \mathbb{N},\ n = 2^{k}\ \text{lub}\ n=2^{k} \pm 1$ wykonujemy ${ \lceil \frac{3}{2}n-2 \rceil}$
**Podstawa indukcji:** Pokażemy, że dla $n=0$, $n=1$ i $n=2$ wykonamy (${ \lceil \frac{3}{2}n-2 \rceil}$) porównań
* dla n=0 trywnailnie nie wykonujemy, żadnego porównania (tablica pusta)
* dla n=1 trywialnie, zero porównań
* dla n=2 wykonujemy jedno porównanie (z zad. $return\ (max(a_{1}, a_{2}),\ min(a_{1}, a_{2}))$ wykonuje tylko jedno porównanie), a ${ \lceil \frac{3}{2}*2-2 \rceil} = 1$
**Krok indukcyjny:**
Weźmy dowolne $k \in \mathbb{N}$ i załóżmy, że teza jest spełniona. Pokażemy, że dla k+1 też.
Rozpatrzmy przypadki:
* $n = 2^{k}$ wówczas $n' = 2^{k+1} = 2^{k}+2^{k}$
Chcemy pokazać równość:
${ \lceil \frac{3}{2}*2^{k} -2 \rceil} + { \lceil \frac{3}{2}*2^{k} -2 \rceil} + 2 = { \lceil \frac{3}{2}*2^{k+1} -2 \rceil}$
(łączymy dwa poddrzewa wielkości $2^{k}$ - dla nich wiemy, że zachodzi teza. Łączenie dodaje nam dodatkowe 2 porównania).
$\lceil \frac{3}{2}*2^{k} -2 \rceil + \lceil \frac{3}{2}*2^{k} -2 \rceil + 2 = 3*2^{k-1} -2 + 3*2^{k-1} -2 +2 = 2*(3*2^{k-1}) - 2 =$
$= 3*2^{k} - 2 = \lceil 3*2^{k} - 2 \rceil =\lceil \frac{3}{2}*2^{k+1} - 2 \rceil$
* $n = 2^{k}- 1$
Skorzystamy z tożsamości $n=\lfloor \frac{n}{2} \rfloor + \lceil \frac{n}{2} \rceil$
Czyli $2^{k+1}-1=\lfloor \frac{2^{k+1}-1}{2} \rfloor + \lceil \frac{2^{k+1}-1}{2} \rceil = (2^{k}-1) + 2^{k}$
Chcemy pokazać równość:
${ \lceil \frac{3}{2}*(2^{k}-1) -2 \rceil} + { \lceil \frac{3}{2}*2^{k} -2 \rceil} + 2 = { \lceil \frac{3}{2}*(2^{k+1}-1) -2 \rceil}$
Rozpiszmy: ${\lceil \frac{3}{2}*(2^{k}-1) -2 \rceil} + { \lceil \frac{3}{2}*2^{k} -2 \rceil} + 2 =$
$=\lceil \frac{3}{2}*2^{k} - \frac{3}{2}*1-2 \rceil + \lceil \frac{3}{2}*2^{k} -2 \rceil + 2 = \lceil 3*2^{k-1} - \frac{3}{2} -2\rceil + \lceil \frac{3}{2}*2^{k} -2 \rceil + 2=$
$(3*2^{k-1} + \lceil -\frac{3}{2} \rceil - 2) + (3*2^{k-1} - 2) + 2 = (3*2^{k-1} - 1 - 2) + (3*2^{k-1} - 2) + 2 =$
$= 2*3*2^{k-1} - 3 - 2 + 2 = \frac{3}{2}*2^{k+1} - 3 = \frac{3}{2}*2^{k+1} +\lceil -\frac{3}{2} \rceil - 2=\lceil \frac{3}{2}*2^{k+1} - \frac{3}{2} -2\rceil$
$=\lceil \frac{3}{2}*(2^{k+1} - 1) -2\rceil$
* $n = 2^{k}+ 1$
Skorzystamy z tożsamości $n=\lfloor \frac{n}{2} \rfloor + \lceil \frac{n}{2} \rceil$
Czyli $2^{k+1}+1=\lceil \frac{2^{k+1}+1}{2} \rceil + \lfloor \frac{2^{k+1}+1}{2} \rfloor = (2^{k}+1) + 2^{k}$
Chcemy pokazać równość:
${ \lceil \frac{3}{2}*(2^{k}+1) -2 \rceil} + { \lceil \frac{3}{2}*2^{k} -2 \rceil} + 2 = { \lceil \frac{3}{2}*(2^{k+1}+1) -2 \rceil}$
Rozpiszmy: ${\lceil \frac{3}{2}*(2^{k}+1) -2 \rceil} + { \lceil \frac{3}{2}*2^{k} -2 \rceil} + 2 =$
$=\lceil \frac{3}{2}*2^{k} + \frac{3}{2}*1-2 \rceil + \lceil \frac{3}{2}*2^{k} -2 \rceil + 2 = \lceil 3*2^{k-1} + \frac{3}{2} -2\rceil + \lceil \frac{3}{2}*2^{k} -2 \rceil + 2=$
$(3*2^{k-1} + \lceil \frac{3}{2} \rceil - 2) + (3*2^{k-1} - 2) + 2 = (3*2^{k-1} + 2 - 2) + (3*2^{k-1} - 2) + 2 =$
$= 2*3*2^{k-1} - 2 + 2 = \frac{3}{2}*2^{k+1} = \frac{3}{2}*2^{k+1} + \lceil \frac{3}{2} \rceil - 2 = { \lceil \frac{3}{2}*(2^{k+1}+1) -2 \rceil}$
#### PODPUNKT 2
**Jak bardzo może liczba porównań odbiegać od optymalnej?**
Oznaczmy R(n) jako liczbę nadmiarowych porównań.
Szukamy n takiego, że $R(n)=T(n) - OPT(n)$ jest maksymalne,
Wiemy, że $OPT(n) = \lceil \frac{3}{2} n -2\rceil$
Z podpunktu 1) wiemy bowiem, że:
- $0 \leq r \leq 2^{k-1}$
$R(n) = r - \lceil \frac{r}{2} \rceil$ dla jakich $n$ jest maksymalny?
Dla $r=2^{k-1}$ czyli dla $n=2^{k} + 2^{k-1}$
$R(2^{k} + 2^{k-1})=2^{k-1}-2^{k-2}=(2-1)*(2^{k-2})=2^{k-2}$, wówczas $R(n)=2^{k-2}$
- $2^{k-1}<r<2^{k}$ czyli $2^{k-2}<\frac{r}{2}<2^{k-1}$
$R(n) = 2^{k-1} - \lceil \frac{r}{2} \rceil$ dla jakich $n$ jest maksymalny?
Dla $r = 2^{k-1}+1$, czyli dla $n = 2^{k}+2^{k-1}+1$
$R(2^{k}+2^{k-1}+1)=2^{k-1}-\lceil \frac{2^{k-1}+1}{2}\rceil = 2^{k-1}-\lceil 2^{k-2} + \frac{1}{2}\rceil = 2^{k-1}-2^{k-2}-1=2^{k-2}-1$
Interesuje nas maksymalna wartość R(n), zatem z powyższech wybierzemy $n=2^{k} + 2^{k-1}$
Pokażmy, że faktycznie tak jest:
$R(n)=T(n)-OPT(n) = \frac{3}{2} * 2^{k} - 2 + 2r - (\frac{3}{2}*2^{k}-2+\lceil \frac{3*r}{2} \rceil)=$
$= \frac{3}{2} * 2^{k} - 2 + 2r - \frac{3}{2}*2^{k}+2-(r+\lceil\frac{r}{2} \rceil)=$
$=\frac{3}{2} * 2^{k} - 2 + 2r - \frac{3}{2}*2^{k}+2-\lceil \frac{r}{2} \rceil-r= 2r - \lceil \frac{r}{2}\rceil-r=r- \lceil\frac{r}{2} \rceil = 2^{k-1} - \lceil\frac{2^{k-1}}{2} \rceil=$
$=2^{k-1}-2^{k-2}=2^{k-2}$
$n = 2^{k}+r = 2^{k}+2^{k-1}=2*2^{k-1}+2^{k-1}=3*2^{k-1}=6*2^{k-2}$
$2^{k-2}=\frac{n}{6}$
#### PODPUNKT 3
```cpp =
Procedure MaxMin(S:set)
if |S|=1 then return {a1, a1}
else
if |S|=2 then return (max(a1, a2), min(a1, a2))
else
if |S| % 2 == 0 && |S|/2 % 2 == 1 then
podziel S na S1 i S2, tak że |S1|=|S|/2+1 oraz |S2|=|S|/2-1
else
podziel S na dwa równoliczne podzbiory S1, S2;
//z dokładnością do jednego elementu
(max1, min1) <- MaxMin(S1)
(max2, min2) <- MaxMin(S2)
return (max(max1, max2), min(min1, min2))
```
W każdym kroku algorytmu sprawdzamy czy podział tablicy o parzystej długości spowoduje utworzenie podtablic o nieparzystej długości. Jeśli tak, to modyfikujemy algorytm w taki sposób, żeby uzyskać podtablice o parzystej długości. Dzięki temu, będziemy wykonywać mniej porównać, bo w końcowych wywołaniach (w "liściach") dostaniemy zbiory dwuelementowe, a wiemy, że one wymagają tylko jednego porównania. W podstawowej wersji algorytmu w "liściach" dostawaliśmy trzyelementowe tablice, co powodowało większą niż optymalną ilość porównań.
## Zadanie 3
ARTYKUŁ - https://algorithmtutor.com/Computational-Geometry/An-efficient-way-of-merging-two-convex-hull/
Dla zbioru wierzchołków, którego moca <=4 wyznaczenie otoczki jest 
0) wybieramy najbardziej na prawo wysuniety punkt lewej otoczki, oznaczamy go $p$ i najbrdziej wysuniety na lewo punkt prawej otoczki, oznaczamy go $q$
1) punkt $p$ pozostaje nieruchomo, w nim zaczepimy nasza "wskazówkę" (prostą z $p$ do $q$). Wyznaczamy punkt $q'$, który będzie kolejnym wierzchołkiem w prawej otoczce, idąc zgodnie z ruchem wskazówek zegara. Teraz sprawdźmy, jak przesynęł się nasza wskazówka, jeśli przeciwnie do ruchu wskaówek zegara to nasze $q'$ to nowe $q$ i powtarzamy ten krok, wpp. przechodzimy do punktu 2).
2) punkt $q$ pozostaje nieruchomo, w nim zaczepimy nasza "wskazówkę" (prostą z $q$ do $p$). Wyznaczamy punkt $p'$, który będzie kolejnym wierzchołkiem w lewej otoczce, idąc przeciwnie z ruchem wskazówek zegara. Teraz sprawdźmy, jak przesunęła się nasza wskazówka, jeśli zgodnie z ruchem wskaówek zegara to nasze $p'$ to nowe $p$ i powtarzamy ten krok, wpp. przechodzimy do punktu 3).
3) powtarzamy punkty 1) i 2), aż do momentu, w którym $p$ i $q$ się "ustabilizują" tzn. nie będą się już zmieniały
```
$\rightarrow$ Zauważmy, że algorytm ten zachowuje właśność STOP-u, ponieważ otoczki wypunkłe, które towżymy w każdym z kroków, są konstruowane na podstawie dwóch wielokątów wypukłych.Zatem jeżeli znajdziemy wierzchołek, dla którego wybór kolejnego wierzchołka nie jest już poprawny, to wiemy, że każdy kolejny
```
Analogicznie, szukamy dolnej granicy.
Porównajmy:
| | jak wyznaczamy | kiedy ok? |
| --- | --- | --- |
| | |
| górna q | zgodnie | przeciwnie |
| górna p | przeciwnie |zgodnie |
| | |
| dolna q| przeciwnie | zgodnie |
| dolna p| zgodnie | przeciwnie |
Na podstawie Cormen strona 1040:
Aby sprawdzić, czy odcinek skierowany $qp$ jest położony zgodnie z ruchem wskazówek zegara w stosunku do odcinka skierowanego $qp'$ względem ich wspólnego końca $q$, wykonujemu przesunięcie punktu $q$ do początku układu. To znaczy, oznaczmy jako $p-q$ to wektor $p_{1}'= (x_{1}', y_{1}')$, gdzie $x_{1}'=x_{1}-x_{0}$, a $y_{1}'=y_{1}-y_{0}$ i podobnie definiujemy $p'-q$. Następnie obliczamy iloczyn wektorowy $(p-q)\times(p'-q)=(x_{1}-x_{2})*(y_{2}-y_{0})-(x_{2}-x_{0})*(y_{1}-y_{0})$. Jeśli jego wartość jest dodatnia to odcinek skierowany $qp$ jest położony zgodnie ze wskazówkami zegara, w stosunku do $qp'$ (jeśli jest ujemna to przeciwnie).
**Algorytm:**
Przechowujemy wierzchołki znajdujące się na otoczkach L i P (lewa i prawa) na listach dwukierunkowych. Będziemy na niej przechowywać współrzędne punktu oraz wskaźnik do poprzedniego i następnego wierzchołka.
```cpp=
// zwraca 1 jeśli zgodnie
// zwraca 0 jeśli przeciwnie
funkcja czy_zgodnie(a, b, b')
fi = (b.x - a.x)(b'.y - a.y) - (b'.x - a.x)(b.y - a.y);
jeżeli fi > 0 : zwróć 0
wpp.: zwróć 1
funkcja krawedz_gorna():
p = najbardziej wysunięty na prawo wierzchołek w L
q = najbardziej wysunięty na lewo wierzchołek w P
p' = p.poprzedni
q' = q.nastepny
Wykonaj:
flaga = 0
Dopóki czy_zgodnie(p, q, q') == 0:
q = q'
q' = q'.nastepny
flaga = 1
Dopóki czy_zgodnie(q, p, p') == 1:
p = p'
p' = p'.poprzedni
flaga = 1
Dopóki flaga == 1;
funkcja krawedz_dolna():
p = najbardziej wysunięty na prawo wierzchołek w L
q = najbardziej wysunięty na lewo wierzchołek w P
p' = p.nastepny
q' = q.poprzedni
Wykonaj:
flaga = 0
Dopóki czy_zgodnie(p, q, q') == 1:
q = q'
q' = q'.poprzedni
flaga = 1
Dopóki czy_zgodnie(q, p, p') == 0:
p = p'
p' = p'.nastepny
flaga = 1
Dopóki flaga == 1;
wpp.: zwróć 0
```
**Definicja:** Wielokąt wypukły to taki, w którym wszystkie kąty mają miary $\leq 180^{\circ}$
**Poprawność**:
Wiemy że otoczka wypukła, którą wyzanczył powyższy algorytm zawiera wszystkie wierzchołki, ponieważ za każdym razem złączamy dwie otoczki wypukłe, a one zawierają wszystkie punkty swojego zbioru.
Wyznaczona otoczka jest wielokątem wypukłym, ponieważ wiemy, że algorytm znajduje najwyżej położoną prostą, której zmiana jednego z wierzchołków na kolejny wierzchołek poprzedniej otoczki liniowej spowodowałby wykluczenie z otoczki co najmniej jednego punktu, który w tej otoczce powinien sie znajdować.
Działania opieramy na figurze wypukłej, czyli figurze, której kąty wewnętrzne nie przekraczają 180 stopni. Jeżeli więc za punktem q', który nie spełnia warunku naszego algorytmu, znalazłby sie punkt położony wyżej od aktualnego q to okazałoby sie, że jest to figura wklęsła.
Wiemy że gdybysmy "przeszli się" po otoczce liniowej to zawsze będziemy skręcać w jedną stronę - tylko w lewo lub tylko w prawe.
***CORMEN str.1053-1063 z odnośnikiem do iloczynu wektorów (33.1)***
## Zadanie 4
Schemat postępowania:
1) indeksujemy wszystkie wierzcholki drzewa
2) w petli ustalamy wierzcholek i-ty jako korzen i puszczamy z niego BFS
3) jesli jakis wierzcholek ma dlugosc C od korzenia i indeks tego wierzcholka jest mniejnszy niz indeks korzenia* to wypisujemy pare korzen-wierzcholkek
4) przechodzimy do kolejnego wierzcholka jako korzenia (3)
\* zeby nie wypisac wszytskich par dwukrotnie
Algorytm
```
funkcja BFS (Graf G, Wierzchołek s)
dla każdego wierzchołka u z G:
kolor[u] = biały
odleglosc[u] = inf
rodzic[u] = NIL
kolor[s] = SZARY
odleglosc[s] = 0
rodzic[s] = NIL
Q.push(s)
dopóki kolejka Q nie jest pusta:
u = Q.front()
Q.pop()
dla każdego v z listy sąsiedztwa u:
jeżeli v jest biały:
kolor[v] = SZARY
odleglosc[v] = odleglosc[u] + wagakrawedzi u-v
rodzic[v] = u
Q.push(v)
kolor[u] = CZARNY
dla i od s do |V(G)|: # Usuwanie duplikatów
jeżeli odleglosc[i]=C:
wypisz pare (s,i)
funckja glowna
dla kazdego wierzcholka s wywolaj
BFS(G,s)
```
## Zadanie 5
## Zadanie 6
## Zadanie 7
### (a)
**Macierz Teoplitza**
(aby wygodniej móc działać na macierzy w algorytmie będziemy ją reprezentować jako wektor, w którym pierwsze (n-1) wartości to pierwsza kolumna zapisana od dołu a kolejne n wartości to pierwszy wiersz zapisany od lewej do prawej)
Zauważmy, że macierze Teoplitza z definicji na przekątnych mają te same wartości. Zauważmy zatem, że możemy je pamiętać jako pojedyńczy wektor (lub tablicę) o wielkości $n+(n-1)=2n-1$, ponieważ wystarczy, że zapamiętamy pierwszy wiersz oraz pierwszą kolumnę, a komórkę $(0, 0)$ wsytarczy zapisać raz.
Zauważmy teraz, że w wyniku dodawania dwóch macierzy Teoplitza otrzymamy macierz Teoplitza. Teraz dodawanie dwóch macierzy sprowadza się do dodania do siebie dwóch wektorów o wielkości $2n-1$ każdy. Zatem mamy $O(4n) = O(n)$
### (b)
**Idea rozwiązania:**
Zauważmy, że możemy mnożenie macierzy Teoplitza (o rozmiarze $n$) przez wektor możemy rozpisać za pomocą powyższej zależności. Wówczas wystarczy wykonać następujące działania:
- $X = A*(u+v)$
- $Y = (B-A)*v$
- $Z = (C-A)*u$
zauważmy, że A, B, C to również macierze Teoplitza ale rozmiaru $\frac{n}{2}$.
Wtedy wynikiem będzie wektor postaci:
$\left[\begin{array}{c}
X + Y \\
X + Z
\end{array}\right]$
Zauważmy jednak, że dla $n$ nie będących potęgą 2, w pewnym kroku algorytmu dojdzeimy do macierzy o wielkości m, takiej że $2 \nmid m$, której nie będziemy wstanie podzielić w powyższy sposób tj. na cztery macierze Teoplitza. Rozszerzmy zatem naszą macierz do wielkości $n'$ będącej najbliższą orginalnemu $n$ liczbą będącą potęgą 2, czyli $n'=2^{\lceil log_{2}n \rceil }$. Natomiast wektor $V$ przez który mnożymy macierz $M$ rozszerzymy do rozmiaru $n'$ dopisując zera.
Widzimy, że takie działanie nie zaburzy wyniku, gdyż dopisane do macierzy $M$ kolumny wyzerują się po przemnożeniu przez dopisane do wektora $V$ zera. Natomiast z wektora wynikowego zwrócimy tylko $n$ pierwszych wartości, więc nadmiarowe (powstałe z dopisanych wierszy) zostaną zignorowane.
Rozpiszmy:
$l$ - długość wektora, który reprezentuje macierz $M$ (według reprezentacj iz podpunktu (a))
$l = 2n'-1$
$k$ - długość wektorów, które reprezentują macierze $A, B, C$
$k=\lfloor \frac{l}{2} \rfloor$
$A = M[\lfloor \frac{k}{2} \rfloor +2,...,\ \frac{l+k}{2}]$
$B = M[k+2,...,\ l]$
$C = M[1,...,\ k]$
**Algorytm:**
```cpp=
// l - długość macierzy M w postaci z podpunktu a
vector<int> MMT(vector M, vector v, int l)
{
if(l == 1)
{
return M[0] * v[0];
}
int k = floor(l/2);
vector<int> A = M[floor(k/2)+2...(l+k)/2]
vector<int> B = M[k+2...l]
vector<int> C = M[1...k];
// rozmiar wektora v to ceil(l/2), tzn. k + 1, bo k=floor(l/2) i l jest nieparzyste
vector<int> u = v[1...(k+1)/2];
vector<int> w = v[(k+1)/2+1...k+1];
vector<int> X = MMT(A, u+w, k);
vector<int> Y = MMT(B-A, w, k);
vector<int> Z = MMT(C-A, u, k);
return vector<int>{X+Y, X+Z};
// otrzymujemy wektor wynikowy długości ceil(l/2)
}
```
Z wektora wynikowego, który zwróci ta funkcja wyciągamy tylko pierwsze n elementów.
**Ile operacji arytmetycznych?**
odejmowanie C-A to l/2 odejmowań
odejmowanie B-A to l/2 odejmowań
dodawanie U+W to (l-1)/4 dodawań
dodawanie X + Y to (l-1)/4 dodawań
dodawanie X + Z to (l-1)/4 dodawań
3 * mnożenie macierzy Toepliza l/2 x l/2
**Złożoność czasowa:**
$l=2^{\lceil log_{2}n \rceil }$ zatem $l \geq n$
$T(l) = 3T(\frac{l}{2}) + O(l)$
Zatem z twierdzenia o rekursji uniwersalnej: $T(l) = O(l^{log_{2}3})$
$O(l^{log_{2}3}) = O((2^{\lceil log_{2}n \rceil })^{log_{2}3}) \leq O((2^{log_{2}(n)+1})^{log_{2}3})= O((2^{log_{2}n}*2)^{log_{2}3})=O(n^{log_{2}3} *3)=O(n^{log_{2}3})$
## Zadanie 8
##### WERSJA KOŃCOWA
IDEA:
W każdej z tablic znajdujemy medianę, co potrafimy zrobić w czesie O(1), ponieważ znamy długość każdej tablicy (n), a mediana znajduje się w $\lfloor n/2 \rfloor$. Ustalamy która z tablic ma mediane maksymalną i minimalną. Następnie ustalamy minimum z elementów, które minimalna mediana ma przed sobą i elementów, które mediana maksymalna ma po sobie. Usuwamy tyle elementów przed miedianą minimalną i po medianie maksymalnej.
W momencie, w którym w jednej z trzech tablic dojdziemy do momentu gdy ma ona długość 2 to jej mediana jest pierwszym elementem w tablicy.
Algorytm postępowania w tej sytuacji wygląda tak, że należy usunąc pierwszy element z tablicy w której mediana jest minimalna i jeden element z tablicy, w której mediana jest maksymalna. Jest to krok podobny w działaniu do normalnego kroku postępowania.
Dlaczego możemy usunąc medianę minimalną?
Nie możliwe jest to aby minimalna mediana 3 zbiorów była mediana złączenia tych 3 zbiorów,
ponieważ wiemy, że po prawej stronir złaćzonego zbioru z trzech tablic będzie na tyle dużo elemetnów że miejsce mediany będzie zajęte przez liczbę większa nić minimalna mediana. Dlaczego?
Dlatego, że wiemy, że po prawej stornie tablicy złączonej będzie jeden element z tablicy dwuelementowej, a z pozostałych zawsze będzie więcej niż połowa.
PRZYPADEK GDY TABLICA JEST PARZYSTEJ DŁUGOŚCI
n/2 + mediana(która znajduje się na pozycji n/2-1)
PRZYPADEK GDY TABLICA JEST NIEPARZYSTEJ DŁUGOŚCI
$\lfloor n/2 \rfloor$ + mediana
Następnie na obu tablicach wywołujmey binsearch z elementem z tablicy, która jest jednoelementowa. Wiedząc na których pozycjach w obu tablicach znajdowłby się ten elemen (oznaczmy przez m1 i m2) jesteśmy w stanie określić gdzie znajdowałby się ten element w tablic złączonej z 3 tablic o długośći n+m+k. Była bo to pozycja o indkesie m1+m2-1.
Jeżeli $m1+m2-1$ == $\frac{n+m+k}{2}$ to znaleźliśmy medianę i koniec.
Jeżeli $m1+m2-1$ > $\frac{n+m+k}{2}$ to wiemy, że możemy usunąc sobie z pamięci jednoelementową tablicę, ale również usuwamy najmniejszy element z obu pozostałych tablic.
Jeżeli $m1+m2-1$ < $\frac{n+m+k}{2}$ to przypadek jest analogiczny do przypadku wyżej, ale usuwamy elemetn największy.
Następnie na pozostałych dwóch tablicach uruchamiamy krok poszykiwania mediany, który jest taki sam jak krok pierwszy. Czyli ustalamy medianę dla obu tablic a następnie usuwamy minimalną ilośc po wiekszej medianie i przed mniejszą medianą.
## Zadanie 9
Sign in with Wallet
Connect another wallet