# AiSD LISTA 5

| 1 | 2 | 3(Z) | 4 | 5(Z) | 6 | 7(Z) |
| - | - | - | - | - | - | - |
| 1 | 2 | 1 | 1 | | 1 | |

### ZAD 1
Liczby przechowywane w drzewie decyzyjnym mogą byc jedynie porównywane.

Tezę podaną w treści zadanie potwierdzimy przykładem.
Rozpatrzmy dwa różne rozłożenia 4 punktów, dla których otoczka wypukła jest inna.
Te dwa ułożenia są do siębie bardzo podobne. Różnią sie jedynie położeniem punktu P, który na obrazku 1 i 2 odpowiednio nazywa się $P_1$ i $P_2$.

| obrazek 1| obrazek 2 |
| -------- | --------- |
| $w_2.x < x_1 < w_3.x$ | $w_2.x < x_2 < w_3.x$ |
| $w_2.y < y_1 < w_1.y$ | $w_2.y < y_2 < w_1.y$ |

Widzimy zatem, że w oba przypadki są nierozróżnialne pomimo że mają różne rozwiązania. Zatem przy pomocy drzew decyzyjnych nie da się rozwiązać tego problemu.

### ZAD 2
Opisany w treści zadania problem sprowadza się do sprawdzenia czy w danym ciągu istnieja 3 jakiekolwiek liczby, po tkróeych dodaniu otrzymamy liczbę 0.

ciąg danych wejściowych przedstawiany jest jako - $x_1, x_2, ..., x_n$
Taki ciąg możemy reprezentować również jako punkt w przestrzeniu n wymiarowej, czyli $x_1, x_2, ..., x_n \in R^n$

(W drzewach decyzyjnych mogliśmy porównywać dwie liczby. W przypadku liniowych drzew decyzyjnych porównujemy kombinacje liniowe danych na wejściu.)

W przypadku tego zadania odpowiednim będzie skorzystanie z liniowych drzew decyzyjnych, które są drzewami trynarnymi, czyli takimi, że z wierzchołka poprowadzone sa trzy krwędzie prowadzoące do synów. Tutaj w wierzchołkach wewnętrznych znajduja się kombinację liniowe elementów ciągu wejściowego, a trzy wspomniane wcześniej krawędzie prowadzące do synów odpowiadajom trzem różnym przyrównaniom: ?>0, ?<0 oraz ?=0. (Czyli dzieliemy naszą przestrzeń poszukiwań hiperpłaszczyznami i patrzymy czy jesteśmy nad ta płaszczyzną, pod czy na niej)

Idea jest taka, że chcemy sobie stowrzyć liniowe drzewo decyzyjne i chcemy stworzyć dużo instancji problemów rzędu n! i pokazać że odpowiedź na każde z tych problemów musi wylądować w innym liściu, czyli to drzewo ma dużo liści.

**Na wykładzie została podana definicja, która mówi:**
Niech $T_n = (V, E)$ będzie liniowym drzewem decyzyjnym dla rozważanego problemu ograniczonego do danych $R^n$. DLa kążdego wierzchołka $v \in V$ przez $S(v)$ oznaczamy zbiór tych punktów z $R^n$, które osiągają $v$.

Dodatkowo został podany fakt:
Dla każdego $v \in V$ zbiór $S(v)$ jest wielościanem wypukłym.
(to było na wykładzie)

Jak stworzyc dużo instancji tych problemów, które będą w różnych liściach.
$P_1, P_2,...$ są różnymu punktami z $R^n$.
Tworzymy instancje problemów tak że bierzemy odpowiednio liczby:
P = 1, 3, 5, ..., n-1, 2*n, -(2n+2), -(2n+4), ..., -(2n+n-1)
Mamy więcej podproblemów niż tylko P. Skupiamy się na podproblemach P i próbujemy je od siebie odróżniać. Wychodzimy po za rodzine P, bo jednak mówię, że jestem tam podproblem dla którego dopowiedź jest "tak".

DLACZEGO ODPOWIEDŹ DLA KAŻDEJ INSTANCJI TEGO PODPROBLEMU BRZMI "NIE";
- potrzebujemy przynajmniej jednej ujemnej liczby, poniewąz suma trzech liczb dodatnich napewno nie da nam zera. W takim razie weźmy najmniejszą liczbę ujemną i dwie największe liczby dodatnie (na razie nie rozważamy liczby 2*n). W takim przypadku mamy: n-1+n-3+(-(2n+2)) = 2n-4-2n-2=-6 a to nie jest zero. Liczby dodatnie sa tylko i wyłącznie mniejsze a liczby ujemne równiez maleją dlatego nie możliwe jest dobranie jakiechkolwiek parametrów tak aby zniwelowąć dziure miedzy ich sumą.
- dochodzimy do wniosku że na pewno musimy skorzystać z 2*n.
ALE w momencie dodania do liczby 2*n jakiejkolwike liczby ujemnej np. 2*n + (-(2*n+2))=2*n-2*n-2 = -2. W zbiorze liczb dodatnich, którymi dysponujemy znajdują się jedynie liczby nieparzyte. Zatem nie jesteśmy wstanie znaleźć składnika, który doprowadzi nas do wyniku 0.

A więc mamy $\frac{n}{2}!$ różnych problemów na, które odpowiedź na pewno brzmi "nie".

**Następnym krokiem jest pokazanie, że każda z tych odpowiedzi ląduję w innym liściu.** (drzewo ma tyle liści ile podproblemów)

**Zakładmy niewprost, że odpowiedzi są w tym samym liściu.**
Weźmy dowolne punkty $P_i, P_j$ takie, że różnia sie na k-tej wpółrzędnej. Załóżmy, że znajdują się one w tym samym liściu. Jeżeli tak jest, to są w tej samej hiperpłaszczyżnie, więc na linii między $P_i$ oraz $P_j$ wszystkie punkty należą do tej płaszczyzny czyli dają taką samą odpowiedź $NIE$. Zatem istnieje jakiś punkt $P$ między nimi, który na $k$-tej współrzędnej ma liczbę parzystą. Weźmy go zatem.

Ale skoro ma on liczbę parzystą na $k$-tej pozycji, to algorytm powinien zwracać dla niego "tak", bo $P(k) + 2n + -(2n + P(K)) = 0$. Wiemy, że $- (2n + P(k))$ należy do naszego zbioru danych, bo skoro ten punkt leży między $P_i$ a $P_j$, to też $1 < k < n$. Stąd sprzeczność.

A więc mamy $\frac{n}{2}!$ liści to
$3^{h_n}\geq \frac{n}{2}!$
$h_n \geq \log_3\frac{n}{2}! \geq c*n*\log_2n$

### ZAD 3 (Z)

W zadaniu drugim chcieliśmy stworzyć dużo liści rzędu n! i pokazać, że każdy podproblem spada do innego liścia.
Teraz pytanie brzmi czy dałoby się więcej tych liści.
W zadniu 3 pokażemy, że modelu liniowych drzew decyzyjnych nie da sie tego zrobić.

Każdy podporblem trakrujemy ja punkt z n wymiarowej przestrzeni.

Hiperpłaszczyzna to równanie z kombinacją liniową. Jesteśmy w stanie dokładnie powiedzieć na jakich hiperłaszczyznach leża odpowiedzi "tak". Na takich na których trzy elemetny ciągu dadzą nam w sumie 0.

Na ile więc sposób możemy wybrac takie kiperpłaszczyzny?
Na ${n \choose 3} = \frac{n!}{(n-3)!*3!} = \frac{n*(n-1)*(n-2)}{6}=\Theta(n^3)$
Na pozostałych hiperpłaszczyznach mamy odpowiedź "nie".

### ZAD 4

Chcemy scalić dwa n elementowe ciągi $A = a_1, a_2, ..., a_n$ i $B = b_1, b_2, ..., b_n$ w jeden posortowany ciąg $X$. Zakładamy, że ciągi $A$ oraz $B$ są posortowane (inaczej scalanie nie miałoby sensu).
Cała przestrzeń danych, czyli wszystkie możliwe ustawienia ciągu $X$ to ${2n}\choose{n}$, bo wybieramy $n$ z $2n$ miejsc na jeden ciąg, a pozostałe wypełniamy drugim.
Adwersarz ogranicza przestrzeń danych, tak aby zawierała $2n$ zestawów danych.

Strategia adwersarza będzie opierać się na warunku:
$a_1<b_1<a_2<b_2<a_3<b_3<a_4<b_4<...<a_n<b_n$

Zapiszmy nasz ciag jako zestaw $2n-1$ par stworzonych z sąsiadujacych ze sobą elementów, czyli takich, które możemy zamienić miejscami bez utraty poprawności strategii adwersarza.
$<(a_1, b_1), (b_1, a_2), (a_2, b_2)\dots, (a_k, b_k), (b_k, a_{k+1}), (a_{k+1}, b_{k+1})\dots,(a_n, b_n)>$

Zauważmy, że mamy $2n$ możliwych ciągów, ponieważ możemy zamienić elementy w każdej z $2n-1$ par lub nie zamienić w żadnej.

Zakładamy, że gracz nie zadaje głupich tzn. nie dających mu nowych informacji pytań. Wie, że ciągi A i B były posortowane, wiec $a_i<a_{i+1}$ i $b_i<b_{i+1}$.

Rozważmy wszytskie pytania jakie może zadać gracz i pokażmy, że każde z nich eliminuje co najwyżej jeden zestaw danych. Wówczas wykażemy, że do scalenia dwóch posortowanych podciągów potrzebne jest conajmniej 2n-1 porównań.
// i bedzie indeksem dla a, j dla b

1) $i>j+1$ adwresarz odpowie,że $b_j<a_i$. Nie zmiejsza to ilości zestawów/ciągów, bo $a_i$ i $b_j$ nie są w tej samej parze.

2) $i=j+1$ adwresarz odpowie,że $b_j<a_i$ i wyeliminuje jeden ciąg, taki w którym była zamieniana para $(a_i, b_j)$, czyli $(b_j, a_{j+1})$ np. $(b_1, a_2)$

3) $i<j$ adwresarz odpowie,że $a_i<b_j$. Nie zmiejsza to ilości zestawów/ciągów, bo $a_i$ i $b_j$ nie są w tej samej parze.

4) $i=j$ adwresarz odpowie,że $a_i<b_j$ i wyeliminuje jeden ciąg, taki w którym była zamieniana para $(a_i,b_j)$, czyli $(a_i, b_i)$

Widzimy, że każde zapytanie usunie co najwyżej jeden zestaw.

**PRZYKŁAD**
$n = 2$
$<(a_1, b_1)(b_1, a_2)(a_2, b_2)>$
Otrzymujemy z tego ciągi:
$a_1, b_1, a_2, b_2$ - nie zamieniamy żadnej pary
$b_1, a_1, a_2, b_2$ - zamieniamy pierwszą parę miejscami
$a_1, a_2, b_1, b_2$ - zamieniamy środkową parę
$a_1, b_1, b_2, a_2$ - zamieniamy ostatnią parę

### ZAD 5 (Z)
### ZAD 6

WYSTARCZY:
Rozwiązaniem zadania jest drzewo decyzyjne.
Aby wybrać element wygrywając i doprowadzić go do korzenia drzewa należy wykonać $n - 1$ porównań.
Aby wybrać drugi element największy należy wybrać go z pośród elemetnów które przegrały ze zwwycięscą (największym elementem).
Takich elementóe jest $log\ n$ (wysokość drzewka o n liściach to $log\ n$).
Aby znaleźć największe z nich należy dokońać $log\ n - 1$ porównań.

$n - 1 + \log n - 1 = n + \log n - 2$

POTRZEBA (nie da się mniejsza ilością porównań uzyskać odpowiedzi):

Wy wyniku działania powyższego algorytmu dzielimy zbiór n-elemetnowy na element największy - MAX1, element drugi największy - MAX2 i zbiór pozostałych clementów, których jest n-2.

Rozważmy problem znalezienia n-2 elementów mnieszych od drugoiego największego elemetnu MAX2.

Wiemy, że aby stwierdzić, że element jest mniejszy od MAX2 musimy go z nim porównać lub porównać go z elementem, który wiemy, że jest mniejszy niż MAX2.
Takich porównań będzie n-2.

Teraz wystarczy, że pokażemy, że aby znaleźć MAX1 wykonaliśmy $\log n$ porównań.

Wprowadźmy oznaczenie:
niech $L(x)$ oznacza liczność zbioru składającego się elementów mniejszych lub równych x (które ustaliliśmy, że takie są w trakcie trwania algorytmu)

Jeśli porównujemy dwie liczby x i y, to gdy $x \leq y$ to $L(x) \leq L(y)$ ( y jest większe, więc będzie więcej elementów mniejszych od y)

Czyli skoro $x\leq y$ to $L(y) = L`(y) + L(x)$ (kolejne "wywołania algorytmu")
Czyli z każdym porównaniem $L(y)$ może powiększyć się maksymalnie dwukrotnie (, bo gdy $x \leq y$ to $L(x) \leq L(y)$)
Czyli po k porównaniach mamy $L(y) \leq 2^k$, bo na początku mamy $L(y) = 1$ ( na poczatku wiemy tylko, że y jest mniejszy lub równy y)

$L(MAX1)= n$ bo MAX1 jest maximum zbioru
stąd:
$L(MAX1)=n \leq 2^k$ //logarytmujemy
$logn \leq k$ gdzie k to liczba porównań
$\lceil logn \rceil \leq k$, bo k to liczba całkowita

Stąd potrzebujemy $\lceil logn \rceil+n-2$ porównań.

### ZAD 7 (Z)