Beugró kérdések

Számelmélet

1. Mondja ki a maradékos osztás tételét! Ossza el maradékosan $18$-at $7$-tel!

Tetszőleges $a$, $b \neq 0$ egész számokhoz egyértelműen léteznek $q$, $r$ egészek, hogy $a = bq + r$ és $0 \leq r < |b|$.

$18 \bmod 7 = 4$

Itt $q=2$, $r=4$, így $18=7\cdot2+4$

2. Definiálja a legnagyobb közös osztót! Mi lesz $(12, 18)$ ?

Legyenek $a, b \in\Z$. Ekkor $d\in\Z^+$ az $a$ és $b$ legnagyobb közös osztója, ha:

$d \mid a$ és $d \mid b$;
$\forall k\in\Z:\; k \mid a,\;k \mid b\implies k \mid d$.

Jelölése: $d = (a, b) = \text{lnko}(a, b) = \gcd(a, b)$

\[ (0, 0) := 0 \]

$(12, 18) = 6$

3. Mondja ki a lineáris diofantikus egyenletek megoldhatóságáról szóló tételt! Megoldható-e a $12x + 18y = 5$ egyenlet? Ha igen, adjon megoldást, ha nem, indokoljon!

Minden $a$, $b$, $c$ egész számok esetén pontosan akkor léteznek $x$, $y$ egészek, hogy

$x \cdot a + y \cdot b = c$, ha $(a, b) | c$

$(a, b)=(12, 18)=6$

$6 \nmid 5$, tehát ennek a diofantikus egyenletnek nincs megoldása

Ugyanakkor

$12x + 18y = 12$ esetén

$a=12$

$b=18$

$c=12$

$a$ és $b$ bővített euklidészi algoritmusából: $12 \cdot -1 + 18 \cdot 1 = 6$

$x_0' = -1$

$y_0' = 1$

$x_0 = \frac{c}{(a, b)}\cdot x_0' = \frac{12}{6}\cdot-1 = -2$

$y_0 = \frac{c}{(a, b)}\cdot y_0' = \frac{12}{6}\cdot1 = 2$

Ezek alapján:

$x_t = x_0 + \frac{b}{(a, b)}\cdot t = -2+\frac{18}{6}\cdot t=3t-2$

$y_t = y_0 - \frac{a}{(a, b)}\cdot t = 2-\frac{12}{6}\cdot t=2t-2$

4. Definiálja a prímszámokat! Az alábbi számok közül melyek prímek: $1,2,3,4,5,6$?

Egy $p \neq 0,\pm1$ szám prímszám, ha $p = a \cdot b \implies p = \pm a$ vagy $p = \pm b$

Prímszámok: $2, 3, 5$

5. Mondja ki a számelmélet alaptételét! Írja fel az $n = 18$-at a tétel szerint!

Minden $n \neq 0, \pm 1$ egész szám sorrendtől és előjeltől eltekintve egyértelműen felírható prímszámok szorzataként:

\[ n = \pm p_1^{\alpha_1} \cdot p_2^{\alpha_2} \dots p_{\ell}^{\alpha_\ell} = \pm\,\underset{i=1}{\overset{\ell}{\Large{\Pi}}}\;p_i^{\alpha i} \]

ahol $p_1$, $p_2$, ..., $p_{\ell}$ pozitív prímek, $\alpha_1$, $\alpha_2$, ..., $\alpha_\ell$ pozitív egészek.

(Magyarul minden egész szám ami nem nulla, kifejezhető prímszámok hatványainak szorzataként.)

$18 = +2^1\cdot3^2$

6. Definiálja a kongruencia relációt! Mondjon példát két különböző $x$ egészre, mely teljesíti az $x \equiv 3 \mod 4$ relációt!

Adott $n \ne 0$ és $a, b$ egészek esetén, akkor mondhatjuk, hogy $a$ kongruens $b$-vel modulo $n$, ha

\[ a \equiv b \mod n \text{, ha } n \mid a-b \]

