05.03.2024: Klasyczny komputer

1. Nierozstrzygalność problemu STOP'u
2. Nierozstrzygalność problemu ZERO = $\{n\in\NN: p_n \equiv 0\}$
3. Nierozstrzygalność problemu EQ_g = $\{n\in\NN: (\forall k)(p_[n]\downarrow \land p_n[k] = g(k))\}$
4. Twierdzenie Godla o niezupełności arytmetyki Peano

12.03.2024: Klasyczny komputer: ciągi skończone I

1. Porządek $\preceq_{lex}$ na alfabecie $\{a,b\}$ ($a\preceq b$) nie jest dobrym porządkiem.
2. Porządek podciągowy: dla $x = (x_1,\ldots,x_k)$ oraz $y = (y_1,\ldots,y_m)$ określamy $x\preceq y$ jeśli istnieje ciąg $1\leq i_1 \lt i_2 \lt \ldots \lt i_k \leq m$ taki, że $$x_1 = y_{i_1} \land x_2 = y_{i_2} \land \ldots \land x_k = y_{i_k}$$
3. Częściowy porządek $(\Sigma^*,\prec)$ jest ufundowany, czyli nie istnieje nieskończony ciąg $(x_n)_n$ taki, że $$x_0 \gt x_1 \gt x_2 \gt \ldots$$
4. Lemat Dickson'a: Załóżmy, że $|\Sigma| \lt \infty$. Niech $(\sigma_n)_n$ będzie dowolnym nieskończonym ciągiem elementów zbioru $\Sigma^*$. Istnieją wtedy $i \lt j$ takie, że $\sigma_i \preceq \sigma_j$.
5. Wniosek. Załóżmy, że $|\Sigma| \lt \infty$ oraz, że $A\subseteq \Sigma^*$. Wtedy zbiór elementów minimalnych zbioru $A$ jest skończony.
6. Wniosek:Załóżmy, że $|\Sigma| \lt \infty$ oraz $A \subseteq \Sigma^*$. Niech $$up(A) = \{\eta\in\Sigma^*: (\exists \sigma \in A)(\sigma \preceq \eta)\}$$. Wtedy zbiór $up(A)$ jest językiem regularnym.
7. Def: $lcs(x,y) = \max\{a\in\Sigma^*: a \preceq x \land a \preceq y\}$
8. Ustalamy $n,k$. Rozważamy alfabet $\Sigma = \{1,\ldots,k\}$. Zbiór $\Sigma^n \times \Sigma^n$ traktujemy jako przestrzeń probabilistyczną z miarą dyskretną $P((x,y)) = k^{-2 n}$. Niech $L_{n,k}(x,y) = lcs(x,y)$
   1. Fakt: $\EE{L_{n+m,k}} \geq \EE{L_{n,k}} + \EE{L_{m,k}}$
   2. Lemat Fekete Jeśli $(a_n)_n$ jest podaddytywny ($(\forall n,m)(a_{n+m} \leq a_n + a_m)$), to ciąg $(\frac{a_n}{n})_{n\geq 1}$ jest zbieżmy oraz $$ \lim_n\frac{a_n}{n} = \inf_n \frac{a_n}{n}$$ Uwaga: na razie tego nie udowodniliśmy.
   3. Wniosek: Ciąg $\lim_n \frac{\lambda_{n,k}}{n}$ jest zbieżny, gdzie $\lambda_{n,k} = \EE{L_{n,k}}$.
   4. Def. (stała Chvatal'a-Sankov'a) $\gamma_k = \lim_n\frac{\lambda_{n,k}}{n}$
   5. Co wiadomo: $\gamma_2 \approx 0.788$, $\gamma_4 \approx 0.59$

19.03.2024: Klasyczny komputer: ciągi skończone II

1. Uogólnienie problemu LCS: sequence alignment problem
2. Porządek podłańcuchowy $x \sqsubseteq y \IFF (\exists u,v)(y = u \| x \| v)$.
3. "Pattern matching problem"
4. Algorytm prefiksowy rozpoznawania zgodności ze wzorcem
5. Szczególny przypadek algorytmu Rabina-Karpa dla alfabetu $\Sigma=\{A,C,G,T\}$ i ciągów długości $3$.

import Data.List

longestPrePost :: Eq a => [a] -> [a] -> Int
longestPrePost x y = length $ last $ intersect (inits x) (tails y)
  
buildList :: Eq a => [a] ->[([a],a)]  
buildList pattern = [(p,c) | p <- inits pattern, c <- nub pattern]

transf :: Eq a => [a]->[a]->a->(Int,a,Int)
transf pattern p c = (length p, c, longestPrePost pattern (p++[c]))

-- budowa automatu prefiksowego 
buildPA :: Eq a => [a] -> [(Int,a,Int)]
buildPA pattern = map (\(p,c)->transf pattern p c) (buildList pattern) 
             
main = do
  putStrLn "Podaj łańcuch"
  pattern <- getLine
  putStrLn $ show $ buildPA pattern