1. feladat: MDS kód paraméterei

Feladat: Adott egy C(15, 4) paraméterű maximális távolságú kód. Adja meg a felismerhető és javítható hibák számát!

Megoldás:
MDS kódnál a minimális távolság: d = n - k + 1.
Adatok: n = 15, k = 4.
Minimális távolság (d): d = 15 - 4 + 1 = 12.
Felismerhető hibák maximális száma: f = d - 1 = 12 - 1 = 11.
Javítható hibák maximális száma: t = ⌊(d - 1) / 2⌋ = ⌊11 / 2⌋ = 5.

2. feladat: Lineáris kód ekvivalens szisztematikus mátrixa

Feladat: Adott G = [0 1 0 1 1; 0 0 1 1 0; 1 1 0 1 0]. Adjon meg egy ekvivalens szisztematikus kódot G' és H' mátrixszal!

1. G' (Szisztematikus generátormátrix [I | P]) előállítása:
Cél, hogy a mátrix bal oldala egy 3x3-as egységmátrix legyen. Ehhez sorcseréket és sorok összeadását (XOR) alkalmazzuk.
Eredeti G:
r1: 0 1 0 1 1
r2: 0 0 1 1 0
r3: 1 1 0 1 0

Tegyük az r3-at az első helyre (mert 1-gyel kezdődik), az r1-et a másodikra (mert 0 1-gyel kezdődik), r2 marad harmadik:
r1': 1 1 0 1 0
r2': 0 1 0 1 1
r3': 0 0 1 1 0