$x \equiv 3 \mod 4 \iff 4 \mid x-3 \Longleftarrow x=3 \lor x = 7$

7. Mondja ki a lineáris kongruenciák megoldhatóságára vonatkozó tételt! Megoldható-e a $12x \equiv 2 \mod 10$ lineáris kongruencia? Ha igen, adja meg az összes megoldást, ha nem, indokoljon!

Legyenek $a$, $b$, $n$ egesz számok, $n > 1$. Ekkor az $ax \equiv b \mod n$ megoldható $\iff (a, n)\;|\; b$. Ez esetben pontosan $(a, n)$ darab inkongruens megoldas van mod $n$.

$(12, 10)\;|\; 2\quad$ igaz

$12 \cdot 1 + 10 \cdot (-1) = 2$

$a = 12$

$b = 2$

$n = 10$

$x = 1$, a Bővített Euklidészi Algoritmus szerint

$x_k = \frac{b}{(a, n)} \cdot x + k \frac{n}{(a, n)} = \frac{2}{(12, 10)}\cdot1 + k \cdot \frac{10}{(12, 10)} = 1 + 5k \quad \left(k \in [0, (a, n)-1] = [0, 1]\right)$

8. Mondja ki a kinai maradéktételt! Megoldható-e az $\begin{drcases} x \equiv 1 \mod 2 \\ x \equiv 2 \mod 3 \quad\end{drcases}$ szimultán kongruenciarendszer? Ha igen, adja meg az összes megoldást, ha nem, indokoljon!

Legenek $1 < n_1, n_2, \dots, n_k$ páronként relatív prím számok, $c_1, c_2, \dots, c_k$ egészek.

Ekkor a

\[ \begin{drcases}x \equiv c_1 \bmod n_1\\ x \equiv c_2 \bmod n_2 \\ x \equiv c_k \bmod n_k \end{drcases} \]

kongruencia rendszer megoldható, és bármely két megoldás kongruens egymással modulo $n_1 \cdot n_2 \dots n_k$

$\begin{drcases} x \equiv 1 \mod 2 \\ x \equiv 2 \mod 3 \end{drcases}$

Bővített euklidészi algoritmus 2-re és 3-ra:

$n_1x_1 + n_2x_2 = 1$

$2 \cdot (-1) + 3 \cdot (1) = 1$

$c_{1,2} = n_1x_1c_2 + n_2x_2c_1$

$c_{1,2} = 2\cdot(-1)\cdot2 + 3\cdot1\cdot1 = 3-4=-1 \mod n_1n_2=6$

$x \equiv 5 \mod 6$

9. Definiálja az Euler-féle $\varphi$ függvényt! Mi lesz $\varphi(6)$?

Df.: $n \in \N^{+},\, n > 1$ kanonikus alak:

$n = p_1^{\alpha_1}, p_2^{\alpha_2} \dots p_{k}^{\alpha_k}$ , ahol $p_i$ páronként különböző prímek, és $\alpha \in \Z^+ , \, (1 \le i \le k)$

$\varphi(n) = \#\{ 1 \le a \le n \; | \; lnko (n,a) = 1 \}$

$\varphi(6) = \#\{ 1, 5 \} = 2$

10. Mondja ki az Euler–Fermat-tételt! Mi lesz $3^4 \equiv \;? \mod 8$. Válaszát indokolja!

Legyenek $a, n \in \Z, (a, n) = 1$ Ekkor

\[ a^{\varphi(n)} \equiv 1 \bmod n \]

ahol $\varphi$ az Euler-féle függvény.

$\varphi(8)=4$

$\forall a \in \Z: (a, 8)=1 \implies a^4\equiv1 \mod 8$

Mivel $3 \in \Z$ és $(3,8)=1$, ezért $3^4\equiv1 \bmod 8$

$? = 1$

Polinomok

1. Definiálja a polinomok fokát! Mennyi lesz $\deg(x^3 + x − 1) =?$

