Skúška

Príprava

V školskej časti skúšky sa vyskytne jeden z týchto príkladov:

• RLE Kódovanie (binárnych dát).
• Huffmanovo kódovanie - zostavenie Huffmanovho stromu z binárnych dát.
• Spojkový zoznam - pridanie na začiatok a na koniec, odobratie prvku.
• Binárny vyhľadávací strom - vytvorenie a zrušenie, výpis preorder, inorder, postorder, vyhľadávanie
• Binárna kopa - overenie kopovitosti,pridávanie, odoberanie, zostavenie kopy, triedenie pomocou kopy, výpis kopy vo forme stromu

Vyhodnotenie bude vo forme jednotkových testov, podobne ako pri zápočtových písomkách.

Naštudujte a nacvičte si algoritmy tak aby ste ich vedeli samostatne naprogramovať na skúške. Pri príprave používajte aj systém Valgrind.

V prípade, že nie sú postačujúce prednášky a cvičenia, odporúčaný spôsob praktickej a teoretickej prípravy je naštudovať si problém a vyskúšať pomoocu

• Exercism C Track

• Geek4Geeks Practice:

  • Triedenie
  • Asociatívne polia
  • Spojkové zoznamy
  • Vyhľadávací strom: Binárny vyhľadávací strom, prechádzanie inorder, preorder, postorder, vyhľadávanie. pridávanie
  • Zásobník
  • Binárna kopa

Riadny termín

Bude sa skladať z domácej úlohy (20 bodov) a zo školskej úlohy (40 bodov).

Domáce zadanie:

• Kompressor

Domáca časť pre riadny termín: Kompressor

Naprogramuj nástroj na kompresiu a dekompresiu.

Na kompresiu použite kompresný algoritmu, napr. : Huffmanovo kódovanie, LZ77, LZ78, iný. Môžete vymyslieť aj vlastný algoritmus. Nesmiete použiť algoritmus RLE - Run Length Encoding.

Kompresor a dekompresor by mal byť schopný pracovať s ľubovoľným binárnym súborom do 10 MB. Súbor by mal byť po skomprimovaní menší minimálne o 10 percent a po dekomprimovaní by mal byť zhodný s pôvodným súborom. Pri práci s binárnymi súbormi môžete využiť funkcie fopen(), fread() a fwrite().

Na otestovanie kompresora a dekompresora použite súbory z Canterbury corpus

Riešenie nesmie využívať inú ako štandardnú knižnicu. Riešenie sa môže inšpirovať voľne dostupným cudzím riešením za predpokladu že uvediete zdroj, ste podrobne oboznámený so zdrojovým kódom a viete odpovedať na otázky týkajúce sa kódu. Vaše riešenie nemôže kopírovať cudzie riešenie. V prípade, že použijete generatívny model, napíšte ktorý a napíšte aj prompt ktorý ste použili.

Program by mal mať takéto rozhranie pri spustení z príkazového riadka:

# skomprimuje infile do súboru outfile
./compressor -c infile outfile
# dekomprimuje sUbor compressed a zapise do suboru uncompressed.
./compressor -d compressed uncompressed
./compressor -h  # Vypíše pomoc

Súčasťou programu je aj dokumentácia z ktorej sú jasné implementačné detaily aj návod na použitie.

Meno vstupného a výstupného súboru načítajte ako argument príkazového riadka.

Odovzdanie domácej časti skúšky

Riešenie odovzdávajte na GIT s pomocou systému Traktor do repozitára usaa25 do adresára sk1.

Vaše riešenie by malo byť ukončené a odovzdané najneskôr 2 dni pred termínom skúšky na ktorý ste sa prihlásili.

Adresár musí obsahovať:

• compressor.h : hlavičkový súbor s predpismi funkcií uvedených vyššie.
• compressor.c: implementácia funkcií definovaných v hlavičkovom súbore.
• main.c : implementácia funkcie main().
• Makefile : Pravidlá pre skompilovanie. Príkaz make musí skompilovať program.
• README.md s dokumentáciou. Dokumentácia musí obsahovať zadanie, stručný opis funkčnosti, stručný opis riešenia , podmienky za ktorých funguje a zoznam použitých zdrojov.

Opravný termín

Opravný termín bude hodnotený podobne ako riadny termín. Pred termínom vypracujete domácu časť skúšky a v škole vypracujete písomku.

Domáca časť - Opravný termín - Kalkulačka

Naprogramuj vedeckú kalkulačku. Kalkulačka by mala vyhodnocovať aj zložitejšie výrazy v infixnej notácii.

Kalkulačka by mala podporovať tieto operácie:

• načítanie a prácu s číslami s presnosťou min. 2 desatinné miesta.
• sčítanie, odčítanie, násobenie, delenie, zátvorky.
• sinus, cosinus, odmocnina, druhá mocnina, logaritmus.

Príklad použitia:

(2 + 3) * 2
10
(10 * 2) + (6 / 2)
23

Pri riešené môžete využiť prepis infixovej formy zápisu do postfixovej. Potom môžete problém riešiť ako "zásobníkovú" kalkulačku.

Odovzdanie domácej časti skúšky

Riešenie odovzdávajte na GIT s pomocou systému Traktor do repozitára usaa25 do adresára sk2.

Vaše riešenie by malo byť ukončené a odovzdané najneskôr 2 dni pred termínom skúšky na ktorý ste sa prihlásili.

Adresár musí obsahovať:

• calculator.h : hlavičkový súbor s predpismi funkcií uvedených vyššie.
• calculator.c: implementácia funkcií definovaných v hlavičkovom súbore.
• main.c : implementácia funkcie main().
• Makefile : Pravidlá pre skompilovanie. Príkaz make musí skompilovať program.
• README.md s dokumentáciou. Dokumentácia musí obsahovať zadanie, stručný opis funkčnosti, stručný opis riešenia , podmienky za ktorých funguje a zoznam použitých zdrojov.

Predtermín

Predtermín sa uskutoční na poslednom cvičení. Nebude potrebné vypracovať "domácu úlohu", len "domácu prípravu" na programovanie na hodine.

Na hodine naprogramujte:

• Run Length kódovanie binárnych dát
• Zostavenie Huffmanovho stromu zo zadaných znakov a ich početností.
• Výpis a načítanie binárneho stromu vo formáte preorder.
• Zakódovanie alebo dekódovanie údajov Huffmanovým kódovaním podľa zadaného stromu.