Számítástudomány 2 - Dolgozat Megoldások

1. feladat: Dijkstra algoritmus

Feladat: Határozza meg a Dijkstra algoritmus segítségével az F csúcsból az összes csúcsba a legolcsóbb utak költségeit!

Megoldás menete:

Kezdőpont (F) távolsága 0, a többié ∞ (végtelen).
Válasszuk ki a legkisebb távolságú, még nem rögzített csúcsot.
Relaxáció: ha az aktuális távolság + az él súlya kisebb a szomszéd eddigi távolságánál, írjuk felül.

Dijkstra táblázat (F-ből indulva):

Választott	A	B	C	D	E	G	H	J
-	∞	∞	∞	∞	∞	∞	∞	∞
F (0)	∞	∞	∞	∞	11	12	∞	10
J (10)	∞	∞	∞	∞	11	12	22	10
E (11)	∞	∞	17	18	11	12	20	10
G (12)	∞	∞	15	18	11	12	20	10
C (15)	22	24	15	18	11	12	20	10
D (18)	22	24	15	18	11	12	20	10
H (20)	22	24	15	18	11	12	20	10
A (22)	22	24	15	18	11	12	20	10
B (24)	22	24	15	18	11	12	20	10

Végeredmény (költségek F-ből): A: 22, B: 24, C: 15, D: 18, E: 11, G: 12, H: 20, J: 10.

2. feladat: Huffman kódolás

Feladat: A:4, B:5, C:3, D:2, E:5. Huffman kódok és bitek száma.

Megoldás menete: Mindig a két legkisebb gyakoriságút vonjuk össze.

Huffman-fa felépítésének lépései:

Kezdetben:

D:2  C:3  A:4  B:5  E:5

1. lépés: D(2)+C(3)=5

  (5)
  / \
D:2 C:3  A:4  B:5  E:5

2. lépés: A(4)+5=9

    (9)
    / \
  A:4 (5)
      / \
    D:2 C:3  B:5  E:5

3. lépés: B(5)+E(5)=10

    (9)         (10)
    / \         /  \
  A:4 (5)     B:5  E:5
      / \
    D:2 C:3

4. lépés (Végső fa kódokkal): 9+10=19

      (19)
     /    \
   0/      \1
  (9)      (10)
  / \      /  \
0/  \1   0/    \1
A:4 (5) B:5   E:5
    / \
  0/   \1
 D:2   C:3

Kódok: A: 00, D: 010, C: 011, B: 10, E: 11.
Bitek száma Huffman-nal: 4*2 + 2*3 + 3*3 + 5*2 + 5*2 = 8+6+9+10+10 = 43 bit.
Bitek száma kód nélkül: 19 betű * 3 bit = 57 bit.

3. feladat: NFA -> DFA konverzió

Feladat: Adja meg az eredeti NFA és az új, teljesen definiált DFA mozgástáblázatát!

1. Eredeti NFA mozgástáblázat:

Állapot	'a'	'b'	'c'
-> S	{S}	{S, A}	{S, C}
A	-	-	{B}
B*	-	-	-
C	-	-	{B}

2. Új DFA mozgástáblázat (Részhalmaz-konstrukció):

DFA állapot	'a'	'b'	'c'	Típus
-> {S}	{S}	{S, A}	{S, C}	Kezdő
{S, A}	{S}	{S, A}	{S, C, B}
{S, C}	{S}	{S, A}	{S, C, B}
{S, C, B}	{S}	{S, A}	{S, C, B}	Végállapot

Mivel minden állapothoz minden bemeneti jelre van átmenet, az automata teljesen definiált. (A hiányzó kombinációk, pl. {A, B} nem elérhetőek a kezdőállapotból).

4. feladat: Szindróma dekódolás

Feladat: v1=10100, v2=11101, v3=11001 szavak dekódolása.

Számítási elv: A szindróma s = v * H^T. Bináris esetben ez azt jelenti, hogy összeadjuk (XOR) a H^T mátrix azon sorait, ahol a v vektorban 1-es áll.

H^T sorai: r1=(110), r2=(101), r3=(100), r4=(010), r5=(001)

1. v1 = 10100 dekódolása:

Szindróma (s1): Az 1. és 3. bit 1-es -> r1 + r3 = (110) ⊕ (100) = 010.
Hiba keresése: A táblázatban 010-hoz tartozó hiba: e1 = 00010.
Kódszó (c1): c1 = v1 ⊕ e1 = 10100 ⊕ 00010 = 10110.

2. v2 = 11101 dekódolása:

Szindróma (s2): Az 1., 2., 3. és 5. bit 1-es -> r1 ⊕ r2 ⊕ r3 ⊕ r5 = (110) ⊕ (101) ⊕ (100) ⊕ (001) = 110.
Hiba keresése: A táblázatban 110-hoz tartozó hiba: e2 = 10000.
Kódszó (c2): c2 = v2 ⊕ e2 = 11101 ⊕ 10000 = 01101.