$f=c_nx^n+\cdots+c_0\quad (c_n,\ldots,c_0\in\mathbb{K},\;c_n\ne0)$

Ekkor $\deg f:=n$

\[ \deg(x^3 + x − 1) = 3 \]

2. Definiálja a maradékos osztást polinomok körében! Ossza el maradékosan az $f:=x^3+3x+1\in\mathbb{Q}[x]$ polinomot a $g=x+1\in\mathbb{Q}[x]$ polinommal!

Legyen $\mathbb{K} \in \{ \mathbb{C}, \R, \mathbb{Q}, \Z_{p} \}$ és $f, g \in \mathbb{K}[x], g \neq 0$ Ekkor léteznek olyan $q, r \in \mathbb{K}[x]$ polinomok, hogy

\[ f = q \cdot g + r \quad\quad \deg r < \deg g \]

\[\begin{align*} & x^3+3x+1:x+1=\overbrace{x^2-x+4}^{q} \\ & -(x^3+x^2) \\ & -x^2+3x+1 \\ & -(-x^2-x) \\ & 4x + 1 \\ & -(4x+4) \\ & \underbrace{-3}_{r} \end{align*}\]

3. Mondja ki a gyöktényező kiemelhetőségére vonatkozó tételt! Mondjon példát két olyan $g$ polinomra, melynek gyöke az $x=1$ és $x=2$ érték!

Legyen $\mathbb{K\in\{C,R,Q,Z_p\},\;f\in \mathbb{K}[x],\;x_1\in \mathbb{K}}$

Ekkor $f$ felírható az $f=(x-x_1)\cdot g\quad(g\in \mathbb{K}[x])$

$f(x)=(x-1)(x-2)=x^2-2x-x+2=x^2-3x+2$

$g(x)=(x-1)(x-2)(x-3)=(x^2-3x+2)(x-3)=x^3-3x^2+2x-(3x^2-9x+6)=x^3-3x^2+2x-3x^2+9x-6=x^3-6x^2+11x-6$

4. Mondja ki a polinom foka és gyökeinek száma közötti összefüggést! Hány gyöke lehet az $f=x^5+x+1\in\mathbb{Q}[x]$ polinomnak?

$f\in\mathbb{K}[x]$ polinomnak legfeljebb $\deg f$ gyöke lehet $(\mathbb{K}\in\{\mathbb{C,R,Q,Z_p}\})$

$\large{Viszont\;\Z_x\not\in\Z_{p}}$ felett nem igaz

$deg (x^5+x+1)=5 \implies$ 5 gyöke lehet

5. Definiálja polinomok legnagyobb közös osztóját! Mi lesz az $f=(x−1)(x+1)\in\mathbb{Q}[x]$ és $g=x(x−1)^2(x+1)^2\in\mathbb{Q}[x]$ polinomok legnagyobb közös osztója?

Két polinom $f$ és $g$ legynagyobb közös osztója, $h = (f, g) = lnko(f,g)$ , ha - közös osztó: $h | f$ és $h |g$ ; - legynagyobb : ha $q\mid f~\text{és}\;q\mid g \implies q\mid h$ - $h$ föegyütthatója 1.

\[ lnko(f,g) = (x-1)(x+1)=x^2-1 \]

6. Definiálja a formális deriváltat! Mi lesz az $f=x^2+x+1\in\Z^2[x]$ polinom formális deriváltja? Polinomokra definiáljuk a $f'$ formális deriváltat a következő módon: - $(x^n)' = n*x^{n-1}$ - $(c*f)' = c * f'$ - $(f + g)' = f' + g'$

$f = x^2+x+1$

$f'= 1$ (ügyeljünk a használt számhalmazra!)

7. Definiálja az irreducibilis polinom fogalmát! Irreducibilis lesz-e az $f = (x + 1)(x + 2) \in R[x]$ polinom?

Egy $f$ polinom irreducibilis, ha nem bontható szorzatra nem-triviális módon, azaz $$ f = g * h \implies \deg g = \deg f \; \text{vagy} \; \deg h = \deg f $$

$f$ irreducibilis $g = (x+1) \,$

8. Definiálja a kongruencia relációt polinomok körében! Mondjon példát két különböző $g \in\Z^2[x]$ polinomra, mely teljesíti a $g\equiv x+1\mod x^2+x+1$ relációt!

$\mathbb{K\in\{C,\;R,\;Q,\;Z_p\},\;h\in K[x]}$ nem nulla polinom.

Ekkor $f,g\in\mathbb{K}[x]:$

\[ h\mid f-g\;\implies\;f\equiv g \mod h \]

$g\equiv x+1\mod x^2+x+1$

$h|(x-1)-(x^2+x+1):$

\[ g=(x^2+x+1)k + (x+1)\quad (k\in\Z) \]

\[ f_1=(x^2+x+1)k + (x+1)\underset{\big|k=2}{}=2x^2+3x+3 \]

\[ f_2=(x^2+x+1)k + (x+1)\underset{\big|k=3}{}=3x^2+4x+4 \]

9. Mondja ki a Lagrange interpolációról szóló tételt! Hány olyan legfeljebb harmadfokú polinom van, mely a $3$ helyen a $2$-t, az $1$ helyen a $0$-t, a $6$ helyen a $−9$-t és a $0$ helyen a $−1$-t veszi fel?

Legyen

\[ L_i=\underset{j\ne i}{\underset{j=0}{\overset{n}{\prod}}}\dfrac{x-x_i}{x_j-x_i} \qquad f=\underset{j=1}{\overset{n}{\sum}}y_iL_i \]

Legyenek $x_0,x_1,\ldots,x_n\in \mathbb{C}$ páronként különböző alappontok és $y_0,y_1,\ldots,y_n\in\mathbb{C}$ tetszőleges értékek.

$n\in\N^+:\exists!f\in\mathbb{C}[x]:\; \deg f< n\,;\;f(x_i)=y_i$

Legyen $P_n$ a legfeljebb $n$-edfokú polinomok osztálya

A Lagrange-féle interpolációs feladatnak pontosan egy megoldása van $P_n$-ben

1 létezik.

Kódelmélet

1. Definiálja a betűnkénti kódolás fogalmát! Betűnkénti kódolás lesz-e a $\varphi(a)=01,\;\varphi(b)=11,\;\varphi(c)=01$ függvény?

Df.: Legyen $\mathcal{X} = \{x_1, x_2, \dots , x_n \}$ halmaz a forrásábécé és $\mathcal{Y} = \{ y_1, y_2, \dots , y_k \}$ a kódábécé. Ekkor egy $\varphi : \mathcal{X} \rightarrow \mathcal{Y}^*$ injektív függvényt kódolásnak (vagy betűnkénti kódolásnak) hívunk.

Itt $\mathcal{Y}^*$ az $\mathcal{Y}$ elmeiből álló véges szavak halmaza.

A $\varphi$ függvényt kiterjesztjük a $\mathcal{X}^*$ halmazra betűnként:

$\varphi ( u_1, u_2, \dots , u_r ) = \varphi ( u_1 ), \varphi (u_2), \dots , \varphi (u_r)$

Nem, hiszen a $\varphi$ nem injektiv, hiszen $\varphi(a)=\varphi(c)$

2. Definiálja a felbontható kódolás fogalmát! Felbontható kódolás lesz-e a $\varphi(a)=01,\;\varphi(b)=11,\;\varphi(c)=10$ függvény?

Df.: Legyen $\varphi : \mathcal{X} \mapsto \mathcal{Y}^*$ kódolás felbontható (vagy egyértelműen dekódolható), ha

$u, v \in \mathcal{X}^*, \, u = u_1u_2 \dots u_r, \, v = v_1v_2 \dots v_s$ esetén, ha $u \neq v$, akkor

\[ \varphi (u_1) \varphi(u_2) \dots \varphi(u_r) \neq \varphi(v_1) \varphi(v_2) \dots \varphi(v_s) \]

