# AiSD Listy 2024
## Zad 1
```rust=
use std::cmp;
// Definicja struktury węzła drzewa binarnego
#[derive(Debug)]
struct TreeNode {
val: i32,
left: Option<Box<TreeNode>>,
right: Option<Box<TreeNode>>,
}
impl TreeNode {
fn new(val: i32) -> Self {
TreeNode { val, left: None, right: None }
}
}
// Funkcja obliczająca maksymalną głębokość drzewa
fn max_depth(root: &Option<Box<TreeNode>>) -> i32 {
match root {
None => 0,
Some(node) => {
let left_depth = max_depth(&node.left);
let right_depth = max_depth(&node.right);
cmp::max(left_depth, right_depth) + 1
}
}
}
// Funkcja obliczająca maksymalną odległość między wierzchołkami
fn max_distance(root: &Option<Box<TreeNode>>) -> i32 {
match root {
None => 0,
Some(node) => {
let max_left = max_depth(&node.left);
let max_right = max_depth(&node.right);
let left_distance = max_distance(&node.left);
let right_distance = max_distance(&node.right);
cmp::max(max_left + max_right, cmp::max(left_distance, right_distance))
}
}
}
fn main() {
// Konstruowanie drzewa binarnego:
// 1
// / \
// 2 3
// / \
// 4 5
let mut root = TreeNode::new(1);
root.left = Some(Box::new(TreeNode::new(2)));
root.right = Some(Box::new(TreeNode::new(3)));
root.left.as_mut().unwrap().left = Some(Box::new(TreeNode::new(4)));
root.left.as_mut().unwrap().right = Some(Box::new(TreeNode::new(5)));
println!("Maksymalna odległość między wierzchołkami: {}", max_distance(&Some(Box::new(root))));
}
```
Poprawiona funkcja do drugiego podpunktu zwraca parę (depth, max_len)
```python=
def max_len(T):
if (T == null):
return (0, 0)
left = max_len(T.left)
right = max_len(T.right)
depth = max(left.depth, right.depth) + 1
local_max_len = max(left.max_len, right.max_len)
return (depth, max(local_max_len, left.depth + right.depth + 2))
```
## Zad 2 ?
W tych procedurach przyjmuje się, że kopiec minimaksowy jest przechowywany w tablicy, gdzie korzeń znajduje się na indeksie $1$, a dzieci wierzchołka o indeksie $i$ znajdują się na indeksach $2*i$ i $2*i+1$. Procedura $element(Kopiec[indeks])$ zwraca wartość elementu w kopcu na podanym indeksie. Funkcja $rozmiar(Kopiec)$ zwraca aktualny rozmiar kopca.
Procedura Przywracania Porządku
```python=
PrzywróćPorządek(Kopiec, indeks)
jeżeli indeks > rozmiar(Kopiec) / 2 to
Powrót // Nie ma dzieci, koniec rekurencji
indeks_najmniejszy = indeks // Załóż początkowo, że bieżący indeks jest najmniejszy
indeks_lewe = 2 * indeks
indeks_prawe = 2 * indeks + 1
jeżeli indeks_lewe <= rozmiar(Kopiec) i element(Kopiec[indeks_lewe]) < element(Kopiec[indeks_najmniejszy]) to
indeks_najmniejszy = indeks_lewe // Aktualizuj indeks najmniejszego elementu
jeżeli indeks_prawe <= rozmiar(Kopiec) i element(Kopiec[indeks_prawe]) < element(Kopiec[indeks_najmniejszy]) to
indeks_najmniejszy = indeks_prawe // Aktualizuj indeks najmniejszego elementu
jeżeli indeks_najmniejszy != indeks to
Zamień(Kopiec[indeks], Kopiec[indeks_najmniejszy]) // Zamień elementy
PrzywróćPorządek(Kopiec, indeks_najmniejszy) // Rekurencyjnie przywróć porządek dla dziecka
```
Procedura Usuwania Minimum:
```python=
UsuńMinimum(Kopiec)
minimum = element(Kopiec[1]) // Zapamiętaj minimum (pierwszy element kopca)
Kopiec[1] = Kopiec[ostatni] // Zastąp korzeń ostatnim elementem kopca
zmniejsz rozmiar(Kopiec) o 1 // Zmniejsz rozmiar kopca
PrzywróćPorządek(Kopiec, 1) // Przywróć porządek od korzenia
Powrót minimum
```
Procedura Usuwania Maksimum:
```python=
UsuńMaksimum(Kopiec)
maksimum = element(Kopiec[1]) // Zapamiętaj maksimum (pierwszy element kopca)
indeks_maksimum = 1 // Indeks maksimum to korzeń
dla każdego i od 2 do rozmiar(Kopiec) wykonaj
jeżeli element(Kopiec[i]) > element(Kopiec[indeks_maksimum]) to
indeks_maksimum = i // Aktualizuj indeks maksimum
Kopiec[indeks_maksimum] = Kopiec[ostatni] // Zamień maksimum z ostatnim elementem kopca
zmniejsz rozmiar(Kopiec) o 1 // Zmniejsz rozmiar kopca
PrzywróćPorządek(Kopiec, indeks_maksimum) // Przywróć porządek od indeksu maksimum
Powrót maksimum
```
## Zad 3
Porządkiem topologicznym wierzchołków acyklicznego digrafu $G = (V,E)$ nazywamy taki liniowy porządek jego wierzchołków, w którym początek każdej krawędzi występuje przed jej końcem. Jeżli wierzchołki z $V$ utożsamimy z początkowymi liczbami naturalnymi to każdy ich porządek liniowy można opisać permutacją liczb $1, 2, ..., |V|$; w szczególności pozwala to na porównywanie leksykograficzne porządków.
Ułóż algorytm, który dla danego acyklicznego digrafu znajduje pierwszy leksykograficznie porządek topologiczny.
1. Stwórz pustą listę wynikową, która będzie przechowywać porządek topologiczny.
2. Zlicz liczbę wejść do każdego wierzchołka w grafie.
3. Dodaj wszystkie wierzchołki o zerowej liczbie wejść do kolejki gdzie priorytet jest leksykograficzny.
4. Dopóki kolejka nie jest pusta:
a. Pobierz wierzchołek z kolejki i dodaj go do wynikowej listy.
b. Dla każdej krawędzi wychodzącej z tego wierzchołka, zaktualizuj liczbę wejść do wierzchołka docelowego, usuwając jedno wejście.
c. Jeśli liczba wejść do wierzchołka docelowego wynosi zero, dodaj go do kolejki.
5. Jeśli wynikowa lista zawiera wszystkie wierzchołki, zwróć tę listę jako wynik porządku topologicznego.
6. W przeciwnym razie zwróć informację, że graf zawiera cykl
::: warning
Kolejka musi być priorytetowa i algorytm ten będzie miał złożoność $O (|V|log|V|+|E|)$
:::
```python=
from collections import defaultdict, deque
def topological_sort(graph):
indegree = defaultdict(int)
for node in graph:
for neighbor in graph[node]:
indegree[neighbor] += 1
zero_indegree_nodes = deque(node for node in graph if indegree[node] == 0)
topological_order = []
while zero_indegree_nodes:
node = zero_indegree_nodes.popleft()
topological_order.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
zero_indegree_nodes.append(neighbor)
return topological_order
# Przykładowe użycie:
graph = {
1: [2, 3],
2: [4],
3: [4],
4: [5],
5: []
}
topological_order = topological_sort(graph)
print("Pierwszy leksykograficznie porządek topologiczny:", topological_order)
```
Niezmienniki :
- Zawsze istnieje co najmniej jeden 0-in wierzchołek.
- Kolejka zawsze wypluwa co najmniej jeden taki wierzchołek
Istnieje wierzchołek z 0 wchodzącymi krawędziami bo graf jest acykliczny. Mój algorytm weźmie te wszystkie wierzchołki do kolejki i zwróci najmniejszy leksykograficznie wierzchołek. Za każdym razem gdy dodajemy do kolejki zabieramy wchodzące krawędzie do innych wierzchołków. Jako, że jest to graf acykliczny to po zabraniu wszystkich takich wierzchołków mamy gwarancję, że pojawi się nowy 0-in wierzchołek bo inaczej musiałby istnieć cykl.
Załóżmy, że mamy poprawnie wypełnione rozwiązanie do pewnego momentu. To co skonstruowaliśmy jest poprawne.
## Zad 4
Niech $u$ i $v$ będą dwoma wierzchołkami w grafie nieskierowanym $G = (V,E, c)$, gdzie $c : E \rightarrow R_+$ jest funkcją wagową. Mówimy, że droga z $u = u1, u2, ...., u_{k-1}, u_k = v$ z $u$ do $v$ jest sensowna, jeżeli dla każdego $i = 2, ... , k$ istnieje droga z $u_i$ do $v$ krótsza od każdej drogi z $u_{i-1}$ do $v$ (przez długość drogi rozumiemy sumę wag jej krawędzi).
Ułóż algorytm, który dla danego $G$ oraz wierzchołków $u$ i $v$ wyznaczy liczbę sensownych dróg z $u$ do $v$.
1. Inicjalizujemy tablicę $dp$, gdzie $dp[i][j]$ będzie przechowywać liczbę sensownych dróg z wierzchołka $u_i$ do wierzchołka $v_j$.
2. Tablica $dp$ będzie miała wymiary $|V| \times |V|$, gdzie $|V|$ to liczba wierzchołków w grafie.
3. Inicjalizujemy tablicę $dp$ wartościami początkowymi. $dp[i][j] = 0$ dla wszystkich $i \neq j$, a $dp[i][i] = 1$, ponieważ zawsze istnieje jedna sensowna droga z wierzchołka do samego siebie (droga pusta).
4. Przechodzimy przez wierzchołki grafu, zaczynając od $u$:
a. Dla każdego wierzchołka $u_i$, znajdujemy wszystkie krawędzie $(u_i, v_j)$, gdzie $v_j$ jest wierzchołkiem sąsiadującym z $u_i$.
b. Dla każdej takiej krawędzi, aktualizujemy wartość $dp[u_i][v_j]$ sumując wartość $dp[u_i][u_k]$ dla wszystkich sąsiadujących z $v_j$ wierzchołków $u_k$, takich że $u_k \neq u_i$.
5. Powtarzamy kroki 4, aż przejdziemy przez wszystkie wierzchołki.
6. Ostateczna odpowiedź to suma wartości $dp[u_i][v]$, gdzie $u_i$ to wszystkie sąsiadujące wierzchołki z $u$.
```python=
def count_sensible_paths(graph, u, v):
n = len(graph)
dp = [[0] * n for _ in range(n)]
# Inicjalizacja wartości dla diagonalnej
for i in range(n):
dp[i][i] = 1
# Przechodzenie przez wierzchołki grafu
for i in range(n):
for j in range(n):
if i != j:
for k in range(n):
if k != i:
dp[i][j] += dp[k][j] if (i, k) in graph and (k, j) in graph else 0
# Sumowanie wartości dla wszystkich sąsiadujących wierzchołków z u
total_paths = sum(dp[u_i][v] for u_i in range(n) if (u, u_i) in graph)
return total_paths
# Przykładowe użycie
graph = {
(0, 1): 1, # Krawędź (0, 1) z wagą 1
(0, 2): 2, # Krawędź (0, 2) z wagą 2
(1, 2): 1, # Krawędź (1, 2) z wagą 1
(1, 3): 1, # Krawędź (1, 3) z wagą 1
(2, 3): 2 # Krawędź (2, 3) z wagą 2
}
u = 0
v = 3
print("Liczba sensownych dróg z u do v:", count_sensible_paths(graph, u, v))
```
## Zad 5
Ułóż algorytm, który dla zadanego acyklicznego grafu skierowanego G znajduje długość najdłuższej drogi w G. Następnie zmodyfikuj swój algorytm tak, by wypisywał drogę o największej długości (jeżeli jest kilka takich dróg, to Twój algorytm powinien wypisać dowolną z nich).
1. Stwórz listę $distance$ o długości równej liczbie wierzchołków grafu, początkowo wypełnioną wartościami 0.
2. Przejdź przez wierzchołki grafu w porządku topologicznym.
3. Dla każdego wierzchołka $v$, przejdź przez wszystkie krawędzie wychodzące z $v$ i zaktualizuj wartość $distance$ dla każdego wierzchołka docelowego.
4. Wartość $distance[v]$ będzie ostateczną najdłuższą drogą do wierzchołka $v$.
5. Zwróć maksymalną wartość z listy $distance$.
```python=
from collections import defaultdict
def longest_path(graph):
def dfs(v):
nonlocal max_length
if v not in visited:
visited.add(v)
for neighbor, weight in graph[v]:
max_length = max(max_length, dfs(neighbor) + weight)
return max_length
return 0
max_length = 0
visited = set()
for vertex in graph:
max_length = max(max_length, dfs(vertex))
return max_length
# Przykładowe użycie:
graph = {
'A': [('B', 5), ('C', 3)],
'B': [('D', 7)],
'C': [('D', 2)],
'D': [('E', 4)],
'E': []
}
print("Długość najdłuższej drogi:", longest_path(graph))
```
Modyfikacja DFSa aby zwracać najdłuższą drogę
```python=
def dfs(v):
nonlocal max_length, max_path
if v not in visited:
visited.add(v)
for neighbor, weight in graph[v]:
path_length = dfs(neighbor) + weight
if path_length > max_length:
max_length = path_length
max_path = [v] + max_path
return max_length
return 0
```
## Zad 6 WIP
Dany jest niemalejący ciąg $n$ liczb całkowitych dodatnich $a_1 \le a_2 \le ... \le a_n$. Wolno nam modyfikować ten ciąg za pomocą następującej operacji: wybieramy dwa elementy $a_i, a_j$ spełniające $2a_i \le a_j$ i wykreślamy je oba z ciągu. Ułóż algorytm obliczający, ile co najwyżej elementów możemy w ten sposób usunąć.
1. Inicjuj licznik usuniętych elementów na $0$.
2. Iteruj przez ciąg od początku do końca:
a. Sprawdź dla każdego elementu $a[i]$, czy istnieje element $a[j]$ (gdzie $j$ > $i$) spełniający warunek $2*a[i]$ <= $a[j]$.
b. Jeśli tak, usuń $a[i]$ i $a[j]$, zwiększ licznik usuniętych elementów o $2$, i zacznij iterację od nowa od pierwszego elementu.
c. Jeśli nie, przejdź do kolejnego elementu.
3. Zwróć ostateczną liczbę usuniętych elementów.
```python=
def max_removed_elements(arr):
removed_count = 0
n = len(arr)
i = 0
while i < n - 1:
j = i + 1
while j < n:
if arr[j] >= 2 * arr[i]:
arr.pop(j)
arr.pop(i)
removed_count += 2
n -= 2
i = 0
break
j += 1
else:
i += 1
return removed_count
# Przykładowe użycie:
arr = [1, 2, 3, 4, 5, 6]
print("Maksymalna liczba usuniętych elementów:", max_removed_elements(arr))
```
## Zad 7
Dany jest nieskierowany graf ważony $G = (V,E, c)$ z $c : E \rightarrow R_+$ oraz ciąg $v_1, v_2, ..., v_k$ różnych wierzchołków z $V$. Niech $D_j (0 \le j \le k)$ będzie sumą długości najkrótszych ścieżek między wszystkimi parami wierzchołków pozostającymi w $G$ po usunięciu wierzchołków $v_1, v_2, ..., v_j$ (wraz z wierzchołkiem usuwamy wszystkie incydentne z nim krawędzie).
Ułóż algorytm obliczający wartości $D_0,D_1, ...,D_k$.
1. Dla każdego wierzchołka $v$ w grafie $G$:
Inicjalizuj $D[v][v] = 0$
Dla każdej krawędzi $e$ incydentnej do $v$, ustaw $D[v][u] = waga(e)$
2. Dla $j$ od $0$ do $k$:
2.1 Utwórz graf pomocniczy $G'$ poprzez usunięcie wierzchołków $v_1, v_2, ..., v_j$ oraz ich incydentnych krawędzi z $G$.
2.2 Dla każdej pary wierzchołków $(u, v)$ w $G'$:
Oblicz najkrótszą ścieżkę pomiędzy $u$ i $v$ algorytmem Dijkstry i zapisz jej długość w $D[j+1][u][v]$.
3. Oblicz $D[j][u]$ jako sumę $D[j+1][u][v]$ dla wszystkich par wierzchołków $v$ w $G'$ dla każdego $u$ w $G'$.
## Zad 8
## Lista 2
### Zad 6
### Zad 7
```c++
visited[i] = {false}
DFS (G, cur, e_value, e2){
visited[cur] = true
if(cur == e2)
return;
for(i in cur.neighbours)
if(c(cur, i) < e_value and !visited[i])
DFS(G, i, e_value, e2)
}
e_in_mst(G, e){
DFS(G/e, e.first, c(e), e.second)
return !visited[e.second];
}
```
Dowód:
**Lemat 1: Cycle property:**
For any cycle C in the graph, if the weight of an edge e of C is larger than any of the individual weights of all other edges of C, then this edge cannot belong to an MST.
Proof: Assume the contrary, i.e. that e belongs to an MST T1. Then deleting e will break T1 into two subtrees with the two ends of e in different subtrees. The remainder of C reconnects the subtrees, hence there is an edge f of C with ends in different subtrees, i.e., it reconnects the subtrees into a tree T2 with weight less than that of T1, because the weight of f is less than the weight of e.
**Lemat 2: jeżeli na każdym cyklu, który zawiera krawędź e istnieje krawędź cięższa niż krawędź e, to e należy do MST.**
Dowód:
Rozważmy krok algorytmy Kruskala, w którym rozpatrywana jest krawędź e. Zauważmy, że dodanie krawędzi e do stworzonego do tej pory drzewa nie utworzy nam cykly, ponieważ z założenia istnieje krawędź cięższa na każdym cyklu, nierozpatrzona jeszcze przez algorytm, czyli nasza krawędź będzie w MST.
**Dowód algorytmu:**
Oznaczmy wierzchołki krawędzi e jako (e1,e2)
Nasz algorytm sprawdza czy istnieje ścieżka od e1 do e2 nieprzechodząca przez tą krawedź taka, że waga każdej krawędzi na tej ścieżce jest mniejsza od wagi krawędzi e. Jeżeli istnieje, to z Lematu 1 wynika, że e nie należy do MST. Jeśli nie istnieje to z lematu drugiego wynika, że należy do MST.
### Zad 8
```=
a; b; c;
visited[n];
depth[n];
next[n];
func dfs(v)
visited[v] = true
if v is a leaf
depth[v] = 0
next[v] = null
return
for u in neighbours[v]
if not visited[u]
dfs(u)
if depth[u] + 1 > depth[v]
depth[v] = depth[u] + 1
next[v] = u
func diameter(T)
v = dowolny wierzchołek, np 1
visited = {0, 0...}
depth = {0, 0...}
next = {0, 0...}
dfs(v)
while next[v]
v = next[v]
a = v
visited = {0, 0...}
depth = {0, 0...}
next = {0, 0...}
dfs(v)
while next[v]
v = next[v]
b = v
```
#### Znajdowanie wierzchołka najdalej od średnicy
1. dfs-em policz odległość od średnicy dla każdego wierzchołka
2. weź max z tych odległości
```=
dist[n];
func distance(v)
visited[v] = 1
for w in neighbours[v]
if not visited[w]
if dist[w] != 0
dist[w] = max(dist[w], dist[v]+1)
distance(w)
func find_c(T)
dist = {inf, inf...}
visited = {0, 0...}
v = a
while next[v]
dist[v] = 0
v = next[v]
distance(a)
c = a
for v in V(T)
if dist[v] > dist[c]
c = v
if dist[c] == 0
c = any vertex
```
### Zad 9
Docelowa permutacja to 123…n.
Zauważmy, że permutację można rozbić na cykle i swapować tylko wewnątrz nich. Cykle dwuelementowe można rozwiązać jednym swapem. W każdym kroku algorytmu rozbiijamy lewy cykl na dwa (cykl, którego pierwszy element jest pierwszym elementem nie na miejscu).
Znajdźmy element najbardziej na prawo x w tym cyklu, jego poprzednika p i pierwszy element po x (idąc cyklem), który chce iść w lewo y. Zamieńmy p i y.
Elementy pomiędzy x a p stworzą cykl z x-sem, osobny cykl stworzy p z resztą elementów.
T(n) = T(n - k) + T(k) + O(n)
Czyli oczekiwany czas :(((
:::spoiler O(n^2)
Nie rozważamy elementów na właściwym miejscu, będziemy zamieniać "sąsiadów" (elementy, pomiędzy którymi nie ma elementów, które nie są na swoim miejscu), jeśli zamiana przybliży obydwu do swoich miejsc.
#### Uzasadnienie poprawności:
Każdy krok przybliża jakiś element i zawsze można wykonać krok.
Dowód nie wprost:
Zauważmy, że skrajne elementy można tylko przybliżyć (bo nie są na swoich miejscach), w takim razie drugi element oddaliłby się, przy zamianie z pierwszym, więc przy zamianie z trzecim się przybliży. No to trzeci się oddala przy zamianie z drugim… Przedostatni element się przybliży w zamianie z ostatnim, ale ostatni się już nie może oddalać: sprzeczność.
Koszt swapowania $i$ i $j$ to $k =|i-j|$, przesuwamy oba elementy o k, więc suma odległości wszystkich elementów zmniejszyła się o 2k. Zatem najtańszsze rozwiązanie kosztuje 1/2 odległości poczatkowych i tyle kosztuje nasz algorytm.
Zlozonosc O(n^2) bo w kazdej iteracji wiekszej petli ustawimy jakiegos dobrze, dokladnie ostatniego ktory chce isc na prawo.
:::
### Zad 10
### Zad 11
## Lista 3
### Zad 1
bez podłogi może się całkiem zepsuć np. dla $n=3$
### Zad 2
### Zad 3
:::warning
błędne rozw
:::
Algorytm Karatsuby jest znany z wydajnego mnożenia dużych liczb, ale modyfikacja go dla obliczania kwadratu liczby jest ciekawym zadaniem. Rozważmy modyfikacje dla k = 2 i k = 3:
:::spoiler zwykly Karatsuba
Algorytm Karatsuby jest szybkim algorytmem mnożenia wielomianów i liczb, który wykorzystuje technikę podziału i zwyciężaj. Można go również zastosować do mnożenia dużych liczb całkowitych.
Algorytm Karatsuby opiera się na następującym założeniu: aby pomnożyć dwie liczby o długości n, można je podzielić na połowę, aby otrzymać cztery mniejsze liczby, a następnie użyć zależności między nimi, aby zredukować liczbę mnożeń potrzebnych do uzyskania wyniku.
Przykład:
Weźmy dwie liczby całkowite do pomnożenia: 1234 i 5678.
1. Podziel obie liczby na pół:
Pierwsza liczba: 12 | 34
Druga liczba: 56 | 78
2. Oblicz iloczyny częściowych:
a. Iloczyn pierwszych cyfr: 12 * 56 = 672
b. Iloczyn ostatnich cyfr: 34 * 78 = 2652
3. Oblicz sumę i różnicę iloczynów częściowych:
a. Suma: 672 + 2652 = 3324
b. Różnica: (12 * 34) + (56 * 78) - (672 + 2652) = 4140 - 3324 = 816
4. Teraz składamy te iloczyny częściowe w odpowiedni sposób:
6720000 + 81600 + 2652 = 7006652
Więc wynik mnożenia 1234 przez 5678 to 7006652.
Algorytm Karatsuby jest znacznie bardziej efektywny niż standardowy algorytm mnożenia "szkoły podstawowej", ponieważ redukuje liczbę operacji mnożenia, co przyspiesza obliczenia, szczególnie w przypadku dużych liczb.
:::
### Dla k = 2:
Algorytm Karatsuby standardowo dzieli liczby na dwie równe części. Możemy wykorzystać podobny pomysł do obliczania kwadratu liczby.
1. Dla liczby n, możemy podzielić ją na dwie części o długości n/2.
2. Obliczamy kwadrat pierwszej części (a^2), kwadrat drugiej części (b^2).
3. Obliczamy iloczyn części pierwszej i drugiej (ab).
4. Kwadrat liczby n to suma kwadratu a * $10^n$, dwukrotności iloczynu a i b * $10^{n/2}$ oraz kwadratu b.
### Dla k = 3:
Analogicznie do k = 2, możemy rozważyć podział liczby na trzy części o równych długościach.
1. Dla liczby n, dzielimy ją na trzy części o długości n/3.
2. Obliczamy kwadrat każdej z trzech części.
3. Obliczamy iloczyny skrzyżne, czyli a*b, a*c oraz b*c.
4. Kwadrat liczby n to suma kwadratu każdej części, potrójnej sumy iloczynów skrzyżnych oraz dwukrotnej potrójnej sumy wartości każdej części.
### Asymptotyczna złożoność:
Algorytm mnożenia tradycyjnie ma złożoność O(n^2), gdzie n to liczba bitów w reprezentacji liczby. Algorytmy Karatsuby mają złożoność czasową O(n^log₂3), co jest lepsze od zwykłego mnożenia. Jednakże, obliczenie kwadratu liczby za pomocą modyfikowanego algorytmu Karatsuby nie da nam zysku asymptotycznego, ponieważ złożoność kwadratu za pomocą tej metody będzie nadal O(n^log₂3), co jest asymptotycznie równoznaczne z zastosowaniem algorytmu Karatsuby do mnożenia. Oznacza to, że nie uzyskamy tutaj asymptotycznie szybszego algorytmu.
### Zad 4
Żeby połączyć te wielokąty musimy znaleźć styczne.
Wielokąty są dane jako cykliczne dwukierunkowe listy punktów zgodnie z ruchem wskazówek zegara.
Dla wyższej prostej (dla niższej analogicznie):
Zaczynając od punktów najbliżej prostej będziemy sprawdzać czy akutalna prosta przecina któryś z wielokątów, jeśli tak to weźmiemy następny punkt tego wielokąta (dla prawego wielokąta następny leży zgodnie z zegarem, lewy przeciwnie).
Przecinanie wielokąta sprawdzamy:
```
n = punkt.next
if n.y >= prosta(n.x).y
return tak
else
return nie
```
### Zad 5
```
v <- korzeń
while(v is not leaf)
u <- min(v.left, v.right)
if (v < u)
return V
v <- u
return v
```
### Zad 6
### Zad 7
### Zad 8
### Zad 9
## Lista 4
### Zadanie 1
### Zadanie 2
### Zadanie 3
### Zadanie 4
### Zadanie 5
Tylko długość lcs:
```
dp = {0, ...}
prev = 0
for i = 1 .. n
prev = 0
for j = 1 .. m
temp = dp[j]
if x[i] == y[j]
dp[j] = prev + 1
else
dp[j] = max(dp[j-1], dp[j])
prev = temp
return dp[n]
```
Normalny LCS
### Zadanie 6
```python
class Node:
def __init__(self, value):
self.value = value
self.children = []
self.weight = 0
def max_weight_independent_set(root):
if root is None:
return 0, 0
# Obliczamy sumy wag niezależnego podzbioru wierzchołków dla dzieci danego wierzchołka
include_root = root.weight
exclude_root = 0
for child in root.children:
child_include, child_exclude = max_weight_independent_set(child)
include_root += child_exclude
exclude_root += max(child_include, child_exclude)
return include_root, exclude_root
# Przykładowe użycie
if __name__ == "__main__":
# Tworzymy drzewo
root = Node(1)
root.children = [Node(2), Node(3), Node(4)]
root.children[0].children = [Node(5), Node(6)]
root.children[1].children = [Node(7)]
root.children[2].children = [Node(8), Node(9)]
# Przypisujemy wagi do wierzchołków
root.weight = 1
root.children[0].weight = 2
root.children[1].weight = 3
root.children[2].weight = 4
root.children[0].children[0].weight = 5
root.children[0].children[1].weight = 6
root.children[1].children[0].weight = 7
root.children[2].children[0].weight = 8
root.children[2].children[1].weight = 9
# Znajdujemy największą wagę niezależnego podzbioru wierzchołków
include_root, exclude_root = max_weight_independent_set(root)
max_weight = max(include_root, exclude_root)
print("Największa suma wag niezależnego podzbioru wierzchołków:", max_weight)
```
### Zadanie 7
LCS z warstwą na szukanie każdej literki + jedna.
#### Zawiera podciąg "egzamin" :ok:
$T_0$ - najdłuższy wspólny podciąg
$T_1$ - najdłuższy wspólny podciąg zawierający literę e
$$
T_1[i][j] =
\begin{cases}
\max(T_1[i-1][j], T_1[j-1][i]), \ & \text{jeśli } x[i] \neq y[j] \\
T_1[i-1][j-1] + 1, & \text{jeśli } x[i] = y[j] \neq ``e`` & \wedge & T_1[i-1][j-1] > 0 \\
T_1[i-1][j-1], & \text{jeśli } x[i] = y[j] \neq ``e``\\
T_0[i-1][j-1] + 1, & \text{jeśli } x[i] = y[j] = ``e`` \\
\end{cases}
$$
$T_2$ - najdłuższy wspólny podciąg zawierający podciąg "eg"
$$
T_2[i][j] =
\begin{cases}
\max(T_2[i-1][j], T_2[j-1][i]), \ & \text{jeśli } x[i] \neq y[j] \\
T_2[i-1][j-1] + 1, & \text{jeśli } x[i] = y[j] \neq ``g`` & \wedge & T_2[i-1][j-1] > 0 \\
T_2[i-1][j-1], & \text{jeśli } x[i] = y[j] \neq ``g``\\
T_1[i-1][j-1] + 1, & \text{jeśli } x[i] = y[j] = ``g`` & \wedge & T_1[i][j] > 0 \\
0, & wpp
\end{cases}
$$
$T_3$ - najdłuższy wspólny podciąg zawierający podciąg "egz"
$T_7$ - najdłuższy wspólny podciąg zawierający podciąg "egzamin"
Złożoność czasowa: $O(n^2)$
Złożoność pamięciowa: $O(n^2)$
#### Nie zawiera podciągu "egzamin" :ok:
$T_1$ - najdłuższy wspólny podciąg bez litery "e"
$$
T_1[i][j] =
\begin{cases}
\max(T_1[i-1][j], T_1[j-1][i]), \ & \text{jeśli } x[i] \neq y[j] & \vee
& x[i] = y[i] = ``e``\\
T_1[i-1][j-1] + 1, & \text{jeśli } x[i] = y[j] \neq e\\
\end{cases}
$$
$T_2$ - najdłuższy wspólny podciąg bez podciągu "eg"
$$
T_2[i][j] =
\begin{cases}
\max(T_2[i-1][j], T_2[i][j-1]), \ & \text{jeśli } x[i] \neq y[j] \\
T_2[i-1][j-1] + 1, & \text{jeśli } x[i] = y[j] \neq g\\
\max(T_1[i-1][j-1] + 1, T_2[i-1][j-1]), &\text{jeśli } x[i] = y[j] = g
\end{cases}
$$
$T_7$ - najdłuższy wspólny podciąg bez podciągu "egzamin"
Złożoność czasowa: $O(n^2)$
Złożoność pamięciowa: $O(n^2)$
#### Zawiera podsłowo "egzamin" :ok:
$T_0$ - najdłuższy wspólny podciąg
$T_1$ - najdłuższy wspólny podciąg kończący się na literze $e$
$$
T_1[i][j] =
\begin{cases}
T_0[i-1][j-1] + 1, & \text{jeśli } x[i] = y[j] = e \\
\max(T_1[i-1][j], T_1[j-1][i]), \ & \text{wpp. }
\end{cases}
$$
$T_2$ - najdłuższy wspólny podciąg kończący się słowem "eg"
$$
T_2[i][j] =
\begin{cases}
T_1[i-1][j-1] + 1, & \text{jeśli } x[i] = y[j] = g \ \&\& \ T_1[i-1][j-1] > 0 \\
\max(T_2[i-1][j], T_2[j-1][i]), \ & \text{wpp. }
\end{cases}
$$
$T_7$ - najdłuższy wspólny podciąg kończący się słowem "egzamin"
$T_8$ - najdłuższy wspólny podciąg zawierający podsłowo egzamin
$$
T_8[i][j] =
\begin{cases}
\max(T_8[i-1][j-1] + 1, T_7[i][j]), &\text{jeśli } x[i] = y[j]\ \&\&\ (T_8[i-1][j-1]>0 \ || \ T_7[i][j] > 0) \\
\max(T_8[i-1][j], T_8[i][j-1]), \ & \text{wpp. }
\end{cases}
$$
Złożoność czasowa: $O(n^2)$
Złożoność pamięciowa: $O(n^2)$
#### Nie zawiera podsłowa "egzamin"
$T_k$ - lcs nie konczacy sie k-literowym prefiks i nie zawierajacym podslowa S dlugosci s ($T_s$ to wynik).
czy literki sie zgadzaja:
- nie - jak normalny lcs,
- tak, to czy ta literka to:
- s[k], wtedy musimy odwolac sie do poprzedniej warstwy, zeby na pewno nie przedluzyc istniejacego prefiksu do dlugosci k,
- s[s], dbamy tylko o to zeby sie nie konczyc zakazanym k-tym sufiksem wiec potencjalnie mozemy sie konczyc dluzszym, w szczegolnosci s-1 literowym i musimy sie upewnic ze nie stworzymy pelnego slowa biorac wartosc z przedostatniej warstwy,
- wpp bierzemy bez problemu.
$$
T_1[i][j] =
\begin{cases}
\max(T_1[i-1][j], T_1[j-1][i]), \ & \text{jeśli } x[i] \neq y[j] \\
T_1[i-1][j-1], & \text{jeśli } x[i] = y[j] = S[1] \\
max(T_{s-1}[i-1][j-1] +1, T_1[i-1][j-1]), & \text{jeśli } x[i] = y[j] = S[s]\\
T_s[i-1][j-1] + 1, & wpp \\
\end{cases}
$$
$$
T_k[i][j] =
\begin{cases}
\max(T_k[i-1][j], T_k[j-1][i]), \ & \text{jeśli } x[i] \neq y[j] \\
max(T_{k-1}[i-1][j-1]+1, T_k[i-1][j-1]), & \text{jeśli } x[i] = y[j] = S[k] \\
max(T_{s-1}[i-1][j-1] +1, T_k[i-1][j-1]), & \text{jeśli } x[i] = y[j] = S[s]\\
T_s[i-1][j-1] + 1, & wpp \\
\end{cases}
$$
### Zadanie 8
### Zadanie 9
odzyskiwanie rozwiązania
```python
def lengthOfLIS(nums):
# Binary search approach
n = len(nums)
ans = []
# Initialize the answer list with the
# first element of nums
ans.append(nums[0])
for i in range(1, n):
if nums[i] > ans[-1]:
# If the current number is greater
# than the last element of the answer
# list, it means we have found a
# longer increasing subsequence.
# Hence, we append the current number
# to the answer list.
ans.append(nums[i])
else:
# If the current number is not
# greater than the last element of
# the answer list, we perform
# a binary search to find the smallest
# element in the answer list that
# is greater than or equal to the
# current number.
low = 0
high = len(ans) - 1
while low < high:
mid = low + (high - low) // 2
if ans[mid] < nums[i]:
low = mid + 1
else:
high = mid
# We update the element at the
# found position with the current number.
# By doing this, we are maintaining
# a sorted order in the answer list.
ans[low] = nums[i]
# The length of the answer list
# represents the length of the
# longest increasing subsequence.
return len(ans)
# Driver program to test above function
if __name__ == "__main__":
nums = [10, 22, 9, 33, 21, 50, 41, 60]
# Function call
print("Length of LIS is", lengthOfLIS(nums))
```
### Zadanie 10
Mamy dwa odcinki $p_1$ od $(x_1, y_1)$ do $(x_2, y_2)$ oraz $p_2$ od $(x_3, y_1)$ do $(x_4,y_2)$.
$p_1$ i $p_2$ się przecinają wtedy i tylko wtedy $x_1 < x_3$ oraz $x_2 > x_4$ lub $x_1 > x_3$ oraz $x_2 < x_4$.
Zapominamy o konkretnych wartościach $x$
Przykładowo odcinek $(1,6)$
Dane z przykładu:
$(1,6), (2,4), (3,7), (4,1), (5,8), (6,5), (7,2), (8,9), (9,3)$
Rozpatrzmy jakieś rozwiązanie $S$. Posortujmy $S$ względem pierwszej współrzędnej. Wtedy druga współrzędna też jest rosnąca.
$6, 4, 7, 1, 8, 5, 2, 9, 3$
Czyli to jest po prostu najdłuższy rosnący podciąg.
Mamy dany ciąg $\sigma$
Jedna z możliwości: najdłuższy wspólny podciąg $\sigma$ i ciągu $1,2,3,\dots,n$
Czas $O(n^2)$
Przechodzimy po ciągu $\sigma$ i dla każdego elementu liczymy najdłuższy rosnący podciąg kończący się w tym elemencie.
Struktura: dla każdego $i$ trzymamy liczby $\sigma_j$, takie że najdłuższy wspólny podciąg kończący się w $\sigma_j$ ma długość $i$
1: 6, 4, 1
2: 7, 5, 2
3: 8, 3
4: 9
Trzymamy tę strukturę jako tablica list.
#### Lemat
Każda lista w tej strukturze jest malejąca.
```
x - ciąg wejściowy
S - struktura jak wyżej
Dla i = 1 do n:
Znajdź największe j, takie że S[j] zawiera liczbę mniejszą od x[i] (i)
Dodaj x[i] do S[j+1]
```
(i) - wykonujemy za pomocą binary search
Złożoność czasowa: $O(n\log n)$
Złożoność pamięciowa: $O(n)$
#### Liczba najdłuższych rosnących podciągów
Przykład: $6, 4, 7, 1, 8, 5, 2, 9, 3$
1: (6,1), (4,1), (1,1)
2: (7,2), (5,2), (2,1)
3: (8,2), (3,1)
4: (9,2)
$p[i]$ - wskaźnik w $i$-tej liście
$p[i]$ - największy element w $i$-tej liście mniejszy od ostatniego elementu w $i+1$-szej liście
$p[1] = (1,1)$
$p[2] = (2,1)$
$p[3] = (8,2)$
$s[i]$ - liczba rosnących podciągów długości $i$, które się kończą liczbą co najwyżej $p[i]$
```
x - ciąg wejściowy
S - struktura jak wyżej
p[n] - wskaźniki
s[n] - jak wyżej
Dla i = 1 do n:
Znajdź największe j, takie że S[j] zawiera liczbę mniejszą od x[i] (i)
Dopóki p[j][0] > x[i]: (ii)
s[j] -= p[j][1]
p[j] = p[j].next
Dodaj do S[j+1] krotkę (x[i], s[j])
s[j+1] = s[j+1] + s[j]
```
Złożoność pamięciowa: $O(n)$
Złożoność czasowa: $O(n\log n)$
## Lista 5
### Zadanie 1
Rozważmy dlaczego problem znajdowania otoczki wypukłej nie może być skutecznie rozwiązany za pomocą modeli drzew decyzyjnych:
1. **Złożoność problemu**: Problem otoczki wypukłej polega na znajdowaniu najmniejszego wypukłego wielokąta, który zawiera wszystkie punkty z danej zbiorowości punktów w przestrzeni. Jest to zadanie o złożoności obliczeniowej zależnej od liczby punktów wejściowych. W przypadku dużych zbiorów punktów problem staje się bardzo trudny obliczeniowo.
2. **Brak naturalnego podziału**: Modele drzew decyzyjnych operują poprzez tworzenie reguł decyzyjnych na podstawie podziału przestrzeni wejściowej na podzbiory. W przypadku problemu otoczki wypukłej, brak naturalnego podziału przestrzeni punktów uniemożliwia efektywne stworzenie reguł decyzyjnych.
3. **Złożoność geometrii**: Otoczka wypukła zazwyczaj obejmuje krawędzie, które są wyznaczone przez kombinacje różnych punktów wejściowych. Modele drzew decyzyjnych mają trudność z wyznaczeniem takich złożonych relacji geometrycznych.
4. **Skomplikowane warunki graniczne**: Otoczka wypukła może mieć skomplikowane warunki graniczne, które nie są łatwe do uchwycenia za pomocą reguł decyzyjnych. Modele drzew decyzyjnych mogą mieć trudności z odpowiednim uwzględnieniem tych warunków.
5. **Ograniczenia w modelowaniu przestrzeni**: Modele drzew decyzyjnych operują na sposób iteracyjny, dokonując podziałów przestrzeni wejściowej wzdłuż jednego z wymiarów. W przypadku problemu otoczki wypukłej, taka strategia podziału może nie być wystarczająco elastyczna, aby efektywnie modelować złożone kształty geometryczne.
W rezultacie, problem znajdowania otoczki wypukłej jest zbyt złożony i wymaga bardziej zaawansowanych technik, takich jak algorytmy geometryczne, aby być skutecznie rozwiązany. Modele drzew decyzyjnych są bardziej odpowiednie dla problemów, w których przestrzeń wejściowa może być podzielona w sposób klarowny i gdzie relacje między danymi są prostsze do wyrażenia za pomocą reguł decyzyjnych.
### Zadanie 2
Aby udowodnić, że $( n log_n )$ jest dolną granicą na rozwiązanie tego problemu w modelu liniowych drzew decyzyjnych, użyjemy techniki zwaną "dolną granicą informacyjną" lub "dolnym limitem na liniowe drzewa decyzyjne".
1. **Definicja problemu**: Naszym celem jest znalezienie trzech różnych liczb w ciągu, których suma wynosi zero.
2. **Model liniowych drzew decyzyjnych**: W modelu liniowych drzew decyzyjnych, w każdym węźle podejmowana jest decyzja na podstawie jednego zmiennego wejściowego, a następnie przekierowanie do jednego z dwóch poddrzew w zależności od wyniku tej decyzji. Model ten jest wyjątkowo elastyczny, ale koszt działania na każdym poziomie drzewa wynosi co najmniej liniowo względem liczby możliwych decyzji w danym węźle.
3. **Analiza dolnej granicy**: Aby znaleźć dolną granicę, rozważmy liczbę wszystkich możliwych trójek liczb w ciągu $n$ liczb. Jest to $\binom{n}{3}$, co wynosi $\frac{n(n-1)(n-2)}{6}$. Każda taka trójka musi być przetestowana, aby sprawdzić, czy suma wynosi zero. Zatem liczba możliwych wyników testów to co najmniej $\frac{n(n-1)(n-2)}{6}$.
4. **Wyrażenie dolnej granicy**: W modelu liniowych drzew decyzyjnych, każdy test w węźle drzewa może dać co najwyżej jedną jednostkę informacji. W konsekwencji, aby otrzymać co najmniej $\frac{n(n-1)(n-2)}{6}$ wyników testów, drzewo musi mieć co najmniej $\frac{n(n-1)(n-2)}{6}$ liści.
5. **Ograniczenie dolne**: Liczba liści w drzewie o wysokości $h$ wynosi co najwyżej $2^h$. Więc $\frac{n(n-1)(n-2)}{6} \leq 2^h$, gdzie $h$ jest wysokością drzewa decyzyjnego.
6. **Szacowanie wysokości drzewa**: Możemy przyjąć, że drzewo jest zbalansowane, co oznacza, że wysokość drzewa $h$ jest rzędu $\log_2(m)$, gdzie $m$ to liczba liści w drzewie. W tym przypadku $m \geq \frac{n(n-1)(n-2)}{6}$, więc $h \geq \log_2\left(\frac{n(n-1)(n-2)}{6}\right)$.
7. **Wnioski**: Zatem, $h$ jest co najmniej rzędu $\log(n^3)$, co wynosi $3\log n$. Stąd wynika, że dolną granicą czasową w modelu liniowych drzew decyzyjnych dla tego problemu jest $\Omega(n \log n)$.
To dowodzi, że $n \log n$ jest dolną granicą na rozwiązanie tego problemu w modelu liniowych drzew decyzyjnych.
### Zadanie 3
1. Posortuj ciąg liczb rosnąco.
2. Dla każdej liczby `A` w ciągu, wykonaj pętlę dwóch wskaźników:
- Ustaw wskaźnik `lewy` na indeksie `i + 1` (następnej liczby po `A`).
- Ustaw wskaźnik `prawy` na ostatnim indeksie.
- Dopóki `lewy` jest mniejszy niż `prawy`:
- Oblicz sumę `suma = A + ciąg[lewy] + ciąg[prawy]`.
- Jeśli `suma` jest równa zero, zwróć `true`.
- Jeśli `suma` jest mniejsza niż zero, zwiększ `lewy`.
- Jeśli `suma` jest większa niż zero, zmniejsz `prawy`.
3. Jeśli nie znaleziono żadnej trójki spełniającej warunek, zwróć `false`.
Złożoność czasowa tego algorytmu zależy głównie od sortowania oraz od pętli wewnętrznej:
- Sortowanie: Zwykle sortowanie ma złożoność czasową O(n log n).
- Pętla dwóch wskaźników: Przechodzi przez każdą kombinację par liczb, co daje złożoność czasową O(n^2).
Całkowita złożoność czasowa tego algorytmu wynosi więc O(n^2), gdzie n to liczba elementów w ciągu liczb.
### Zadanie 4
### Zadanie 5
### Zadanie 6
### Zadanie 7
### Zadanie 8
### Zadanie 9
[link](https://drive.google.com/file/d/1MBJm_YKy3_KH3A4GXh-KEvBt-x7jZffa/view)
## Lista 6
### Zadanie 1
### Zadanie 7
### Zadanie 8
### Zadanie 9
### Zadanie 10
## Lista 7
### Zadanie 1
### Zadanie 2
### Zadanie 3
### Zadanie 4
### Zadanie 5
## 2025 Lista 3
### Zadanie 2
Nierówność Markova
wartość oczekiwana
Google Drive
Gist
Clipboard
Sign in with Wallet
