# AIDS Notatki

Listy:
https://hackmd.io/@i1kZv8GjTaWvK0CT68ow8Q/ryochpOwn
Zadania z egzaminów:
https://hackmd.io/xBsisetSSHePCV2bIV4fNA

## Losowe rzeczy
### O, $\Omega$ i $\Theta$

### Klasa $\mathcal{NP}$ - da się sprawdzić w wielomianowym

Problemy $\mathcal{NP}-$trudne to takie, dla których *najprawdopodobniej* nie istnieją algorytmy wielomianowe.
::: spoiler definicja
:::
#### $\mathcal{NP}-$zupełność

#### Złożoność pseudowielomianowa

Zależy nie tylko od rozmiaru danych wejściowych, ale również od pewnego parametru charakterystycznego dla danego problemu (np rozmiar plecaka).

## Sortowanie
### Tylko porównania
**insert sort** - w $i$−tej iteracji element $T [i]$ wstawiamy w odpowiednie miejsce do uporządkowanego ciągu $T [1], . . . , T [i − 1]$.
**select sort** - $i − 1$-szej iteracji elementy $T [1], . . . , T [i − 1]$ są gotowe, spośród $T [i], . . . , T [n]$ wybieramy minimum i
wstawiamy je na pozycji $T[i]$.

**heapsort**
::: spoiler przyspieszenie heapsorta
:::

**mergesort**

**quicksort**

Koszt partition: $\Theta(r-p)$.

Na pivota wybiera się losowy element tablicy, medianę z trzech losowych, wybrany element (np. pierwszy) lub medianę z trzech wybranych (pierwszy, środkowy, ostatni).

::: spoiler Oczekiwany koszt
Załóżmy, że pivota wybieramy losowo. Niech $n = r-p+1$ oznacza liczbę elementów w $A[p...r]$. Każdy element ma swoją rangę: liczbę elementów, od których jest większy lub równy.
Inny sposób:
Jeszcze inny sposób:
Wierzchołki w drzewie rekursji dzielimy na chmurki i słoneczka, chmurki dzielą tablicę ojca na cześć większą niż 0.75, a słoneczka to pozostałe wierzchołki. Żaden wierzchołek nie może mieć dwóch chmurzastych synów i oczekiwana liczba chmurek z rzędu jest ograniczona przez 1. Przypiszmy chmurki słoneczkom, od których te chmurki odchodzą, zastąpimy je pojedynczymi krawędziami. Teraz wysokość drzewa jest $O(log(n))$ i każdy wierzchołek wykonuje liniową pracę.
:::
::: spoiler Usprawnienia
- Trójpodział: gdy klucze mogą się wielokrotnie powtarzać warto dzielić na trzy części: mniejsze, równe i większe i wywoływać się dalej tylko na mniejszych i większych.
- Eliminacja rekursji,
- Zapisanie wewnętrznej pętli w języku procesora,
- W miejscu.
:::

### Nie tylko porównania
**Counting Sort** - zakładamy, że dane to liczby całkowite z przedziału $[1, k]$.
Koszt: $\Theta(n+k)$

**Bucket Sort** - n liczb rzeczywistych z [0, 1] o rozkładzie jednostajnym.
Dzielimy przedział [0, 1] na n kubełków długości $\frac{1}{n}$, wrzucamy do nich liczby, sortujemy wewnątrz kubełków i łączymy.
.

Koszt: $\Theta(n)$
:::spoiler Uzasadnienie
:::

**Radix Sort** - dane: $A_1, ..., A_n$ - ciągi elementów z $\Sigma = {0, 1, ..., k-1}$ o długości $d$.
::: spoiler Na ciągach obowiązuje porządek leksykograficzny.
:::
(counting sort to ta stabilna metoda generalnie).
Koszt $O((n+k)d)$.

*Ciągi niejednakowej długości.*
Koszt liniowy wględem liczby wszystkich literek i k.
::: spoiler uzasadnienie

:::

Zastosowanie: **Izomorfizm drzew**
Będziemy to robić warstwami dla obu drzew naraz - pierwsza warstwa to wierzchołki odległe od korzenia o h - wysokość drzewa, druga - o h - 1 itd.
- Zaczynamy od warstwy 1. Każdy wierzchołek jest liściem i dostaje etykietę 1. Sprawdzamy, czy w obu drzewach jest ich tyle samo.
- Przchodzimy do wyższej warstwy, dla każdego wierzchołka z tej warstwy tworzymy listę, na którą wrzucamy etykiety jego dzieci w kolejności rosnącej (posortowaliśmy je w poprzedniej fazie). Nadajemy etykiety wierzchołkom z nowej warstwy tak, żeby wierzchołki o takich samych listach miały takie same etykiety a o różnych różne (radix sort). Sprawdzamy, czy nowe listy etykiet są takie same.

Jeśli doszliśmy do korzenia to sukces, wpp. smuteczek.


## Kopce

Kopiec - Drzewo binarne T o wysokości h, którego wierzchołki zawierają klucze z liniowo uporządkowanego zbioru, spełniające warunki:
- wszystkie jego liście znajdują się na głębokości d lub d-1,
- wszystkie liście z poziomu d-1 leżą na prawo od wszystkich wierzchołków wewnętrznych z tego poziomu,
- położony najbardziej na prawo wierzchołek wewnętrzny z poziomu d-1 jest jedynym wierzchołkiem wewnętrznym w T, który mkoże mieć jednego syna,
- klucz w każdym wierzchołu wewnętrznym jest nie mniejszy od kluczy w jego potomkach.


Kopce pamiętamy w tablicy:
wierzchołki z poziomu k-tego pamiętany są kolejno od lewej do prawej w $K[2^k], K[2^k+1], ..., K[2^{k+1}-1]$. Wierzchołek w $K[i]$ ma ojca w $K[{i / 2}]$ i dzieci w $K[2i]$ i $K[2i+1]$ (o ile istnieją).

### Procedury przywracające własności kopca

Zmiana klucza w wierzchołku kopca może zaburzyć uporządkowanie (jeśli nowy klucz jest większy od klucza ojca to je zamieniamy i tak rekurencyjnie, jeśli nowy klucz jest mniejszy od któregoś dziecka to zamieniamy go z większym i tak rekurencyjnie).

### Buduj kopiec

Startujemy od kopców 1-elementowych, następnie używamy tych kopców oraz nowych elementów do utworzenia kopców 3-elementowych: nowy element umieszczamy w korzeniu takiego kopca, a jego synami czynimy korzenie kopców 1-elementowych, następnie sprawdzamy, czy nowy korzeń jest mniejszy od któregoś dziecka, jeśli tak to zamieniamy go z większym i tak dalej. Analogicznie z dwóch kopców $(2^k-1)$-elementowych i jednego nowego elementu budujemy kopiec $(2^{k+1}-1)$-elementowy.


tworzy kopiec w czasie $O(n)$

### Podwójna kolejka priorytetowa

Podwójna kolejka priorytetowa umożliwia znajdowanie i usuwanie zarówno maks i min.



Na naturalnie zdefiniowanych ścieżkach z korzenia H do L klucze są uporządkowane nierosnąco.
::: spoiler procedury
:::

## Algorytmy zachłanne

Mamy skończony zbiór C, rozważamy elementy po kolei i akceptujemy je albo odrzucamy.

### Konstrukcja MST
::: spoiler treść zadania
:::
#### Strategia Kruskala

Rozpoczynam od pustego E'. Zbiór C = E. W kolejnych krokach rozpatrujemy krawędź z C o minimalnej wadze. Dodajemy ją do E', jeśli nie powoduje to powstania cyklu.

::: spoiler Dowód
:::

#### Strategia Prima

Inicjujemy E' wstawiając do niego minimalną krawędź spośród incydentnych z arbitralnie wybranym wierzchołkiem v. C = E. W kolejnych krokach rozpatrujemy minimalną krawędź z C incydentną z jakąś krawędzią z E', o ile nie powstanie cykl.
:::spoiler Dowód
:::
#### Strategia Boruvki

- Dla każdego wierzchołka z G znajdujemy najkrótszą incydentną z nim krawędź, dołączamy ją do zbioru E'.
- Tworzymy graf G', w którym wierzchołki są spójnymi składowymi z (G, E').
- Za G przyjmujemy G' i powtarzamy dopóki nie otrzymamy jednej spójnej składowej.

:::spoiler Dowód
:::

### Szeregowanie zadań

::: spoiler jeden procesor bez terminów
:::

::: spoiler jeden procesor z terminami
:::

### Pokrycie zbioru
::: spoiler treść zadania
:::
Algorytm aproksymacyjny:
dla każdego podzbioru $S_i$ określamy cenę za pokrywany element:
$$ cne(S_i)=\frac{c(S_i)}{|S_i/C|}$$
gdzie C jest zbiorem dotychczas pokrytych elementów. Wybieramy podzbiór z minimalnym cne.

Algorytm aproksymacyjny znajduje rozwiązanie o koszcie $O(log (n) \cdot OPT)$

Dla każdego elementu $e_i$
$$cena(e_i) \le \frac{OPT}{n-i+1}$$

## Dziel i zwyciężaj
- podziel dane na mniejsze części,
- rozwiąż dla podproblemów,
- połącz rozwiązania w jedno duże.


### Mnożenie bardzo dużych liczb a, b

$n = 2^k$ - długość a i b
$s = n/2$
$$a = a_1 \cdot 2^s + a_0$$ $$b = b_1 \cdot 2^s + b_0$$ $$0 \le a_1, a_0, b_0, b_1 < 2^s$$ $$c_2=a_1b_1,$$ $$c_1=a_0b_1+a_1b_0,$$ $$c_0=a_0b_0$$ $$ab=c_2\cdot2^{2s}+c_1\cdot2^s+c_0$$
$$c_1=(a_1+a_0)(b_1+b_0)-c_0-c_2$$

Złożoność czasowa $O(n^{log (3)})$
:::spoiler podział na więcej częsci
:::

### Równoczesne znajdowanie minimum i maksimum w zbiorze

$\left\lceil\dfrac{3n}{2}-2\right\rceil$porównań
::: spoiler dowód
:::

### Sieci przełączników