Felbontható, hiszen egyenletes kód.

Egyenletes kód

$\varphi$ minden kódolásának hossza megegyezik (jelen esetben 2)

3. Definiálja a prefix kódok fogalmát! Adjon meg az $\{a, b, c\}$ forrásábécén egy prefix kódolását!

Note

Egy $u = abc$ szó esetén:

$u$ prefixei: $a, ab, abc$;
$u$ infixei: $b, ab, bc, abc$;
$u$ szuffixei: $c, bc, abc$.

Df.: Egy $\varphi$ kódolás prefix kód (vagy prefixmentes kód), ha nem léteznek olyan $u,v$ különböző kódszavak, hogy $u$ prefixe $v$-nek.

$\mathcal Y = \{0, 1\}$

$\varphi(a) = 00$

$\varphi(b) = 01$

$\varphi(c) = 1$

4. Definiálja a kódfa fogalmát! Rajzolja fel a $\{100,\;101,\;11,\;000\}$ kód kódfáját!

Egy $\varphi$ kódfája egy olyan fa, melynek csúcsai a (kódszavak és azok prefixei) és az ($y_1 y_2 \dots y_s$ és $y_1 y_2 \dots y_s y_{s+1}$) csúcsok vannak összekötve.

Gráf

5. Definiálja a Hamming-távolságot! Mennyi lesz $d(010, 110) =?, d(0000, 0009) =?$

($\sum$ egy ábécé, $\sum ^n$ az n hosszú karaktersorok halmaza)

Df.: Legyen $u,v \in \sum ^n$ két szó. A szavak Hamming-távolsága: $d(u,v) = \# \{i: u_i \neq v_i \}$

Magyarázó:

Df.: Legyen $\sum$ egy véges halmaz (ábécé) és tekintsük az $n$ hosszú szavak halamzát $\sum^n$. Ekkor a $C \subset \sum^n$ részhalmaz egy kód, elmei a kódszavak.

$F_2$

Tipikusan $\sum = \mathbb{F}_2$ vagy általában $\mathbb{F}_{2^k}$

(itt $\mathbb F_q$ a véges terek ($GF(q)$)) (Tereknél pedig, hogy az osztás definiálható legyen, ahhoz az alapnak valamilyen prím hatványnak kell lennie)

2 meg prím, úgyhogy az azért jó

$d(010, 110)=\#\{1\}=1$

$d(0000, 0009)=\#\{4\}=1$

6. Mondja ki a kód kódtávolsága és a hibajelző, hibajavító képesség közötti összefüggést! Hány hibát jelez ill. javít a $C$ kód, ha $d(C) = 8$?

d függvény kiterjesztése halmazra

$d(\mathcal C) = \min\{d(u, v):q, v \in \mathcal C, u \ne v\}$

Tehát két helyes kódolás közötti legkisebb Hamming-távolság

$d$ akkor minden szóra lehívja $d$-t és abból a legkissebbet veszi.

Egy $\mathcal{C}$ kód $d = d(\mathcal{C})$ kódtávolsággal: - $d - 1$ hibát tud jelezni; - $t = \lfloor (d-1) / 2 \rfloor$ hibát tud javítani

Magyarázat

Ha a paritásbites megoldást nézzük, akkor egy hibára jelezni fog a rendszer, de nem tudja megmondani, hogy hol van.

Egyéb példa: ismétlő kódolás (d=3)

0110 -> 000 111 111 000

Ha feltételezzük, hogy $d-1=2$-nél nem több hiba (bitflip) fordult elő a stringben, akkor észlelni lehet, hogy hiba történt. pl

000 111 010 000 - hiba történt, láthatóan a harmadik részben, de nem egyértelmű, hogy mi lehetett az eredeti

Ha feltételezzük, hogy $\lfloor\frac{d-1}{2}\rfloor=1$-nél nem több hiba fordult elő a stringben, akkor a hibát javítani is lehet. pl

000 111 011 000 - kijavítható az eredeti stringre

7. Definiálja a lineáris kódok fogalmát! Lineáris lesz-e a $\mathcal C=\{110, 101, 111\}\subset\Z^3_2$ kód?

Egy $\mathcal{C} \subset \mathbb{F}^n_q$ kód lineáris, ha $\mathcal{C}$ egy lineáris altér $\mathbb{F}^n_q$ -ben. Ekkor $k = \dim \mathcal{C}$ a kód dimenziója. Spec. $\# \mathcal{C} = q^k$. Ekkor $\mathcal{C}$ egy $(n, k)$ kód.

Lineáris kódok

Példa:

$\green{(0, 0, 1)}, \blue{(0, 1, 0)}, \orange{(0, 1, 1)}$

ezek lineáris kombinációi lineáris alteret alkotnak:

$\{(0, 0, 0), (0, 1, 0), (0, 0, 1), (0, 1, 1)\} = \mathcal C$

$k=\dim (\mathcal C) = 2$, hiszen $\dim \begin{bmatrix} \blue0 & \green0 & \orange0 \\ \blue0 & \green1 & \orange1 \\ \blue1 & \green0 & \orange1 \end{bmatrix} = 2$

$\#C = q^k$

Ekkor $\mathcal C$-t egy $(n, k)$ kódnak nevezzük

Mivel $000 \notin \mathcal C$, ezért nem lehetséges, hogy $\mathcal C$ lineáris altér legyen, tehát nem lineáris kód.

8. Definiálja lineáris kódok generátormátrixát! Mi lesz a $(b_1, b_2)\mapsto(b_1,\;b_2,\;b_1+b_2)$ bináris lineáris kód generátormátrixa?

Df.: Legyen $\mathcal{C}$ egy lineáris $(n,k)$ kód $c_1, \dots, c_k$ generátorokkal. Ekkor a $\mathcal{C}$ egy generátormátrixa $G = (c_1,\dots,c_k) \in \mathbb{F}^{n \times k}_q$.

Ez egy szisztematikus kódolás

$G = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \\ \end{bmatrix}\cdot [b_1,\;b_2]^T = [b_1,\;b_2,\;b_1+b_2]^T$

9. Definiálja lineáris kódok ellenőrzőmátrixát! Mi lesz a $(b_1, b_2)\mapsto(b_1,\;b_2,\;b_1+b_2)$ bináris lineáris kód ellenőrző mátrixa?

Df.: Legyen $\mathcal{C}$ egy $(n,k)$ kód. Ekkor $\mathcal{C}$ ellenőrző mátrixa az a $H \in \mathbb{F}^{(n-k) \times n}_q$ mátrix, melyre $Hc = 0$ pontosan akkor, ha $c \in \mathcal{C}$.

$\begin{bmatrix} q-1 & q-1 & 1 \\ \end{bmatrix}\cdot\begin{bmatrix} b_1 \\ b_2 \\ b_1+b_2 \end{bmatrix}= \bold{0} \left(=\begin{bmatrix} 0 \\ \end{bmatrix}\right)$

Példa más számokkal

$k:=2 = \dim\mathcal{C}$

$n:= 4$

$M=\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 1 & 1 \\ 1 & 0 \\ \end{bmatrix}$

\[ \left\{(1,1,1,1), (1,0,1,0), (0,0,0,0), (0,1,0,1)\right\}\subset \Z_2^4 \]

$E_\text{llenőrző mátrix}= \begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix}$

$\begin{matrix} & \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 1& 1 \\ 1 & 0 \end{bmatrix} \\ \begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix} & \begin{bmatrix} 0 & 0 \\ 0 & 0 \\ \end{bmatrix} \mathclap{~~~~~~~=0}\\\end{matrix}$

$\dim E = n-k = 4-2=2$

Az ellenőrző mátrix dimenziója $n-k$ kell(!), hogy legyen. A generátor mátrix és az ellenőrző mátrix szorzata nullmátrix kell legyen. (valamint minden vektorral nullmátrixot kell adjon)