Dimat 2 beugró kérdések és válaszok

Számelmélet

  1. Mondja ki a maradékos osztás tételét! Ossza el maradékosan 1818-at 77-tel!
  • Tetszőleges a,b≠0a, b \neq 0 egész számokhoz egyértelműen léteznek q,rq, r egészek, hogy a=bq+ra = bq + r és 0≤r<∣b∣0 \leq r < |b|
  • a=18,b=7a = 18, b = 7 esetén 18=2⋅7+418 = 2 \cdot 7 + 4, vagyis q=2,r=4q = 2, r = 4
  1. Definiálja a legnagyobb közös osztót! Mi lesz (12,18)(12, 18)?
  • Legyenek a,b∈Za, b \in \Z. A dd nemnegatív egész szám az aa és bb legnagyobb közös osztója, ha
    1. d∣ad \mid a és d∣bd \mid b;
    2. minden k∈Zk \in \Z esetén, ha k∣ak \mid a, k∣bk \mid b, akkor k∣dk \mid d.
  • Jelölése: d=(a,b)=lnko(a,b)=gcd⁡(a,b)d = (a, b) = \text{lnko}(a, b) = \gcd(a, b). Definíció szerint (0,0)=0(0, 0) = 0.
  • (Minden a,b∈Za, b \in \Z esetén létezik (a,b)(a, b) legnagyobb közös osztó.)
  • (12,18)=6(12, 18) = 6
  1. Mondja ki a lineáris diofantikus egyenletek megoldhatóságáról szóló tételt! Megoldható-e a 12x+18y=512x + 18y = 5 egyenlet? Ha igen, adjon megoldást, ha nem, indokoljon!
  • Minden a,b,ca, b, c egész számok esetén pontosan akkor léteznek x,yx, y egészek, hogy x⋅a+y⋅b=cx \cdot a + y \cdot b = c, ha (a,b)∣c(a, b) \mid c
  • 12x+18y=512x + 18y = 5 esetén a=12,b=18,c=5a = 12, b = 18, c = 5. Mivel (12,8)=4(12, 8) = 4 és 4∤54 \nmid 5, ezért nincs ilyen xx és yy, és az egyenlet nem megoldható.
  1. Definiálja a prímszámokat! Az alábbi számok közül melyek prímek: 1,2,3,4,5,61,2,3,4,5,6?
  • Egy p≠0,±1p \neq 0, \pm 1 szám prímszám, ha p=a⋅b⟹p=±ap = a \cdot b \Longrightarrow p = \pm a vagy p=±bp = \pm b.
  • A felsorolásból 2,3,52, 3, 5 prímek, 1,4,61, 4, 6 pedig nem.
  1. Mondja ki a számelmélet alaptételét! Írja fel az n=18n = 18-at a tétel szerint!

  • Minden n≠0,±1n \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=±p1α1p2α2⋯pℓαℓ=±∏i=1ℓpiαin = \pm p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_\ell^{\alpha_\ell} = \pm \prod_{i=1}^\ell p_i^{\alpha_i} ahol p1,p2,…,pℓp_1, p_2, \dots, p_\ell pozitív prímek, α1,α2,…,αℓ\alpha_1, \alpha_2, \dots, \alpha_\ell pozitív egészek.

  • 18=2⋅3218 = 2 \cdot 3^2, vagyis p1=2,α2=1,p2=3,α2=2p_1 = 2, \alpha_2 = 1, p_2 = 3, \alpha_2 = 2 és ℓ=2\ell = 2

  1. 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≡3mod  4x \equiv 3 \mod 4 relációt!
  • Adott n≠0n \neq 0 és a,ba, b egészek esetén, aa kongruens bb-vel modulo nn, vagyis a≡bmod  na \equiv b \mod n, ha n∣a−bn \mid a - b
  • x1=3x_1 = 3, mert 4∣0(=3−3)4 \mid 0 ( = 3 - 3), és x2=7x_2 = 7, mert 4∣4(=7−3)4 \mid 4 ( = 7 - 3)
  1. Mondja ki a lineáris kongruenciák megoldhatóságára vonatkozó tételt! Megoldható-e a 12x≡2mod  1012x \equiv 2 \mod 10 lineáris kongruencia? Ha igen, adja meg az összes megoldást, ha nem, indokoljon!
  • Legyenek a,b,na, b, n egész számok, n>1n > 1. Ekkor az ax≡bmod  nax \equiv b \mod n megoldható ⟺(a,n)∣b\Longleftrightarrow (a, n) \mid b. Ez esetben pontosan (a,n)(a, n) darab inkongruens megoldás van mod n\text{mod}\ n.
  • A példában a=12,b=2,n=10a = 12, b = 2, n = 10. (a,n)=(12,10)=2∣2(a, n) = (12, 10) = 2 \mid 2, vagyis a lineáris kongruencia megoldható, és 2 inkongruens megoldása van mod n\text{mod}\ n: x1=1,x2=6x_1 = 1, x_2 = 6.
  1. Mondja ki a kinai maradéktételt! Megoldható-e az {x≡1mod  2x≡2mod  3 \left\{ \begin{array}{l} x \equiv 1 \mod 2 \\ x \equiv 2 \mod 3 \end{array} \right. szimultán kongruenciarendszer? Ha igen, adja meg az összes megoldást, ha nem, indokoljon!
  • Legyenek 1<n1,n2,…,nk1 < n_1, n_2, \dots, n_k páronként relatív prím számok, c1,c2,…,ckc_1, c_2, \dots, c_k egészek. Ekkor a {x≡c1mod  n1x≡c2mod  n2⋮x≡ckmod  nk\left\{ \begin{array}{l} x \equiv c_1 \mod n_1\\ x \equiv c_2 \mod n_2 &\\ \vdots &\\ x \equiv c_k \mod n_k \end{array} \right. kongruencia rendszer megoldható, és bármely két megoldás kongruens egymással modulo n1⋅n2⋅…⋅nkn_1 \cdot n_2 \cdot \ldots \cdot n_k.
  • A megadott szimultán kongruenciarendszer összes megoldása kongruens egymással modulo 66, és mivel 00 és 55 között az 55 az egyetlen megoldása, így az összes megoldása 5+6k,k∈Z5 + 6k, k \in \Z alakú.
  1. Definiálja az Euler-féle φ\varphi függvényt! Mi lesz φ(6)\varphi(6)?
  • φ(n)=#{1≤a≤n:(a,n)=1}\varphi(n) = \#\{1 \leq a \leq n : (a, n) = 1\}
  • φ(6)=#{1,5,6}=3\varphi(6) = \#\{1, 5, 6\} = 3
  1. Mondja ki az Euler-Fermat-tételt! Mi lesz 34≡?mod  83^4 \equiv? \mod 8. Válaszát indokolja!
  • Legyenek a,n∈Za, n \in \Z, (a,n)=1(a, n) = 1. Ekkor aφ(n)≡1mod  na^{\varphi(n)} \equiv 1 \mod n, ahol φ\varphi az Euler-féle függvény.
  • φ(8)=5\varphi(8) = 5, vagyis 35≡1mod  83^5 \equiv 1 \mod 8. Mivel 3⋅3≡1mod  83 \cdot 3 \equiv 1 \mod 8, ezért 35≡3⋅3mod  83^5 \equiv 3 \cdot 3 \mod 8, és 34≡3mod  83^4 \equiv 3 \mod 8.

Polinomok

  1. Definiálja a polinomok fokát! Mennyi lesz deg⁡(x3+x−1)=?\deg(x^3 + x - 1) =?
  • Adott f=cnxn+⋯+c0f = c_nx^n + \cdots + c_0 polinom foka cn≠0c_n \neq 0 esetén deg⁡f=n\deg f = n.
  • deg⁡(x3+x−1)=3\deg(x^3 + x - 1) = 3
  1. Definiálja a maradékos osztást polinomok körében! Ossza el maradékosan az f=x3+3x+1∈Q[x]f = x^3 + 3x + 1 \in Q[x] polinomot a g=x+1∈Q[x]g = x + 1 \in Q[x] polinommal!
  • Legyen K∈{C,R,Q,Zp}\mathbb{K} \in \{\mathbb{C}, \R, \mathbb{Q}, \Z_p\} és f,g∈K[x],g≠0f, g \in \mathbb{K}[x], g \neq 0. Ekkor léteznek olyan q,r∈K[x]q, r \in \mathbb{K}[x] polinomok, hogy f=q⋅g+r    deg⁡r<deg⁡gf = q \cdot g + r\;\; \deg r < \deg g
  • x3+3x+1=(x2−x+4)(x+1)+(−3)x^3 + 3x + 1 = (x^2 - x + 4)(x + 1) + (-3)
  1. Mondja ki a gyöktényező kiemelhetőségére vonatkozó tételt! Mondjon példát két olyan gg polinomra, melynek gyöke az x=1x = 1 és x=2x = 2 érték!
  • Legyen K∈{C,R,Q,Zp}\mathbb{K} \in \{\mathbb{C}, \R, \mathbb{Q}, \Z_p\}. Legyen f∈K[x]f \in \mathbb{K}[x] és x1∈Kx_1 \in \mathbb{K} egy gyöke. Ekkor ff felírható az f=(x−x1)⋅gf = (x - x_1) \cdot g formában valamely g∈K[x]g \in \mathbb{K}[x] polinommal.
  • g1=(x−1)(x−2)=x2−3x+2g_1 = (x - 1)(x - 2) = x^2 - 3x + 2, g2=2g1=2(x−1)(x−2)=2x2−6x+4g_2 = 2g_1 = 2(x - 1)(x - 2) = 2x^2 - 6x + 4
  1. Mondja ki a polinom foka és gyökeinek száma közötti összefüggést! Hány gyöke lehet az f=x5+x+1∈Q[x]f = x^5 + x + 1 \in Q[x] polinomnak?
  • Legyen K∈{C,R,Q,Zp}\mathbb{K} \in \{\mathbb{C}, \R, \mathbb{Q}, \Z_p\}. Egy f∈K[x]f \in \mathbb{K}[x] polinomnak legfeljebb deg⁡f\deg f gyöke lehet.
  • Az f=x5+x+1∈Q[x]f = x^5 + x + 1 \in Q[x] polinom foka deg⁡f=5\deg f = 5, így legfeljebb 5 gyöke lehet.
  1. Definiálja polinomok legnagyobb közös osztóját! Mi lesz az f=(x−1)(x+1)∈Q[x]f = (x - 1)(x + 1) \in Q[x] és g=x(x−1)2(x+1)∈Q[x]g = x(x - 1)^2(x + 1) \in Q[x] polinomok legnagyobb közös osztója?
  • Két polinom ff és gg legnagyobb közös osztója h=(f,g)=lnko(f,g)=gcd⁡(f,g)h = (f, g) = \text{lnko}(f, g) = \gcd(f, g), ha:
    • Közös osztó: h∣fh \mid f és h∣gh \mid g;
    • legnagyobb: ha q∣fq \mid f és q∣g⇒q∣hq \mid g \Rightarrow q \mid h
    • hh főegyütthatója 11.
  • (f,g)=1(x−1)(x+1)=f  (g=f⋅x⋅(x−1))(f, g) = 1(x - 1)(x + 1) = f\; \big(g = f \cdot x \cdot (x - 1)\big).
  1. Definiálja a formális deriváltat! Mi lesz az f=x2+x+1∈Z2[x]f = x^2 + x + 1 \in Z_2[x] polinom formális deriváltja?
  • ff polinom formális deriváltja:
    • (xn)′=nxn−1(x^n)' = nx^{n-1}
    • (cf)′=cf′(cf)' = cf'
    • (f+g)′=f′+g′(f + g)' = f' + g'
  • (x2+x+1)′=(x2)′+x′+(x0)′=2x+1+0=1(x^2 + x + 1)' = (x^2)' + x' + (x^0)' = 2x + 1 + 0 = 1
  1. Definiálja az irreducibilis polinom fogalmát! Irreducibilis lesz-e az f=(x+1)(x+2)∈R[x]f = (x + 1)(x + 2) \in R[x] polinom?
  • Egy ff polinom irreducibilis, ha nem bontható szorzatra nem-triviális módon, azaz f=g⋅h⟹deg⁡g=deg⁡ff = g \cdot h \Longrightarrow \deg g = \deg f vagy deg⁡h=deg⁡f\deg h = \deg f.
  • Az f=(x+1)(x+2)∈R[x]f = (x + 1)(x + 2) \in R[x] polinom nem irreducibilis, mert szétbontható nem triviálisan a g=x+1g = x + 1 és h=x+2h = x + 2 polinomra.
  1. Definiálja a kongruencia relációt polinomok körében! Mondjon példát két különböző g∈Z2[x]g \in Z_2[x] polinomra, mely teljesíti a g≡x+1mod  x2+x+1g \equiv x + 1 \mod x^2 + x + 1 relációt!
  • Legyen K∈{C,R,Q,Zp}\mathbb{K} \in \{\mathbb{C}, \R, \mathbb{Q}, \Z_p\} és legyen h∈K[x]h \in \mathbb{K}[x] egy nem-nulla polinom. Ekkor f,g∈K[x]f, g \in \mathbb{K}[x] polinomokra f≡gmod  hf \equiv g \mod h, ha h∣f−gh \mid f - g.
  • g1=x+1,g2=x2g_1 = x + 1, g_2 = x^2
  1. Mondja ki a Lagrange interpolációról szóló tételt! Hány olyan legfeljebb harmadfokú polinom van, mely a 33 helyen a 22-t, az 11 helyen a 00-t, a 66 helyen a −9-9-t és a 00 helyen a −1-1-t veszi fel?
  • Legyenek x0,x1,…,xn∈Cx_0, x_1, \ldots, x_n \in \mathbb{C} páronként különböző alappontok és y0,y1,…,yn∈Cy_0, y_1, \ldots, y_n \in \mathbb{C} tetszőleges értékek. Ekkor egyértelműen létezik olyan ff polinom, hogy deg⁡f≤n\deg f \leq n és f(xi)=yif(x_i) = y_i.
  • A példában n=3n = 3, vagyis egyértelműen meghatározható egy legfeljebb harmadfokú polinom ami teljesíti a feltételeket; csakis egy ilyen 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 φ(a)=01,φ(b)=11,φ(c)=01\varphi(a) = 01, \varphi(b) = 11, \varphi(c) = 01 függvény?
  • Legyen X={x1,x2,…,xn}\mathcal{X} = \{x_1, x_2, \ldots, x_n\} halmaz a forrásábécé és Y={y1,y2,…,yn}\mathcal{Y} = \{y_1, y_2, \ldots, y_n\} a kódábécé. Ekkor egy φ:X→Y∗\varphi : \mathcal{X} \rightarrow \mathcal{Y}^* injektív függvényt kódolásnak (vagy betűnkénti kódolásnak) hívunk.
    Itt Y∗\mathcal{Y}^* az Y\mathcal{Y} elemeiből álló véges szavak halmaza.
    A φ\varphi függvényt kiterjesztjük az X∗\mathcal{X}^* halmazra betűnként:
    φ(u1u2…ur)=φ(u1)φ(u2)…φ(un)\varphi(u_1u_2 \ldots u_r) = \varphi(u_1)\varphi(u_2)\ldots\varphi(u_n).
  • A megadott függvény nem betűnkénti kódolás, mert φ(a)=φ(c)\varphi(a) = \varphi(c), vagyis nem injektív.
  1. Definiálja a felbontható kódolás fogalmát! Felbontható kódolás lesz-e a φ(a)=01,φ(b)=11,φ(c)=10\varphi(a) = 01, \varphi(b) = 11, \varphi(c) = 10 függvény?
  • Egy φ:X→Y∗\varphi: \mathcal{X} \rightarrow \mathcal{Y}^* kódolás felbontható (vagy egyértelműen dekódolható), ha u,v∈X∗\bold{u}, \bold{v} \in \mathcal{X}^*, u=u1u2…ur\bold{u} = u_1u_2 \ldots u_r, v=v1v2…vs\bold{v} = v_1v_2 \ldots v_s esetén, ha u≠v\bold{u} \neq \bold{v}, akkor φ(u1)φ(u2)…φ(ur)≠φ(v1)φ(v2)…φ(vs)\varphi(u_1)\varphi(u_2)\ldots\varphi(u_r) \neq \varphi(v_1)\varphi(v_2)\ldots\varphi(v_s)
  • A példában szereplő φ\varphi kódolás felbontható.
  1. Definiálja a prefix kódok fogalmát! Adjon meg az {a,b,c}\{a, b, c\} forrásábécén egy prefix kódolását!
  • Egy φ\varphi kódolás prefix kód (vagy prefixmentes kód), ha nem léteznek olyan u,v\bold{u}, \bold{v} különböző kódszavak, hogy u\bold{u} prefixe v\bold{v}-nek.
  • φ(a)=1,φ(b)=01,φ(c)=001\varphi(a) = 1, \varphi(b) = 01, \varphi(c) = 001.
  1. Definiálja a kódfa fogalmát! Rajzolja fel a {100,101,11,000}\{100, 101, 11, 000\} kód kódfáját!
  • Egy φ\varphi kód kódfája egy olyan fa, melynek csúcsai a kódszavak, és azok prefixei az y1y2…ysy_1y_2 \ldots y_s és y1y2…ysys+1y_1y_2 \ldots y_sy_{s+1} csúcsok vannak összekötve.
  •         ∅
       / \
      0   1
     /   / \
    00  10  11
   /   /  \
  000 100 101
  1. Definiálja a Hamming-távolságot! Mennyi lesz d(010,110)=?d(010, 110) =?, d(0000,0009)=?d(0000, 0009) =?
  • u,v∈Σn\bold{u}, \bold{v} \in \Sigma^n szavak Hamming-távolsága: d(u,v)=#{i:ui≠vi}d(\bold{u}, \bold{v}) = \#\{i : u_i \neq v_i\}
  • d(010,110)=#{2}=1d(010, 110) = \#\{2\} = 1, d(0000,0009)=#{3}=1d(0000, 0009) = \#\{3\} = 1
  1. 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\mathcal{C} kód, ha d(C)=8d(\mathcal{C}) = 8?
  • Egy C\mathcal{C} kód d=d(C)d = d(\mathcal{C}) távolsággal:
    • d−1d - 1 hibát tud jelezni;
    • t=⌊(d−1)/2⌋t = \lfloor (d - 1) / 2 \rfloor hibát tud javítani.
  • d=8d = 8 esetén 77 hibát tud jelezni, ⌊(8−1)/2⌋=3\lfloor (8 - 1) / 2 \rfloor = 3 hibát tud javítani.
  1. Definiálja a lineáris kódok fogalmát! Lineáris lesz-e a C={110,101,111}⊂Z23\mathcal{C} = \{110, 101, 111\} \sub \Z^3_2 kód?
  • Egy C∈Fpn\mathcal{C} \in \mathbb{F}_p^n kód lineáris, ha C\mathcal{C} egy lineáris altér Fpn\mathbb{F}_p^n-ben. Ekkor k=dim⁡Ck = \dim \mathcal{C} a kód dimenziója. Spec. #C=qk\#\mathcal{C} = q^k. Ekkor C\mathcal{C} egy (n,k)(n, k) kód.
  • 110+101=011∉C110 + 101 = 011 \notin \mathcal{C}, vagyis kódok lineáris kombinációjaként előállítható olyan kód, ami nem eleme C\mathcal{C}-nek, és C\mathcal{C} nem egy lineáris kód.
  1. Definiálja lineáris kódok generátormátrixát! Mi lesz a (b1,b2)↦(b1,b2,b1+b2)(b_1, b_2) \mapsto (b_1, b_2, b_1 + b_2) bináris lineáris kód generátormátrixa?
  • Legyen egy C\mathcal{C} lineáris (n,k)(n, k) kód c1,…,ck\bold{c}_1, \ldots, \bold{c}_k generátorokkal. Ekkor a C\mathcal{C} egy generátormátrixa G=(c1,…,ck)∈Fqn×kG = (\bold{c}_1, \ldots, \bold{c}_k) \in \mathbb{F}_q^{n \times k}.
  • G=[I2P]=[100111]G = \begin{bmatrix}I_2 \\ P\end{bmatrix} = \begin{bmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{bmatrix}
  1. Definiálja lineáris kódok ellenőrzőmátrixát! Mi lesz a (b1,b2)↦(b1,b2,b1+b2)(b_1, b_2) \mapsto (b_1, b_2, b_1 + b_2) bináris lineáris kód ellenőrző mátrixa?
  • Legyen C\mathcal{C} egy (n,k)(n, k) kód. Ekkor C\mathcal{C} ellenőrző mátrixa az a H∈Fq(n−k)×nH \in \mathbb{F}_q^{(n - k) \times n} mátrix, melyre Hc=0H\bold{c} = 0 pontosan akkor, ha c∈C\bold{c} \in \mathcal{C}.
  • H=[−GTI]=[−10−10−1−1100010]H = \begin{bmatrix}-G^T \\ I\end{bmatrix} = \begin{bmatrix}-1 & 0 & -1 \\ 0 & -1 & -1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{bmatrix} mert a chatgpt azt mondta