Beugró kérdések - Simplified
Számelmélet
1. Mondja ki a maradékos osztás tételét!
\(\Z \ni a\), \(b \neq 0:\;\exists!\,q, r\in\Z\)
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)\)
Továbbá: \((0, 0) := 0\)
3. Mondja ki a lineáris diofantikus egyenletek megoldhatóságáról szóló tételt!
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\)
4. Definiálja a prímszámokat!
Egy \(p \in \Z \; \land \; p \notin \{-1, 0, 1\}\) szám prímszám, ha:
\(p = a \cdot b \implies p = \pm\,a~~\) vagy \(~~p = \pm\,b\)
5. Mondja ki a számelmélet alaptételét!
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:
ahol \(p_1\), \(p_2\), ..., \(p_{\ell}\) pozitív prímek, \(\alpha_1\), \(\alpha_2\), ..., \(\alpha_\ell\) pozitív egészek.
6. Definiálja a kongruencia relációt!
Adott \(n \ne 0\) és \(a, b\) egészek esetén (mondhatjuk, hogy \(a\) kongruens \(b\)-vel modulo \(n\))
7. Mondja ki a lineáris kongruenciák megoldhatóságára vonatkozó tételt!
Legyenek \(a\), \(b\), \(n\) egész 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\).
8. Mondja ki a kinai maradéktételt!
Legyenek \(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
kongruencia rendszer megoldható, és bármely két megoldás kongruens egymással modulo \(n_1 \cdot n_2 \dots n_k\)
9. Definiálja az Euler-féle \(\varphi\) függvényt!
Df.: \(n \in \N^{+},\, n > 1\) kanonikus alak:
\(\varphi(n) = \#\{ 1 \le a \le n \; | \; lnko (n,a) = 1 \}\)
10. Mondja ki az Euler–Fermat-tételt!
Legyenek \(a, n \in \Z, (a, n) = 1\) Ekkor
ahol \(\varphi\) az Euler-féle függvény.
Polinomok
\(\mathbb{K}\) my beloved
\(\mathbb{K}\in\{\mathbb{C},\;\R,\;\mathbb{Q},\;\Z,\;\Z_p\}\)
1. Definiálja a polinomok fokát!
\(f=c_nx^n+\cdots+c_0\quad (c_n,\ldots,c_0\in\mathbb{K},\;c_n\ne0)\)
Ekkor \(\deg f:=n\)
2. Definiálja a maradékos osztást polinomok körében!
Legyen \(f, g \in \mathbb{K}[x], g \neq 0\) Ekkor léteznek olyan \(q, r \in \mathbb{K}[x]\) polinomok, hogy
3. Mondja ki a gyöktényező kiemelhetőségére vonatkozó tételt!
Legyen \(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])\)
4. Mondja ki a polinom foka és gyökeinek száma közötti összefüggést!
\(f\in\mathbb{K}[x]\) polinomnak legfeljebb \(\deg f\) gyöke lehet
\(\large{Viszont\;\Z_x\not\in\Z_{p}}\) felett nem igaz
5. Definiálja polinomok legnagyobb közös osztóját!
Két polinom \(f\) és \(g\) legynagyobb közös osztója, \(h = (f, g) = lnko(f,g)\) , ha
- közös osztó: \(h \mid f \land h \mid g\) ;
- legynagyobb : \(\forall q\in\mathbb{K}[x]:\; q\mid f~\land\;q\mid g \implies q\mid h\)
- \(h\) föegyütthatója 1.
6. Definiálja a formális deriváltat! 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'\)
7. Definiálja az irreducibilis polinom fogalmát!
Egy \(f\) polinom irreducibilis, ha nem bontható szorzatra nem-triviális módon, azaz
8. Definiálja a kongruencia relációt polinomok körében!
\(h\in K[x]\) nem nulla polinom.
Ekkor \(f,g\in\mathbb{K}[x]:\)
9. Mondja ki a Lagrange interpolációról szóló tételt!
Legyen
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\)
- Ekkor egyértelműen létezik olyan \(f\) polinom, hogy \(\deg f\le n\) és \(f(x_i)=y_i\)
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
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.
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}\)
\(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)