3. v3 = 11001 dekódolása:

Szindróma (s3): Az 1., 2. és 5. bit 1-es -> r1 ⊕ r2 ⊕ r5 = (110) ⊕ (101) ⊕ (001) = 010.
Hiba keresése: A táblázatban 010-hoz tartozó hiba: e3 = 00010.
Kódszó (c3): c3 = v3 ⊕ e3 = 11001 ⊕ 00010 = 11011.

5. feladat: Hill-rejtjelező (Inverz mátrix)

Feladat: Számítsa ki az A = [21 11; 23 14] mátrix inverzét mod 26!

Képlet: A^-1 = (det A)^-1 * adj(A) (mod 26)

Determináns (det A):
det A = (21 * 14) - (11 * 23) = 294 - 253 = 41.
Modulo 26: 41 mod 26 = 15.
A determináns multiplikatív inverze (15^-1 mod 26):
Olyan x-et keresünk, amire 15 * x ≡ 1 (mod 26).
Mivel 15 * 7 = 105, és 105 / 26 = 4, maradék 1 (4 * 26 + 1 = 105).
Tehát: 15^-1 ≡ 7 (mod 26).
Adjungált mátrix (adj A):
2x2-es esetben: főátló elemeit felcseréljük, mellékátló elemeit negáljuk.
adj A =
14 -11
-23 21

Modulo 26 alakítva:
-11 ≡ 15 (mod 26); -23 ≡ 3 (mod 26).
adj A ≡
14 15
3 21
(mod 26).
Végső inverz mátrix (7 * adj A):
A^-1 ≡ 7 *
14 15
3 21
=
98 105
21 147
(mod 26).
Elemek mod 26:
98 mod 26 = 20 (mert 3*26+20=98)
105 mod 26 = 1 (mert 4*26+1=105)
21 mod 26 = 21
147 mod 26 = 17 (mert 5*26+17=147)

Végeredmény: A^-1 =
20 1
21 17

6. feladat: MDS kód paraméterei

Feladat: C(15, 6) MDS kód.

Minimális távolság: d = 15 - 6 + 1 = 10.
Felismerhető hibák (d-1): 9.
Javítható hibák (floor((d-1)/2)): 4.

7. feladat: Lineáris és Duális kód

Feladat: G = [1 0 1 1 0; 0 1 0 1 1]. Duális generátor G' és kódolás.

1. Generátormátrix felbontása (G = [I | P]):
A bal oldali 2x2-es rész az egységmátrix (I), a jobb oldali 2x3-as rész a P mátrix.
P =

1	1	0
0	1	1

2. P mátrix transzponálása (P^T): A sorokból oszlopokat csinálunk.
P^T =

1	0
1	1
0	1

3. Duális generátormátrix (G' = [P^T | I]): A P^T-hez hozzáillesztünk egy 3x3-as egységmátrixot.
G' =

1	0	1	0	0
1	1	0	1	0
0	1	0	0	1

4. Üzenetek kódolása (c = u * G'): Csak azokat a sorait adjuk össze (XOR) G'-nek, ahol az u üzenetvektorban 1-es áll.
- u1=(1,1,1): 1., 2. és 3. sor összege: (10100) ⊕ (11010) ⊕ (01001) = (00111)
- u2=(1,0,1): 1. és 3. sor összege: (10100) ⊕ (01001) = (11101)
- u3=(1,1,0): 1. és 2. sor összege: (10100) ⊕ (11010) = (01110)
- u4=(0,1,1): 2. és 3. sor összege: (11010) ⊕ (01001) = (10011)

8. feladat: Nyelvtanból automata

Feladat: G = {S,N,P,S} alapján automata átmenetek. Szabályok (példa a levezetéshez):
S→aS | aB | cA; A→cA | b | bB | cB | bC; B→cS | a | aC; C→a | bB.

Szabályok átfordítási logikája: Minden nagybetű egy-egy állapot. A kisbetűk az átmeneteken lévő feltételek. Ha egy szabály csak kisbetűs lezáró (pl. A→b), ahhoz bevezetünk egy új 'E' (Elfogadó) végállapotot.

S állapotból: az S→aS miatt 'a'-val önmagába (S), az S→aB miatt 'a'-val B-be, az S→cA miatt 'c'-vel A-ba jutunk.
A állapotból: A→cA ('c'->A), A→cB ('c'->B), A→bB ('b'->B), A→bC ('b'->C), A→b ('b'->E).
B állapotból: B→cS ('c'->S), B→aC ('a'->C), B→a ('a'->E).
C állapotból: C→bB ('b'->B), C→a ('a'->E).

Átmeneti függvény (delta) táblázatban:

Állapot	'a' bemenet	'b' bemenet	'c' bemenet
-> S (Kezdő)	{S, B}	∅	{A}
A	∅	{E, B, C}	{A, B}
B	{E, C}	∅	{S}
C	{E}	{B}	∅
(E) (Elfogadó)	∅	∅	∅

14	-11
-23	21

98	105
21	147