Hogy az r1' második oszlopa 0 legyen, adjuk hozzá (XOR) az r2'-t: r1'' = r1' ⊕ r2' = (1 0 0 0 1).
A kész szisztematikus mátrix (G'):
G' =

10001
01011
00110

Itt a P mátrix a jobb oldali 3x2-es blokk: P = [0 1; 1 1; 1 0].

2. H' (Paritásellenőrző mátrix [PT | I]) előállítása:
P transzponáltja (PT) = [0 1 1; 1 1 0]. Ehhez jobbról hozzátoldunk egy 2x2-es egységmátrixot.
H' =

01110
11001

3. feladat: Hill-rejtjelező (Kódolás és inverz)

Feladat: A = [18 15; 11 13]. Adja meg a CSIRKE szó rejtjelezett változatát és az A mátrix inverzét mod 26!

1. A inverze mod 26:
- det(A) = 18*13 - 15*11 = 234 - 165 = 69. Modulo 26: 17.
- 17 multiplikatív inverze: 17 * x ≡ 1 (mod 26) → x = -3 ≡ 23 (mert 17*3 = 51 = 2*26 - 1).
- Adjungált mátrix: [13, -15; -11, 18] ≡ [13, 11; 15, 18] (mod 26).
- A-1 = 23 * adj(A) = [299, 253; 345, 414]. Modulo 26 leosztva:
A-1 =

1319
724

2. A CSIRKE szó kódolása:
A betűk kódjai (A=0, B=1...): C=2, S=18, I=8, R=17, K=10, E=4.
Vektorok: v1=[2, 18], v2=[8, 17], v3=[10, 4]. Szorozzuk be az eredeti A mátrixszal (c = A*v mod 26):
- c1: (18*2 + 15*18) = 306 ≡ 20 (U). (11*2 + 13*18) = 256 ≡ 22 (W). Eredmény: UW.
- c2: (18*8 + 15*17) = 399 ≡ 9 (J). (11*8 + 13*17) = 309 ≡ 23 (X). Eredmény: JX.
- c3: (18*10 + 15*4) = 240 ≡ 6 (G). (11*10 + 13*4) = 162 ≡ 6 (G). Eredmény: GG.
Titkosított szó: UWJXGG.

4. feladat: Minimális automata

Feladat: Adott automata (állapotok 1-8, 7-es a végállapot). Készítse el a minimális automatát!

Megoldás menete (Ekvivalencia osztályok iterációja):
Eredeti állapotok és átmenetek (a, b):
1→(2,5), 2→(3,7), 3→(3,6), 4→(3,7), 5→(7,3), 6→(4,5), 7(F)→(1,7), 8→(7,3).

- 0. lépés: Végállapotok és Nem végállapotok felosztása: P0 = {7}, {1,2,3,4,5,6,8}
- 1. lépés: A nem végállapotokat szétbontjuk aszerint, hová mutatnak P0-ban. 2, 4 'b'-re a 7-esbe mutat; 5, 8 'a'-ra a 7-esbe mutat; a többi egyikre sem.
P1 = {7}, {2,4}, {5,8}, {1,3,6}
- 2. lépés: Az {1,3,6} halmazt tovább bontjuk P1 alapján. Az 1-es és 6-os a {2,4} illetve {5,8} osztályokba mutatnak ('a' és 'b' jelre rendre), míg a 3-as a {1,3,6} halmazon belül marad. Így szétválnak.
P2 = {7}, {2,4}, {5,8}, {1,6}, {3}
- 3. lépés: A további bontás nem hoz új osztályt, az algoritmus megállt.

Minimalizált automata állapotai (Összevonások):
Új állapotok: A={1,6} (Kezdő), B={2,4}, C={3}, D={5,8}, E={7} (Végállapot).
Új átmenetek: A→(B,D), B→(C,E), C→(C,A), D→(E,C), E→(A,E).

5. feladat: Huffman kódolás

Feladat: G:2, H:4, E:4, A:5, B:6. Huffman kódok és bitek száma.

Huffman-fa felépítése:
      (21)
     /    \
   0/      \1
  (9)      (12)
  / \      /  \
0/  \1   0/    \1
E:4 A:5 B:6   (6)
              / \
            0/   \1
           G:2   H:4

Lépések: 1. G(2)+H(4)=6; 2. E(4)+A(5)=9; 3. B(6)+6=12; 4. 9+12=21.
Kódok: E: 00, A: 01, B: 10, G: 110, H: 111.
Bitek száma Huffman-nal: 4*2 + 5*2 + 6*2 + 2*3 + 4*3 = 8+10+12+6+12 = 48 bit.
Bitek száma kód nélkül: 5 betűhöz 3 bit kell. Összesen 21 betű * 3 bit = 63 bit.

6. feladat: Dijkstra algoritmus

Feladat: Eljutni A-ból I-be a taxival. A gráf viteldíjai alapján tervezze meg a legolcsóbb utat!

Megoldás menete:
  1. Kezdőpont (A) távolsága 0, a többié ∞ (végtelen).
  2. Minden lépésben kiválasztjuk a legkisebb távolságú, még nem rögzített csúcsot.
  3. Relaxáció: frissítjük a szomszédok értékeit, ha az "aktuális távolság + viteldíj" kisebb a korábbinál.
Dijkstra táblázat (A-ból indulva):
VálasztottBCDEFGHI
-∞∞∞∞∞∞∞∞
A (0)1053∞∞∞∞∞
D (3)1053∞∞∞20∞
C (5)10531414720∞
G (7)10538147208
E (8)10538127208
I (8)10538127208

(A táblázatot elég volt az I csúcs rögzítéséig kitölteni a feladat szerint).

Legolcsóbb út költsége: 8 euró.
Útvonal: A → C → G → I.

7. feladat: Nyelv automatája

Feladat: Készítse el a következő nyelv automatáját: L = { a b3i a2j | i, j ∈ Z+ }

Megoldás menete:
A Z+ a pozitív egész számokat jelenti (1, 2, 3...), tehát i ≥ 1 és j ≥ 1. A szavak felépítése:

  1. Kezdődik egy 'a' betűvel.
  2. Utána jön 'b', méghozzá pontosan 3-szor, 6-szor, 9-szer stb. (legalább 3-szor). Ehhez egy 3 állapotú ciklus (hurok) kell.
  3. Végül 'a' betűk jönnek párosával (2, 4, 6... tehát legalább 2-szer). Ehhez egy 2 állapotú ciklus kell, ahol a második állapot a végállapot.

Az automata gráfja (állapotok és átmenetek):

8. feladat: Automata mozgástáblázata és nyelvtana

Feladat: Adott az M ({S, A, B, C}, {a, b, c, d, e, f}, δ, S, {C}) automata az alábbi átmenetekkel:
(S, b)=A, (S, a)=A, (S, e)=B, (A, a)=A, (A, b)=C, (B, f)=A, (B, f)=C.
Készítse el a mozgástáblázatot és a jobbreguláris nyelvtant!

Megoldás menete:
1. A mozgástáblázat a megadott átmenetek halmazos ábrázolása. Mivel (B, f) két helyre is megy (A és C), ez egy Nemdeterminisztikus (NFA) automata.
2. A jobbreguláris nyelvtan (X → xY alakú szabályok) előállítása az automatából: Minden δ(X, x) = Y átmenetből csinálunk egy X → xY szabályt. Ha az 'Y' végállapot (esetünkben a 'C'), akkor felvesszük a lezáró X → x szabályt is. (Vagy alternatívaként bevezetjük a C → ε szabályt).

1. Mozgások táblázata:
Állapotabcdef
→ S{A}{A}∅∅{B}∅
A{A}{C}∅∅∅∅
B∅∅∅∅∅{A, C}
(C)∅∅∅∅∅∅
2. Jobbreguláris nyelvtan helyettesítési szabályai: