Számítástudomány - Életszerű Gyakorlófeladatok

A vizsgafeladatokhoz hasonló, de valós ipari szituációkra épülő gyakorlópéldák.

1. feladat: Dijkstra algoritmus (Logisztika és Útvonaltervezés)

Szituáció: A Wolt/Foodora futárrendszerében dolgozol. Egy futárnak (F csúcs) az étteremből kell eljutnia egy megrendelőhöz a belvárosban. A város utcáit egy gráf modellezi, ahol az élek az utcák, a súlyok pedig az aktuális forgalmi dugók alapján számított percek.

Feladat: Adott a térkép (gráf) a következő percekkel: F-ből elérhető az Andrássy út (A, 8 perc) és a Bajcsy-Zsilinszky (B, 5 perc). B-ből elérhető a Deák tér (D, 3 perc) és az Oktogon (O, 6 perc). A-ból elérhető az Oktogon (O, 2 perc).
Építsd fel a Dijkstra táblázatot F-ből kiindulva, és határozd meg a leggyorsabb utat az Oktogonig (O)! Cseréld fel a "költséget" a valós "idő" fogalmára.

2. feladat: Huffman kódolás (Adattömörítés a Messengerben)

Szituáció: Egy chat alkalmazás (pl. WhatsApp) fejlesztője vagy. A cél az elküldött üzenetek hálózati forgalmának (adatkeretének) csökkentése. Megfigyeltétek, hogy a magyar nyelvű üzenetekben bizonyos karakterek sokkal gyakrabban fordulnak elő.

Feladat: Egy tipikus "Szia mizu?" jellegű üzenetmintában az előfordulások: E(12), A(10), I(8), Z(4), U(2). Készítsd el erre a mintára a Huffman-fát!
Határozd meg a kódokat, és számold ki, hány bitet spórol a szerver ezzel a módszerrel ahhoz képest, mintha minden karaktert fix 3 biten tárolna (mivel 5 féle karakter van).

3. feladat: NFA -> DFA konverzió (Bankautomata Állapotgép)

Szituáció: Egy bankautomata (ATM) szoftverét írod. A felhasználó gombnyomásait (PIN beírása, Összeg megadása, Jóváhagyás) egy állapotgép kezeli. Egy junior fejlesztő véletlenül egy Nemdeterminisztikus (NFA) tervet adott át, ahol a "Jóváhagyás" gomb lenyomása ('j' esemény) a hálózat állapotától függően a "Pénzkiadás" (P) vagy a "Hiba" (H) állapotba is viheti a gépet egyidejűleg.

Feladat: A determinisztikus (DFA) vezérlőszoftver megírásához alakítsd át a modellt.
Alapállapot (S). 'p' (pin) jelre: A-ba megy. 'o' (összeg) jelre: A-ból B-be megy. 'j' (jóváhagyás) jelre B-ből {P, H} állapotokba visz az NFA.
Írd fel a részhalmaz-konstrukciós táblázatot! Mi lesz a DFA végső "állapot-részhalmaza", ami lekezeli ezt a hálózati aszinkronitást?

4. feladat: Szindróma dekódolás (Műholdas Adatátvitel)

Szituáció: A SpaceX egyik mérnökeként a Starlink műholdak és a földi állomások közötti csomagvesztéseket kezeled. A kozmikus sugárzás miatt a bitek néha átbillenek (1-ből 0 lesz). Hibajavító kódokat használtok, hogy a földi állomás automatikusan korrigálja az 1 bites hibákat anélkül, hogy újra kéne kérni a csomagot.

Feladat: A földi állomás befogad egy csomagot: v = 11011. A beépített hardveres paritásmátrix (H^T) sorai: (100), (010), (001), (110), (101).
Végezd el a Szindróma számítást (XOR műveletek)! Ha a kapott szindróma pl. 011, az a 2. bit hibáját jelenti. Találd meg, hol billent át a bit, és írd fel a javított (eredeti) műholdas üzenetet!

5. feladat: Hill-rejtjelező (Legacy Banki Adatbázis Titkosítás)

Szituáció: Egy régi, 1990-es évekbeli banki adatbázist kell modernizálnod. A jelszavakat egy régi Hill-rejtjelező algoritmus titkosította egy 2x2-es mátrixszal. Ahhoz, hogy migrálni tudd a jelszavakat az új bcrypt alapú rendszerbe, először dekódolnod kell őket, amihez meg kell találnod a titkosító mátrix inverzét.

Feladat: A régi forráskódban megtaláltad a titkosító mátrixot: A = [5 8; 17 3]. A rendszer az angol ábécé 26 betűjét (mod 26) használta.
Számítsd ki a dekódoló mátrixot (A inverzét mod 26)! Keresd meg a determinánst, annak multiplikatív inverzét, majd szorozd be vele az adjungált mátrixot.

6-7. feladat: MDS és Duális kódok (RAID SSD Adattárolás)

Szituáció: Egy adatközpontban dolgozol, ahol az új szerverek adattárolását (RAID 6 szerű rendszer) tervezed. A szerverek adatait feldaraboljátok (k=4) és extra paritás-szerverekre (n=7) mentitek, így jön létre egy C(7, 4) paraméterű kód. A cél, hogy ha egy SSD meghibásodik, az adatok azonnal helyreállíthatóak legyenek.

Feladat: 1. Határozd meg, hogy egy C(7,4) MDS kód esetén maximum hány SSD (hiba) eshet ki úgy, hogy a rendszer még garantáltan javítani tudja az adatokat!
2. A redundanciát generáló áramkör a Duális Kódtér generátormátrixát (G') használja. Ha az eredeti mátrix "P" része a [1 1 0; 0 1 1; 1 0 1; 1 1 1], állítsd össze a G' mátrixot a hardveres implementációhoz!

8. feladat: Nyelvtanból automata (Terminál Parancs Értelmező)

Szituáció: Egy saját fejlesztésű CLI (Command Line Interface) eszközt írsz (mint pl. a Docker vagy a Git). A parancssori argumentumok feldolgozóját (Parser) egy jobbreguláris nyelvtan írja le. A gyors futás érdekében ezt a nyelvtant egy véges állapotgéppé (DFA/NFA) fordítod le, ami karakterről karakterre olvassa a felhasználó parancsait.

Feladat: A parancs (pl. 'run' vagy 'rm') szintaktikája: S -> rU | rM; U -> uN; N -> nE; M -> mE; E -> (üres/elfogadó).
Rajzold fel az automatát (vagy írd fel a táblázatot), amely eldönti egy beírt szóról, hogy az érvényes parancs-e! Mik lesznek az állapotok és mik az átmeneti feltételek (bemenetek)?