:::spoiler Kryteria jakości
- liczba przełączników
- głębokość sieci (#przełączników na najdłuższej ścieżce we-wy)
:::

#### Dowód

Niech $\pi$ będzie dowolna permutacją n-elementową. Pokażemy, że istnieje ustawienie przełączników realizujące tą permutację, tj. dane z $i$-tego portu sieci zostaną przesłane na $\pi(i)$-ty port wyjściowy. Istnienie takiego ustawienia jest konsekwencją istnienia dwukolorowania wierzchołków na zmodyfikowanym grafie G:
- wierzchołki:
- n wierzchołków odpowiadających portom wejśćiowym,
- n wierzchołków odpowiadających portom wyjśćiowym,
- n wierzchołków przejściowych dodanych ze względów technicznych na krawędziach między portami wejściowymi i wyjściowymi.
- krawędzie:
- łączymy w pary porty wejściowe, tak jak wchodzą do przełączników,
- łączymy w pary porty wyjściowe, tak jak wychodzą z przełączników,
- łączymy port wejściowy i z portem wyjściowym $\pi(i)$ (dla każdego i).

Nasz graf jest sumą rozłącznych cykli parzystej długości, bo stopień każdego wierzchołka to 2 (więc rozłączne cykle) i każdy cykl składa się z parzystej liczby wierzchołków wejściowych, wyjściowych i przejściowych.

A więc istnieje kolorowanie białym i czarnym takie, że:
- porty wchodzące do tego samego przełącznika dostają różne kolory,
- port wejściowy $i$ i port wyjściowy $\pi(i)$ mają ten sam kolor.

Ustawienie przełączników:
- wejściowe: białe wierzchołki idą do górnej podsieci,
- Górną i dolną podsieć ustawiamy tak, żeby permutowały zgodnie z $\pi$ (każda ma n/2 drutów więc sobie poradzi),
- wyjściowe: ustawiamy tak, żeby drut z wcześniejszą wartością w $\pi$ poszedł do góry.

### Para najbliżej położonych punktów

Dzielimy zbiór pionową prostą na połowy, dla każdej znajdujemy parę kandytatów, wybieramy lepszą (i, j) o odległości d i sprawdzamy czy jakas para (t, s) z przeciwnych stron prostej jest lepsza.

$P_c$ - punkty odległe o $\le d$ od prostej
odległość$(t, s) \le d => (t, s) \in P_c$
W $P_c$ jest nie więcej niż 6 punktów (x,y) (różnych od $t, s$) takich, że $y_t$ $\le y \le y_S$ (lub odwrotnie).

## Programowanie dynamiczne
Polega na obliczaniu rozwiązań dla wszystkich podproblemów.

### Znajdowanie ${n \choose k}$

:::spoiler Klasyczny dynamik
Szukamy największej sumy pól ($a_{i,j}$ - zysk z pola).
Rozwiązanie :
Odtworzenie drogi :
:::

### LCS
Prosta obserwacja do szukania $LCS(X, Y)$ :


Rozwiązanie :

Koszt to $\Theta(n \cdot m)$. Skonstuowanie LCS na podstawie $d$ jest liniowy.

### Optymalna kolejność mnożenia macierzy


Założenie: Koszt pomnożenia macierzy o wymiarach $a × b$ i $b × c$ wynosi $abc$.
Rozwiązanie:

Koszt: liczymy kolejne przekątne zaczynając od głównej. Koszt policzenia elementu na s-tej przekątnej wynosi $\Theta(s)$, a takich elementów jest $n-s$.

$$T(n) = \sum^{n-1}_{s=0} \Theta (s) \cdot (n-s)= \Theta(n^3)$$

Odtwarzanie w $\Theta(n^2)$ bez pamiętania żadnych dodatkowych rzeczy.

### Problem plecakowy
Wkładamy do plecaka o ograniczonej pojemności przedmioty z sumarycznie maksymalną wartością.
$K(w)$ = maksymalna wartość plecaka o pojemności $w$.
$O(nW)$

$K(w, j)$ = maksymalna wartość plecaka o pojemności $w$ i przedmiotów ${1, 2, ..., j}$ (pozostałych do wzięcia).
$O(nW)$

### Przynależność do języka bezkontekstowego

::: spoiler gramatyki
:::

Gramatyka jest ustalona i nie jest argumentem.

Każde $w = w_1, ..., w_n$ słowo długości większej niż jeden powstało z pierwszej produkcji S->AB. Dalsze wyprowadzenia A i B są niezależne, więc istnieje takie $k$, że $w = a_1, a_2, ..., a_k, b_{k+1}, ..., b_{n}$.

Algorytm polega na obliczeniu dla każdego podsłowa w (od jednoliterowych do całego słowa) zbioru nieterminali, z których da się to podsłowo wyprowadzić.
$\Theta(n^3)$
::: spoiler szczegóły
:::

### Drzewa rozpinające drabin

Ile jest drzew rozpinających drabiny $D_n$?

Sposoby na stworzenie drzew $D_{i}$ z drzew lub lasu $D_{i-1}$ ($S_i$):

Sposoby na stworzenie lasu ($N_i$):


Drabiny mają teraz wyróżnione krawędzie. Szukamy drzewa rozpinającego o k krawędziach wyróznionych.

Możemy uogólnić powyższą metodę. $S_i(j)$ to ile jest drzew na drabinie i-elementowej z j wyróżnionymi krawędziami, analogicznie $N_i(j)$. Do policzenia $S_{i+1}(j)$ $(j = 0, ..., k)$potrzebujemy wszystkich $S_i(l)$ i $N_i(l)$, $(l = 0, ..., k)$ czyli 2k zbiorów.

## Dolne granice

**Drzewo decyzyjne** to skończone drzewo binarne, w których każdy wierzchołek reprezentuje jakieś porównanie, każdy liść wynik, a krawędzie odpowiadają obliczeniom między porównaniami. Przyjmujemy ograniczone modele obliczeń (można tylko porównywać).

**Liniowe drzewa decyzyjne** to drzewa trynarne, w których w wierzchołkach możemy porównywać kombinacje liniowe elementów wejściowych do 0, więc mamy trzy krawędzie (<0, =0, >0).
Zauważmy, że dla drzew decyzyjnych możemy przenumerować dane.

::: spoiler sortowanie
:::

### Różność elementów

Dostajemy punkt w n wymiarach i sprawdzamy, czy ma parami różne współrzędne.
Pokażemy, że istnieją rozłączne podzbiory takie, że każdy wpada do innego liścia i tych liści jest dużo, więc wysokść drzewa jest duża.

S(v) - zbiór punktów, które osiągają v.

S(korzeń) zawiera całe $\mathbb{R}^n$, operacja f(X) etykietująca wierzchołek v rozbija S(v) na trzy rozłączne podzbiory. Dla każdego v S(v) jest wielościanem wypukłym i f jest ciągła.

Niech $P_1, ... P_{n!}$ będą kolejnymi permutacjami zbioru {1, 2, ..., n} (punktami w $\mathbb{R}^n$). Odpowiedź dla wszytkich to YAS. Pokażemy, że każdy punkt dojeżdża do innego liścia.

NIE WPROST

Załóżmy, ze $P_i$ i $P_j$ wpadły do tego samego liścia. Niech k będzie najmniejszą liczbą, która występuje na innych pozycjach w $P_i$ i $P_j$ ($k_i$ i $k_j$) załóżmy bso, $k_i<k_j$. Niech $f(X) = x_{k_i}-x_{k_j}$ , $f(P_i) < 0$ i $f(P_j) > 0$. f jest ciągła, a S(v) wypukły, więc jest takie $P$, że $f(P) = 0$ i jest w liściu który mówi YAS -> sprzeczność.
Liści jest przynajmniej n!, więc wysokość jest $\Omega(nlog(n)$

### Równoczesne znajdowanie min i max

Każdy algorytm wykonuje co najmniej $\lfloor \frac{3}{2} n - 2 \rfloor$ porównań.

Udowodnimy to bawiąc się ze złośliwym adersarzem, który twierdzi, że zna zbiór, który zmusi algorytm do wykonania co najmniej $\lfloor \frac{3}{2} n - 2 \rfloor$ porównań. (Będzie wymyślał ten zbiór na bieżąco trzymając na karteczce zbiory wygrywów, nieznanych, śmietnika i frajerów, a na koniec pożre kartkę, żeby nie było dowodów).

Adwersarz będzie mówił, że element z bardziej lewego zbioru jest większy.

Elementy muszą przechodzić z nieznaych do wygrywów/frajerów, a dopiero potem mogą iść do śmietnika i:
- Jedno porównanie może usunąć co najwyżej dwa elementy z nieznanych,
- dodanie jednego elementu do śmietnika kosztuje jedno porównanie,
- porównania, w których bierze udział nieznane nie zwiększają mocy śmietnika.

Na opróżnienie nieznanych wydamy $\lceil \frac{n}{2}\rceil$ porównań, następne $n-2$ pójdą na wypełnienie śmietnika.

## Wybór k-tego elementu

Dla $k = 1$ wystarczy $n-1$ porównań, dla $k = 2$ wystarczy $n-2+\lceil log(n) \rceil$.

:::spoiler uzasadnienie
:::

### Algorytm deterministyczny

Dziel i Zwyciężaj: Wybieramy pivota p i rozdzielamy T na dwa podzbiory U i V (mniejsze i większe od p). Porównanie k z mocą z U pozwala określić czy w U czy V szukać dalej.
Musimy sensownie wybrać pivota: dzielimy T na $5$-cioelementowe grupy i w każdej wybieramy medianę i rekurencyjnie szukamy mediany median.

Koszt: $O(n)$

:::spoiler Uzasadnienie
Lemat: U i V mają nie mniej niż $\frac{3}{10}n-4$ elementy.

Niech T to koszt piątek:
$$T(n) \le T(\lceil \frac{n}{5} \rceil) + T( \frac{7n}{10}+4 ) + O(n)$$
:::

### Algorytmy zrandomizowane

#### Algorytm Hoare'a
Wybieramy pivota losowo. (Quicksort tylko dalej sprawdzamy tylko jedną z podtablic).

#### LazySelect

Wybieramy losowo próbkę R (rozmiaru, który można liniowo posortować względem n). Znajdujemy w R elementy L i H, takie że z dużym prawdopodobieństwem $k$-ty element znajduje się w niewielkim zbiorze P elementów większych od L i mniejszych od H.

Koszt: $O(n)$

::: spoiler Uzasadnienie
Z prawdopodobieństwem $1 - O(\frac{1}{\sqrt[\leftroot{-2}\uproot{2}4]{n}})$ potrzeba tylko jednej iteracji.
Szkic dowodu:
- Wartość oczekiwana liczby elementów w R nie większych od szukanego = $kn^{-\frac{1}{4}}$,
- wariancja $< \sqrt{n}$,
- nierówność Czebyszewa:
:::

## Drzewa AVL

Chcemy mieć słownik: strukturę umożliwiającą szybkie wstawianie, usuwanie i wyszukiwanie kluczy.
Nasze drzewa są BST i dla każdego wierzchołka różnica wysokości prawego i lewego poddrzewa jest nie większa niż 1.

Liczba wierzchołków w dowolnym drzewie binarnym jest o 1 mniejsza od $\rho(h)$ - liczby pustych wskaźników.

Wysokość drzewa AVL o n wierzchołkach jest mniejsza niż $1.4405 \cdot log(n+2)$.

Dowód:
Indukcyjnie pokazujemy, że $\rho(h) = F(h+2)$ (liczba Fibonacciego): Niech $T$ będzie minimalnym drzewem AVL o wysokości $h$, jedno jego poddrzewo to minimalne drzwo wysokości $h-1$ a drugie $h-2$.

AVL wykorzystuje się do implementacji list. Aby poznać pozycję elementu na liście wystarczy pamiętać, w każdym wierzchołku, ile elementów ma w poddrzewie.

**Operacje**
Koszt: $O(log(n))$

### Rotacje

### Wstawianie
Zwykłe wstawianie do BST. Wracając rekurencją znajdź pierwszy niezbalansowany wierzchołek z, y to jego dziecko, a x wnuczek (napotkane na tej rekurencyjnej drodze).
*najwyżej dwie rotacje*.

### Usuwanie
- Znajdujemy frajera do odstrzelenia,
- Jeśli miał frajerątka, to wstawiamy na jego miejsce następnika (najmniejszy element z prawego poddrzewa frajera).
- Sprawdź, czy następnik był liściem:
- Jeśli nie, wstaw na jego miejsce jego jedyne dziecko (jest ono liściem i możemy go usunąć).
- Jeśli tak, to po prostu usuń.
- Przejdź drogę od tego liścia do korzenia przywracając przywracając zrównoważenie przy pomocy rotacji.

*potencjalnie rotacje dla wszystkich wierzchołków na drodze*.

### Inne
- Rozdzielanie,
- Konkatenacja.

## B-Drzewa

- wszystkie liście leżą na tej samej wysokości,
- każdy węzęł zawiera wiele elementów (są uporządkowane),
- nowe elementy zapamietywane są w liściach,
- drzewo rośnie od liści do korzenia: jeśli jakiś węzeł jest pełny, to tworzymy mu brata, który mu zabiera połowę elementów, środkowy z nich wędruje ze wskaźnikiem na bracika do ojca. Jeśli w ten sposób podzielony zostanie korzeń, to tworzony jest nowy korzeń. Jest to jedyny moment kiedy rośnie wysokość.

:::spoiler Formalnie
:::

Służą do pamiętania dużych słowników, które muszą być pamiętane na dysku.

**Operacje**

### Przeszukiwanie

Podobnie jak w BST, ale dokonujemy wyboru między wieloma synami (dla duzych n(x) przeszukiwanie binarne).


### Tworzenie pustego drzewa


### Rozdzielanie węzła
y - pełny wierzchołek (2t-1 kluczy),
x - y jest i-tym dzieckiem x, zakładamy, że x jest niepełny.

### Wstawianie
Sprawdzamy, czy T nie ma pełnego korzenia, jeśli tak to tworzymy nowy i stary rozdzielamy.

Przechodzi ścieżkę od korzenia do liścia rozdzielając wszystkie pełne wierzchołki, przez które przechodzi.


### Koszt

## Drzewa Czerwono-Czarne
- Każdy wierzchołek ma kolor,
- Każdy liść (NULL) jest czarny,
- Jeśli wierzchołek jest czerwony, to obaj jego synowie są czarni,
- na każdej ścieżce z danego wierzchołka do liścia (bez tego wierzchołka) jest taka sama liczba czarnych wierzchołków (czarna wysokość bh(x)).

Czerwono-Czarne drzewo o n wierzchołkach wewnętrznych ma wysokość nie większą niż $2log(n+1)$.
(Dowód przez indukcję po zwykłej wysokości, pokazujemy, że drzewo zakorzenione w x zawiera co najmniej $2^{bh(x)} - 1$ wierzchołków wewnętrzynch).

**Operacje**

Koszt: $O(log(n))$

### Wstawianie

Jak w BST, nadajemy nowemu wierzchołkowi x kolor czerwony i upewniamy się, że każdy czerwony wierzchołek ma dwóch czarnych synów: wędrujemy od x w górę, stosując zmianę kolorów i rotacji, by przenieść zaburzenie do przodków x-a. Wykonamy rotację najwyżej dwa razy.

:::spoiler
:::

### Usuwanie
Jak w BST, jeśli usuwany wierzchołek y był czarny, to jego ojciec mógł stracić jedno ze swoich czarniątek, i liczba czarniątek na ścieżce może się teraz nie zgadzać.

Czarność y-a przesuniemy na jego syna (syn musiał być jedynakiem i został podczepiony pod ojca y-a albo jest liściem). Teraz zostało zadbać o potencjalnie nadmiarową czarność syna.

[](https://imgur.com/37hFHAG.png)
::: spoiler
:::

## Kopce Dwumianowe

### Drzewa Dwumianowe

Oprócz wstawiania, tworzenia, znajdowania i usuwania minimum mamy też łączenie.

Drzewo $B_i$ zawiera $2^i$ wierzchołków. Rzędem wierzchołka jest liczba jego dzieci, rzędem drzewa jest rząd korzenia.

#### Łączenie (join)

Dwa drzewa $B_i$ łączymy podłączając mniejszy korzeń pod większy jako dziecko (otrzymujemy $B_{i+1}$).


### Kopce Dwumianowe

Trzymamy wskaźnik na minimum.

**Operacje w wersji gorliwej**

W tej wersji kopiec to tablica wskaźników na poddrzewa. W $i$-tej komórce jest wskaźnik na dziecko $i$-tego rzędu (każdy kopiec zawiera co najwyżej jedno dziecko danego rzędu).

#### Gorliwe Łączenie (meld)

Procedura Meld(h, h') usuwa stare wskaźniki i tworzy nowy: H.

Koszt: $O(log(n))$, bo kopiec zawierający n elementów składa się z najwyżej log(n) różnych drzew dwumianowych.

#### Usuń minimum (deletemin(h))

Usuwamy minimum z drzewa, na które wskazuje MIN, z jego dzieci tworzymy nowy kopiec h' i łączymy (meld(h, h')).
Koszt: $O(log(n))$

#### Wstawianie

złącz(kopiec, zrób kopiec(wstawiany element))
Koszt logarytmiczny, ale zamortyzowany stały.

**Operacje w wersji leniwej**

Kopiec to zbiór drzew dwumianowych, zorganizowanych w cykliczną listę dwukierunkową.

#### Łączenie (lazymeld(h, h'))

Łączymy listy i aktualizujemy MIN.

#### Usuwanie minimum (deletemin(h))

Usuwamy minimum z drzewa, na które wskazuje MIN, dołączamy jego poddrzewa do kopca, uaktualniamy MIN i sprzątamy (jak w wersji eager), żeby mieć najwyżej jedno drzewo dla każdego rzędu.

Koszt O(n), ale zamortyzowany O(log (n)).

:::spoiler uzasadnienie
:::

## Kopce Fibonacciego

Chcemy szybko zmieniejszać wartość w danym wierzchołku.
Podobnie jak leniwe kopce dwumianowe, kopce Fibonacciego są zbiorami drzew z porządkiem kopcowym i pamiętamy je jako listę cykliczną dwukierunkową. Dodatkowo w każdym wewnętrznym wierzchołku pamietamy wartość logiczną żałobnik, mówiącą czy wierchołek stracił jednego ze swoich synów (w wyniku cut).

**Operacje**

### Odetnij (cut(h, p))

Czy p jest korzeniem?
- Tak:
- Nie: Odetnij go od ojca p' i dołącz do listy korzenia (meld p, h). Czy p jest pierwszym synem, którego stracił p'?
- Tak: p.żałobnik = true.
- Nie: cut(h, p') i rekurencyjnie w górę.

### Zmniejsz (decrement(h, p, $\Delta$))

Zmniejsz, jeśli nowa wartość zakłóca porządek kopcowy to odetnij (cut(h, p)) i zaktualizuj MIN.

**Zamortyzowany koszt:** $O(1)$
Korzeń każdego drzewa ma jedną jednostkę. Każdy wierchołek wewnętrzny ma konto, żałobnicy będą coś na nim mieli.
Operacja zmniejsz dostaje 4 jednostki.
- Jedną jednostką płacimy za operacje niskiego poziomu i meld.
- Drugą umieszczamy na koncie odcinanego drzewa.
- Dwie pozostałe dajemy ojcu p jeśli został żałobnikiem, żeby miał jak straci drugie dziecko.

### Usuń minimum (deletemin(h))

Analogicznie do dwumianowych, z tym, że jak łączymy drzewa tego samego rzędu to one mogą nie byc identyczne.

Koszt zamortyzowany: O(log(n)).

Lemat: Dla każdego wierzchołka o rzędzie k, drzewo zakorzenione w x ma rozmiar wykładniczy względem k.
Dowód: Niech $x$ będzie dowolnym wierzchołkiem kopca i niech $y_1, ..., y_k$ będą jego synami uporządkowanymi w kolejności przyłączania. W momencie przyłaczania $y_i$ do $x$-a x miał co najmniej $i-1$ synów (mógł mieć więcej i oni mogli zostgac odcieci). Stąd $y_i$ też miał co najmniej $i-1$ synów, ponieważ przyłączamy kopce tego samego rzędu. Od tego momentu mógł stracić najwyżej jednego syna (bo w p. p. zostałby odcięty). W każdym momencie $i$-ty syn każdego wierzchołka ma rząd co najmniej $i-2$.

Oznaczamy przez $F_i$ najmniejsze drzewo o rzędzie i, spełniające powyższą zależność.
Indukcyjnie:
$F_i$ składa się z korzenia i poddrzew $F_0, F_0, F_1, F_2, ..., F_{i-2}$. Liczba wierzchołków $F_i$ ($|F_i|$) jest nie mniejsza niż $1+ \sum^{i-2}_{j=0} |F_j|$, czyli i-tej liczbie Fibonacciego. Liczba wierzchołków jest nie mniejsza niż $\phi^k$.

Stopień wierzchołków drzew w kopcu Fibonacciego jest ograniczony przez O(log (n)).

### Usuń (delete(h, p))

decrement(h, p, $-\infty$)
deletemin(h)

Koszt zamortyzowany: O(log(n)).

## Drzewa Samoorganizujące się

BST, w którym będziemy rotować dany wierzchołek do korzenia, spłaszczając drzewo.

**operacje**

### Przeorganizuj (Splay(j, S))

Czy j należy do drzewa?
- Tak: przerotuj je do korzenia,
- Nie: przerotuj k takie, że $k = min\{x \in S | x > j\}$ lub $k = max\{x \in S | x < j\}$ do korzenia.

#### Implementacja:

3 przypadki:
- x ma ojca, ale nie ma dziadka $\rightarrow$ rotate(x),
- x ma ojca p(x) i ma dziadka:
- x i p(x) obydwaj są lewymi lub prawymi synami swoich ojców $\rightarrow$ rotate(p(x)); rotate(x),
- w p. p. $\rightarrow$ rotate(x); rotate(x).


#### Analiza zamorytzowana


Będziemy utrzymywać:
*Wierzchołek x ma zawsze co najmniej $\mu(x)$ jednostek na swoim koncie.*

Insert daje wierzchołkowi początkowy depozyt.

Operacja Splay dostaje $3(\mu(S)-\mu(x))+1$ jednostek.
BZO x jest lewym synem swojego ojca.
Rozważmy przypadki:
- x nie ma dziadka, niech y to jego ojciec.
Niech $\mu$ to konta przed, a $\mu'$ po rotacji.
Musimy zapłacić:
$$\mu'(x)+\mu'(y)-\mu(x)-\mu(y)$$
A wiemy, że $\mu'(x)=\mu(y), \mu'(x) \ge \mu(x)$ oraz $\mu'(y) \le \mu'(x)$.
Tak więc:
$$\mu'(x)+\mu'(y)-\mu(x)-\mu(y) = \mu'(y)-\mu(x) \le \mu'(x)-\mu(x) \le 3(\mu'(x)-\mu(x))$$

Jedną jednostką płacimy za operacje niskiego rzędu.

- niech y to ojciec a dziadek to z.

Musimy zapłacić:
$$(*) = \mu'(x)+\mu'(y)+\mu'(z)-\mu(x)-\mu(y)-\mu(z)$$

Wiemy, że: $\mu(z) = \mu'(x)$.

$$(*) = \mu'(y)+\mu'(z)-\mu(x)-\mu(y) = [\mu'(y)-\mu(x)]+[\mu'(z)-\mu(y)] \le$$

$$\le [\mu'(x)-\mu(x)]+[\mu'(x)-\mu(y)] \le 2[\mu'(x)-\mu(x)]$$

Na operacje niskiego rzędu zostaje nam $\mu'(x)-\mu(x)+1$ jednostek.

Lemat: Jeśli $\mu'(x)=\mu(x)$, to $\mu'(x)+\mu'(y)+\mu'(z)-\mu(x)-\mu(y)-\mu(z)<0$

Dowód nie wprost:
$\mu'(x)=\mu(x)$ i $\mu'(x)+\mu'(y)+\mu'(z) \ge \mu(x)+\mu(y)+\mu(z)$
Wiemy $\mu(x)\le \mu(y)\le\mu(z)=\mu'(x)=\mu(x)$
$$\mu(x) = \mu(y)= \mu(z)$$
Stąd $$\mu'(x)+\mu'(y)+\mu'(z) \ge 3\mu(z)$$
$\mu'(y)$ i $\mu(z)$ są nieujemne i nie większe od $\mu(z)$.

$$\mu'(x)=\mu'(y)=\mu'(z) = \mu(x)=\mu(y)=\mu(z)$$

Zauważmy, że zbiór wierzchołków przed rotacjami w pod x to zbiór rozłączny z po pod z. Moce tych zbiorów to a i b. Wszystkie te wierzchołki plus y znajdowały się pod z.
$$\lfloor log(a)\rfloor=\lfloor log(a+b+1)\rfloor = \lfloor log(b)\rfloor$$
Ale $\lfloor log(a+b+1)\rfloor\ge \lfloor log(2min\{a,b\})\rfloor > \lfloor log(min\{a,b\})\rfloor$. Sprzeczność.
- w p.p. analogicznie.

Niech $S_1, S_2, ..., S_k$ będzie drzewem zakorzenionym w x w momencie kiedy x zajmuje tą pozycję. Całkowity koszt Splay(x, S):
$$3(\mu(S_1) - \mu(x)) + 3(\mu(S_2)-\mu(S_1))+ ... + 3(\mu(S_k)-\mu(S_{k-1})) + 1 = \\ 3(\mu(S_k)-\mu(x)) + 1=3(\mu(S)-\mu(x)) + 1 $$

## Drzepiec

BST, w którym każdy wierzchołek ma losowo wybrany priorytet. Na kluczach obowiązuje porządek BST, a na priorytetach kopcowy.
Drzewa zbalansowane są bardzo prawdopodobne (robimy quicksorta tak naprawdę), dlatego drzepce działają szybko.

### Merge($T_1, T_2$)

Łączymy drzewce takie że wszystkie klucze z $T_1$ są mniejsze od kluczy z $T_2$.
Wybieramy korzeń o wyższym priorytecie i wsadzamy na korzeń wyniku, jedno poddrzewo mu zostaje drugie rekurencyjnie mergujemy z drugim drzepcem.

### Split($T, k$)

Dzielimy drzewo na trzy drzepce, których klucze są mniejsze, równe i większe od k.

- jeżeli $T.val = k$:
- usuń wskaźniki korzenia,
- return ($T.l, T, T.r$).
- jeżeli $T.val < k$:
- $T' = split(T.r, k)$,
- return ($T-T.r \cup T'[0], T'[1], T'[2]$)
- jeżeli $T.val > k$ analogicznie.

Do innych operacji używamy tych funkcji, tj. delete to split i merge poddrzew, insert to merge merge.

:::spoiler wersja z wikipedii i lorysia
Proste operacje:
- Wyszukiwanie jak w BST.
- Wstawianie jak normalnie i tak długo jak nowy wierzchołek ma większy priorytet niż rodzic wykonujemy rotacje.
- Usuwanie x:
- jeśli liść po prostu usuń,
- jeśli jedno dziecko to wstaw je na miejsce x,
- jeśli dwoje dzieci to wybierz dziecko o wyższym priorytecie i zrób rotację z x. Powtarzaj, aż nie dojdziesz do któregoś z powyższych przypadków.

Masowe operacje:
- Split(x) - rozbij drzepca na dwa, z kluczami mniejszymi i większymi od x. Wstaw x z najwyższym priorytecie w drzewie i odetnij mu dzieci.
- Join(T1, T2) - złącz drzepce T1 i T2, takie że wszystkie klucze T1 są mniejsze od wszystkich z T2. Stwórz wierzchołek x z kluczem większym od każdego klucza w T1 i mniejszym od każdego w T2, daj mu priorytet mniejszy od wszystkich w obu drzewach. podłącz T1 i T2 do x (poddrzewa) i wykonaj właściwe rotacje, żeby przywrócić porządek kopcowy. x będzie liściem i można go łatwo usunąć.
:::
## Drzewa Przedziałowe

Pełne drzewa binarne, takie, że wszystkie elementy tablicy są kolejnymi liśćmi od pierwszego (zerowego).

### Punkt przedział

Mamy tablicę n-elementową oraz q operacji: zmiana elementu lub zapytanie o przedział (np suma, max).

Sumy prefiksowe załatwiłyby zapytania, ale modyfikacje kosztowałyby dużo.
Struktura pierwiastkowa (podzielenie tabilcy na kubełki długości pierwiastka) byłaby szybka do modyfikacji, ale zapytania byłyby drogie.

Rozwiązaniem są drzewa przedziałowe: każdy wierzchołek odpowiada za jakiś przedział (korzeń za całą tablicę, liść za samego siebie) i trzyma wynik zapytania dla tego przedziału.

Modyfikujemy idąc od liścia w górę, pytamy znajdując liście odpowiadające za końce przedziału i idąc w górę, jeśli będziemy mieć brata wewnątrz w ten sposób powstałej ścieżki to weźmiemy go do wyniku.

### Przedział punkt

Modyfikacje na przedziale, zapytania o punkt.

W wierzchołku zapamiętujemy ile ma się zmienić przedział za który odpowiada. Zapytania sumują te wartości.

### Przedział przedział

Modyfikujemy i pytamy o przedział.

Używamy leniwej propagacji: każdy wierzchołek v pamięta o ile ($\Delta(v)$) ma się zmienić przedział, za który odpowiada, i dopiero jak przychodzi zapytanie o jego przedział, to wierzchołek wylicza i zapamiętuje swoją wartość i upycha brud ($\Delta$) do wierzchołków niżej.

## Union Find

Początkowo każdy element zbioru U tworzy jednoelementowy podzbiór. Wykonujemy na nich ciąg $\sigma$ operacji:
- Union($A, B$) zwraca $A \cup B$ i usuwa $A$ i $B$.
- Find($i$) zwraca reprezenanta zbioru, do którego należy $i$.

Rozwiązujemy w trybie online - wynik każdej operacji musi być gotowy przed wczytaniem następnej.

### Proste rozwiązanie

- Użyjemy tablicy, która dla każdego wierzchołka przechowuje reprezentanta zbioru, do którego należy.
- Union przyłącza mniejszy zbiór do większego.
- Find podczepia pod korzeń wszystkie wierzchołki, które napotkał po drodze. (kompresja ścieżki)

### Analiza
Definicje:
- $\overline{\sigma}$ - ciąg instrukcji $\sigma$ po usunięciu Findów.
- **rząd wierzchołka** - jego wysokość w lesie po wykonaniu $\overline{\sigma}$,
- $log^*(n) = min\{k|F(k)\ge n\}$, gdzie $F(0)=1$ i $F(i)=2^{F(i-1)}$ dla $i>0$,
- **grupa rzędu** - rząd r umieszczamy w grupie $log^*(r)$.

Obserwacje:
- drzewo o wysokości $h$ ma co najmniej $2^h$ wierzchołków,
- jest co najwyżej $\frac{n}{2^r}$ wierzchołków rzędu r,
- każdy wierzchołek ma rząd co najwyżej $log(n)$,
- jeśli w trakcie wykonywania ciągu $\sigma$ wierzchołek staje się potomkiem $v$ to ma od niego mniejszy rząd,
- instrukcje Union wykonują się w czasie stałym, rozpatrujemy tylko Findy,
- koszt każdej instrukcji Find jest proporcjonalny do długości ścieżki na drodze do korzenia.

*Niech $c$ będzie dowolną stałą. Wówczas istnieje inna stała $c'$ (zależna od $c$), taka, że powyższe procedury wykonują dowolny ciąg $σ$ złożony z $cn$ instrukcji Union i Find w czasie $c'n log^∗ (n)$.*

#### Analiza zamortyzowana

Find płaci za odwiedzenie wierzchołka $w$, jeśli:
- $w$ jest korzeniem,
- synem korzenia,
- $w$ i jego ojciec mają rzędy w innych grupach.

W p. p. obarczamy kosztem wierzchołek.

- grup jest $\le log^*(n)$, Find zapłaci $\le log^*(n) + 1$,
- każda grupa zapłaci sumarycznie O(n).

bo:

*Ile jest wierzchołków o rzędach z grupy G?*
$$ \sum_{r=F(G-1)+1}^{F(G)} \frac{n}{2^r} \le n \cdot \frac{1}{2^{(G-1)+1}} \cdot \sum^\infty_{i=0} \frac{1}{2^i} = \frac{n}{2^{F(G-1)}} = \frac{n}{F(G)}$$

*Ile zapłaci każdy wierzchołek?*
- *Ile razy wierzchołek może zostać odwiedzony i nadal za siebie płacić?*

Wierzchołek za siebie płaci, kiedy jest w tej samej grupie co swój ojciec i jest właśnie odwiedzany (bo był na drodze finda). Za każdym takim razem dostaje nowego ojca z większym rzędem niż poprzedni, a mogło się to wydarzyć co najwyżej $(F(G)-F(G-1))$ razy.

Czyli koszt wierzchołka $\times$ liczba wierzchołków < n
$$\frac{n}{F(G)}\cdot (F(G)-F(G-1))<n$$

## Hashowanie
Następne słowniki.
- Do pamiętania elementów podzbioru wykorzystywana jest tablica $T[0, ..., m-1]$;
- zwykle m jest proporcjonalne do maksymalnej liczności słownika;
- wielkość uniwersum nie ma tu większego znaczenia.

Metoda wykorzystuje funkcję (tzw. funkcję haszującą) $h: U → \{0, ..., m-1\}$, określającą miejsce pamiętania elementów $U$ w $T$. Oczekujemy, że dla każdego wyniku (y z przeciwobrazu) suma prawdopodobieństw wylosowania x-ów (takich, że $h(x_i)= y$) równa się $\frac{1}{m}$.

#### Przykłady
- $h(k) = k$ mod $m$
m powinno być liczbą pierwszą daleko od potęg 2. (potęgi 2 i 10 są złe bo nie dają równomiernego rozkładu).
- $h(k) = \lfloor m(kA-\lfloor kA \rfloor \rfloor$
m powinno być potęgą 2 bo łatwe mnożenia, ale $A = (\sqrt{5}-1)/2$.

### Listy elementów

$i$-ty element tablicy zawiera wskaźnik na początek listy elementów x, dla których $h(x) = i$.
$\alpha=\frac{n}{m}$, współczynnik wypełnienia tablicy.
Średni koszt operacji Search to $\Theta(1 + \alpha)$ (czyli jeśli m jest liniowo zależny od n to koszt stały).

### Adresowanie otwarte

Elementy pamiętamy bezpośrednio w tablicy T. Często w trakcie będziemy zwiększać wielkość tablicy i losować nową funkcję haszującą do obsłużenia nowego rozmiaru.

Funkcja haszująca $h$ ma teraz dwa argumenty - element, który haszujemy i numer próby. Wymagamy, żeby $\forall _{k \in U} \langle h(k, 0), ..., h(k, m-1) \rangle$ jest permutacją zbioru $\{0, 1, ..., m-1\}$.
Funkcja $h'$ to zwykła funkcja haszująca.

**Usuwanie kolizji:**
- Metoda liniowa:
$h(k,i)=(h'(k)+i)$ mod $m$
- Metoda kwadratowa:
$h(k,i)=(h'(k)+c_1i+c_2 \cdot i^2)$ mod $m$
Oczywiście stałe $c_1, c_2 \neq 0$ i warunek z permutacjami musi być spełniony.

Te metody są słabe bo tworzą sie zlepki.
- Podwójne haszowanie: :crown:
$h(k,i)=(h_1(k)+ih_2(k))$ mod $m$
Dla każdego $k\in U$, $h(k)$ powinno być względnie pierwsze z m.

Podczas wykonywania operacji Delete w miejscu usuwanego elementu w tablicy T należy wpisać znacznik, świadczący o tym, że to miejsce było już wcześniej zajęte.

Analiza kosztów w L0706

### Rodziny uniwersalne

Rodzinę $H$ funkcji haszujących nazywamy uniwersalną, jeśli
$$\forall_{x,y\in U, x \neq y} |\{h\in H: h(x)=h(y)\}|\le\frac{|H|}{m}$$

Dla dowolnego zbioru $n\le m$ liczba kolizji w jakiej bierze udział dany klucz jest mniejsza od 1.

:::spoiler Przykłady
:::

### Schematy urnowe

- Gdy m kul wrzucamy losowo, niezależnie i w sposób jednostajny do n urn, to dla odpowiednio dużego n, z prawdopodobieństwem co najmniej 1−1/n liczba kul w najbardziej popularnej urnie nie przekracza $\frac{3 ln (n)}{ln(ln(n))}$.
- Paradoks urodzin: jeśli $m \le \sqrt{n}$ to z ppb'stwem > $\frac{1}{2}$ nie ma kolizji.
- jeśli dla każdej kuli losujemy dwie urny i wybieramy tą, w kórej jest mniej kul, to z dużym ppb maksymalna liczba kul w urnie to $\Theta(ln(ln\frac{n}{ln 2}))$.

### Słownik statyczny

n kluczy w O(n) komórkach, nie robimy insert ani delete.
Zrobimy hashowanie dwupoziomowe:
- pierwsza funkcja hashująca rozrzuca klucze tak, by $\sum^{n-1}_{i=0}n^2_i=O(n)$, gdzie $n_i$ - liczba kluczy wrzuconych do kubełka i,
- drugą funkcję losujemy aż będzie bezkolizyjna.

Szacowany czas działania w L0705.

## Wyszukiwanie wzorców

Chcemy znaleźć wszystkie wystąpienia wzorca w tekście.

### Notacja

- $\Sigma$ - ustalony alfabet.
- T[1, ..., n] i P[1, ..., m] - ciągi symboli z $\Sigma$,
- T - tekst,
- P - wzorzec,
- P występuje z przesunieciem s w T, jeśli $0\le s\le n -m$ oraz $T[s+1, ..., s+m]$,
- $w \sqsupset x$ - $w$ jest prefiksem $x$-a,
- $w \sqsubset x$ - $w$ jest sufiksem $x$-a.
- $X_k$ - $k$-elementowy perfiks $X$-a.

### Algorytm Karpa-Rabina

Słowa nad $d$-literowym alfabetem traktujemy jako liczby w systemie o podstawie $d$, jeśli zrobią się za duże to bierzemy modulo $q$ (duża liczba pierwsza), takie że $dq$ mieści się w słowie maszynowym.

Liczymy pierwszą liczbę tekstu i liczbę wzorca, porównujemy, jeśli się zgadzają to trzeba sprawdzić literka po literce (jeśli robimy mod $q$), następną liczbę tekstu dostajemy przez odcięcie pierwszej cyfry i dodanie ostatniej.


Koszt: $\Theta((n-m +1)\cdot m)$, działa fajnie dla niewielu wystąpień wzorca.

### Automaty skończone

Automat ma zbiór stanów Q, stan początkowy q, stan końcowy f, funkcja przejścia $\delta$.

::: spoiler automat sprawdzający podzielność przez 3
stan początkowy i końcowy to $q_0$.
wczytuje po kolei cyfry (zapis binarny) i jeśli skończy w $q_0$ to znaczy, że liczba jest podzielna przez 3.
:::

Automat będzie po kolei wczytywał literki, stany to następne literki wzorca. Jeśli wczyta właściwą ($k$-tą) literkę to przejedzie do następnego stanu, jeśli złą to przejdzie do $i$-tego stanu, $i$ jest największą taką liczbą, że $P_i \sqsubset T_k$.

Koszt samego automatu: $O(n)$. Funkcję $\delta$ da się zrobić w $O(m|\Sigma|)$

### Algorytm KMP

*Knutha-Morrisa-Pratta*
Jak poprzednio, Po przeczytaniu $T[i]$ chcemy znaleźć najdłuższy prefiks $P$, który jest sufiksem $T_i$.

Koszt: O(m). (Bo $k$ może sumarycznie spaść tylko o $m$).

Koszt: O(n+m).

### Algorytm Boyera-Moore'a

Podobnie do naiwnego, ale korzystamy z dwóch heurystyk:

#### Zły znak

Wczytaliśmy $s+j$-ty znak i nie zgadza się z $j$-tą literką wzorca. Szukamy największego $z < j$, takiego że $P[z]=T[s+j]$. Heurystyka proponuje przesunąć się o $j-z$ znaków.

#### Dobry sufiks

Patrzymy na sufiksy $P_k$, bierzemy najdłuższy taki, że $P_k \sqsupset P[j+1, ..., m]$ lub $P[j+1, ..., m] \sqsupset P_k$

### Algorytm Shift-AND

Pamiętamy informację o wszystkich prefiksach wzorca, które są sufiksami do tej pory przeczytanego tekstu. Używamy go do krótkich wzorców, więc prefiksy mogą być przechowywane w słowach maszynowych i uaktualnine w kilku instrukcjach.

Mamy tablicę tablic $C_j[0, ..., m], C_j[k] = true \iff P_k \sqsupset T_j$.


Dla każdej litery d tworzymy tablicę R_d,
taką że R_d[i] = (p_i == d).
C_j = Shift(C_{j-1}) AND R_p;
// Shift przesuwa o 1 w prawo i skrajny lewy bit ustawia na 1.

Wzorzec występuje z przesunięciem $j-m\iff C_j[m]=true$.

Koszt: $\Theta(n+m)$

### Algorytm KMR

*Karpa-Millera-Rosenberga*

$w$ - konkatenacja P i T.
Numerujemy (liczbami z $\{1, ..., n\}$) wszystkie podsłowa $w$ o długości $m$, tak że dwa słowa mają ten sam numer $\iff$ są takie same. Wypisujemy wszystkie podsłowa (o pozycji $>m$) o numerze tym samym co P (pozycja $1$).

- Startujemy od ponumerowania podsłów długości 1. (sortujemy litery).
- Z numeracji dla słów długości k tworzymy numerację dla słów długości $k'\in \{k+1, ..., 2k\}$:
- Dla $i$-tego słowa (długości k') tworzymy parę $\langle nr_k(i), nr_k(i+k'-k+1)\rangle$. ($nr_s(j)$ to numer $s$-literowego podsłowa na pozycji j).
- Sortujemy leksykograficznie utworzone pary ($j$-te słowo dostaje numer *liczba różnych par na lewo*).

:::spoiler Przykład
:::

Koszt: $\Theta(n \log{m})$. (bo liczymy numerację dla $\lceil \log{m} \rceil$ długości i dla każdej z nich idzie liniowo (radix sort)).

## FFT

Chcemy pomnożyć dwa wielomiany.
*(Dwie liczby x to podstawa systemu liczbowego).*
Będziemy je reprezentować jako zbiór punktów.
*(Wielomian A stopnia $n-1$ zapiszemy jako $n$ par $(x_i,y_i)$ takich, że $A(x_i)=y_i$).*
Mnożenie w takiej postaci jest bardzo łatwe, ale obliczanie wartości w (dowolnym) punkcie już nie :((interpolacja Lagrange'a w $O(n^2)$).

### Dziel i zwyciężaj

Chcemy policzyć wartości wielomianu A stopnia $n-1$ w n punktach $x\in X$.
$P(x) = a_0 +a_1x + ... + a_{n-1}x^{n-1}$
$A(x) = a_0 + a_2x + a_4x^2 + ... + a_{n-2}x^{\frac{n}{2}-1}$
$B(x) = a_1 + a_3x + a_5x^2 + ... + a_{n-1}x^{\frac{n}{2}-1}$
$P(x) = A(x^2)+xB(x^2)$

Schodzimy tak rekurencyjnie w dół, aż zostanie jedno $a$ (wielomian stopnia 0), ale nie wiemy, jak wybierać właściwe punkty kiedy tak schodzimy (no bo wystarczy połowa). Chcemy tak dobrać punkty, żeby przy każdym kwadraceniu połowa wyrazów sama się zeżarła, żeby rzeczywiście redukować problem. (i mieć $O(n\log{n}))$).

### Liczby zespolone

Nie ma takiego $2^k$-elementowego zbioru $X$, że za każdym razem jak skwadracimy wszystkie elementy dostaniemy zbiór 2 razy mniejszy, więc musimy go sobie uroić.

Chcemy pierwiaski $n$-tego stopnia z 1. $\cos{\Theta}+i\sin{\Theta}$ dla $\Theta = 0, 2\pi / n, ..., (n-1)2\pi /n$, czyli $e^{i\Theta}=e^{2\pi i k / n}=\omega_n^k$, dla $k=0,1,..., n-1$.

Ten wzór jest ładny, bo $(e^{i\Theta})^2=e^{2i\Theta}$.

### DFT (Dyskretna Transformacja Fouriera)

Niech wektor współczynników to $a$, wektor igrekowych wpółrzędnych punktów to $y$. $y$ to DFT. Macierz $V_n$ jest $n \times n$, $V_n[j,k]=\omega_n^{jk}$.
$y=V_n \cdot a$.

### Powrót do współczynników

Umiemy przekształcić nasze wielomiany w $O(n\log{n})$ w zbiory punktów, pomnożyć w $O(n)$, teraz trzeba przekształcić wynik na normalną postać. $V_n^{-1} \cdot y = a$.

**Fakt**: $(j,k)$-ty wyraz $V_n^{-1} = \omega_n^{-jk}/n$
:::spoiler uzaasadnienie
:::
Chcemy policzyć $nV_n^{-1} \cdot y$, czyli $a$.

No to mamy macierz, którą musimy pomnożyć przez wektor, brzmi kwadratowo... Ale ta macierz jest nie byle jaka, w końcu j-ty wiersz składa się z $(\omega^{-1\cdot j})^{ 0}, (\omega^{-1\cdot j})^{ 1}, ..., (\omega^{-1\cdot j})^{ n}$ hmmmm...
I my to mnożymy razy wektor $y$, potraktujmy go jako wektor współczynników wielomianu, wtedy w j-tej komórce wyniku mnożenia będziemy mieć $\frac{1}{n}\sum^n_{k=0}y_k \cdot(\omega^{-1\cdot j})^{k}$, czyli policzyliśmy wartość jakiegoś wielomianu. I my liczymy wartość tego wielomianu dla n punktów (też pierwiastków z 1), czyli możemy zastosować to co robiliśmy do tej pory.

## Emde Boas

Mamy uniwersum liczb całkowitych $U$, $|U|=u=2^{2^k}$ i chcemy mieć $n$ elementów w strukturze $S$.

Chcemy wykonywać operacje:
- insert,
- successor (najmniejszy element większy od danego),
- delete.

Chcemy następnika w $\log{\log{u}}$, czyli $T(k)=T(\sqrt{k})+O(1)$, czyli $T(2^{2^k}) = T(2^{2^{k-1}})+ O(1)$.

#### Prosty pomysł 1:
Tablica t długości $u$, taka, że $t[i] = i \in S$
Koszt $O(u)$

#### Prosty pomysł 2:

Drzewo przedziałowe (czy jest jakiś element na tym przedziale) $O(\log {u})$.

#### Prosty pomysł 3:

Struktura pierwiastkowa, $O(\sqrt{u})$.

Mamy tablicę długości $u$, taką, że $t[i] = i \in S$.
Dzielimy ją na kępki długości $\sqrt{u}$.
Tworzymy streszczenie tej tablicy, dla każdej kępki pamiętamy, czy była w niej jakaś jedynka.

Teraz, żeby znaleźć następcę wystarczy przejrzeć wszystkich ludzi na prawo od nas w naszej kępce, jeśli nie ma to znaleźc w streszczeniu najbliższą kępkę w której coś będzie i tam znaleźć.

### Rozwiązanie


Terminologia:
$x = i \cdot \sqrt{u} + j$, $0 \le j < \sqrt{u}$

- $high(x) = \left\lfloor \frac{x}{\sqrt{u}}\right \rfloor$,
- $low(x) = x \mod \sqrt{u}$,
- $index(i, j) = x$.

$V$ - Struktura van Emde Boasa (vEB) rozmiaru u składa się z:
- V.cluster[i] struktury vEB rozmiaru $\sqrt{u}$ dla $0 \le i < \sqrt{u}$ (kępki),
- V.summary struktury vEB rozmiaru $\sqrt{u}$ (streszczenie).

Operacje:

Insert(V, x):
    Insert(V.cluster[high(x)], low(x))
    Insert(V.summary, high(x))

 Successor(V, x):
    i = high(x)
    j = Successor(cluster[i], low(x))
    if j = inf:
        i = Successor(V.summary, i)
        j = Successor(V.cluster[i], -inf)
    return index(i, j)

:((( to nadal nie jest $\log{\log{u}}$, musimy mieć tylko jedno wywołanie rekurencyjne, żeby być szczęśliwi.

Będziemy trzymać minimum i maksimum w każdej strukturze.

Insert(V, x):
    if x < V.min:
        V.min = x
    if x > V.max:
        V.max = x
    Insert(V.cluster[high(x)], low(x))
    Insert(V.summary, high(x))

 Successor(V, x):
    i = high(x)
    if low(x) < V.cluster[i].max:
        j = Successor(cluster[i], low(x))
    else
        i = Successor(V.summary, i)
        j = V.cluster[i].min //<---
    return index(i, j)

Następca naprawiony, teraz wstawianie: pierwszy raz kiedy coś wsadzamy do kępki musimy wykonać wywołanie rekurencyjne do streszczenia. Sprawimy, że minimum jest leniwe, nie będziemy go rekurencyjnie wpisywać.

Insert(V, x):
    if V.min = None:
        V.min = V.max = x
        return
    if x < V.min:
        swap(V.min, x)
    if x > V.max:
        V.max = x
    if V.cluster[high(x)].min = None:
        Insert(V.summary, high(x))
    Insert(V.cluster[high(x)], low(x))
    

 Successor(V, x):
     if x < V.min:
         return V.min
    i = high(x)
    if low(x) < V.cluster[i].max:
        j = Successor(V.cluster[i], low(x))
    else
        i = Successor(V.summary, i)
        j = V.cluster[i].min //<---
    return index(i, j)

To już działa, bo jeśli wykonamy pierwsze wykonanie rekurencyjne, kępka x była pusta, to drugie wywołanie od razu sie zatrzyma na pierwszym warunku.

Delete(x, V)
    if x = V.min:
        i = V.summary.min
        if i = None 
            V.max = V.min = None
        x = V.min = V.index(i, V.cluster[i].min)
    Delete(V.cluster[high(x)].low(x))
    if V.cluster[high(x)].min = None
        Delete(V.summary, high(x))
    if x = V.max:
        if V.summary.max = None:
            V.max = V.min
        else
            i = V.summary.max
            max = index(i, V.cluster[i].max)

## Sieci sortujące

Chcemy zbudować sieć sortującą z komparatorów.

:::spoiler przykład
:::

Głębokość druta to głębokość komparatora, którego wyszedł lub 0 jeśli nie przeszedł przez żadny. Głębokość komparatora to max(wejście1, wejście2) + 1.

Dwa komparatory na tej samej głębokości mogą działać równolegle.

### Zasada zero-jedynkowa

**Lemat**: Jeśli sieć dla wejścia $\langle a_1, ..., a_n \rangle$ zwraca $\langle b_1, ..., b_n \rangle$, to dla dowolnej funkcji niemalejącej $f$ ta sieć dla $\langle f(a_1), ..., f(a_n) \rangle$ zwróci $\langle f(b_1), ..., f(b_n) \rangle$

**Zasada**: Jeśli sieć działa dla wszystkich ciągów z 0 i 1 to działa dla wszystkich ciągów.

Nie wprost:
Istnieje ciąg $\langle a_1, ..., a_n \rangle$ dla którego nie działa, czyli są takie elementy $a_i < a_j$, że sieć zwraca je w złej kolejności. Niech $f(x) = (x > a_i)$. $siec(f(a_i)) > siec(f(a_j))$, sprzeczność.

Będziemy teraz rozważać tylko ciągi zerojedynkowe.

### Sieć półczyszcząca
Ciąg bitoniczny to taki, że $a_1 \le a_2 \le ... \le a_i \ge a_{i+1} \ge ... \ge a_n$ lub $a_1 \ge a_2 \ge ... \ge a_i \le a_{i+1} \le ... \le a_n$.

Nasza sieć przyjmuje na wejściu ciąg bitoniczny i rozbija go na *czystą* półówkę i bitoniczną półowkę (same zera na górze lub same jedynki na dole).


### Sieć bitoniczna

Sieć półczyszcząca rekurencjnie.

### Sieć scalająca

Tym razem mamy dwa posortowane podciągi, zamiast jednego bitonicznego, odwróćmy kolejność na dolnym i połączmy to będziemy mieć bitoniczny. Zapuśćmy sieci bitoniczne to nam posortuje (wystarczy ogarnąć połówki, relacja miedzy nimi jest ok).


### Sieć sortująca

Rekurencyjnie scalamy.

Głębookość: $\log^2{n}$

## Mnożenie macierzy

Macierze A i B są $n \times n$.

### Metoda Strassena

Dziel i zwyciężaj:
Jedno duże mnożenie zastępujemy 8 mały mi nadal mamy $O(n^3)$, Strassenowi udało się to zbić do 7.

### Mnożenie macierzy logicznych - Metoda czterech Rosjan

Zakładamy, że cały wiersz macierzy możemy przechować w rejestrze: i szyybko wykonywać operacje logiczne.

Podzielimy A i B na $\frac{n}{\log{n}}$ macierzy, A na $A_i$ o rozmiarze $\log{n}\times n$, B na $B_i$ o rozmiarze $n \times \log{n}$.


$A_i \cdot B_i$ jest $n \times n$ i
$$A \cdot B = \sum _{i=1}^{n/log n} A_i \cdot B_i$$

Jak policzyć macierz $C_i = A_i \cdot B_i$?
- jeśli $j$-ty wiersz $A_i$ składa się z samych zer, to $j$-ty wiersz $C_i$ też,
- jeśli $j_1$ można uzyskać z $j_2$ poprzez zmianę jednego 0 na 1 (na pozycji $k$) to wiersz $j_2$ jest ORem wiersza $j_1$ i wiersza $k$ macierzy $B_i$.

Wiersze $A_i$ mają długość $\log{n}$, czyli jest maksymalnie $n$ różnych wierszy i można policzyć wszystkie możliwe warianty wierszy$\times B_i$ w $O(n^2)$.

Wykonujemy $O(n^2/log(n))$ operacji na wektorach bitów.
:::spoiler algorytm
:::