Skúška

Plán skúškového obdobia

Miesto skúšky je PC17, čas je vždy 10:10.

Typ	Dátum	Týždeň	Kapacita	Úloha
R	19.12. pondelok	Z	20	p1 p2 p3
R	5. 1. štvrtok	1	15	o p3 r3
R	9. 1. pondelok	2	15	o p1 r1
R	12. 1. štvrtok	2	15	o p2 r2
R	16. 1. pondelok	3	15	o p3 r3
R	19. 1. štrvrtok	3	15	o p1 r1
R	23. 1. pondelok	4	15	o p2 r2
R	25. 1. streda	4	15	o p3 r3
RO	30. 1. pondelok	5	15	o p1 r1
RO	2. 2. štvrtok	5	15	o p2 r2
O	6. 2. pondelok	6	15	o p3 r3

Odovzdanie

Pozrite si kódy úloh na daný termín. Zadania úloh sú uvedené nižšie.

• Riešenie odovzdávate na Git cez systém Traktor do príslušného adresára.
• Riešenie musí obsahovať Makefile pre preklad pomocou príkazu make. Príkaz make musí skompilovať program.
• 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.

Riešenie musí obsahovať 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.

Hodnotenie

Hodnotenie sa skladá z troch častí. Na úspešnú skúšku musíte dosiahnuť minimálne 31 bodov zo 60. Ku skúške sa pripočítajú body zo zápočtu, ak ste presiahli 40 bodov.

Kód	Body	Úloha
p	15	prvá úloha, automaticky hodnotená
r	20	druhá úloha , ručne hodnotená	druhá úloha
o	25	dokumentácia k prvej a druhej úlohe, 2 otázky zo zdrojových kódov

Postup pri hodnotení

1. Automatické prvej úlohy (p) hodnotenie je len odporúčaním. (max 15 bodov)
2. Prezentujete Vaše riešenie druhej úlohy. (max. 20 bodov).
3. Dostanete jednu až dve otázky z každej úlohy. Otázky sa budú týkať Vašich zdrojových kódov a látky na prednáškach. Neobhájenie odovzdaných zdrojových kódov znamená neúspešnú skúšku. (max. 25 bodov)

Prezentácia riešenia druhej úlohy (r)

Ukážete a okomentujete funkčnosť riešenia 2. úlohy (r). Max. 2 minúty., max 20 bodov.

Na riešení sa bude hodnotiť:

• Funguje program správne ? Má správny výsledok ?
• Obsahuje chyby ?
• Správa sa program podľa očakávania ?
• Je program univezálne použiteľný ? Funguje aj v zložitejších situáciách?
• Je spustenie a používanie jednoduché ?
• Obsahuje vstavanú nápovedu ? Program by mal mať zdokumentované používateľské rozhranie.
• Sú kódy ľahko čitateľné a zdokumentované ?
• Je napísané v akých podmienkach program funguje správne ? Originalita
• Koľko cudzieho kódu ste využili pri riešení? Nízka originalita znamená nízke hodnotenie.

Osobná časť hodnotenia (o)

Zodpoviete 2 otázky zo zdrojových kódov. cca 5 min, max 25 bodov.

Hodnotí sa kvalita dokumentácie a 1 alebo 2 otázky ku zdrojovým kódom.

Skontrolujte si dokumentáciu:

• Je dokumentácia zrozumiteľná?
• Obsahuje dokumentácia všetko potrebné?
• Je pekne upravená?
• Je gramaticky a jazykovo správna?

Zadania P1R1

p1 Huffmanov strom

Odovzdanie:

• Cez Traktor do súboru p1/program.c
• za 15B, automatické hodnotenie
• doplňte dokumentáciu do súboru README.md

Napíšte program na zostavenie Huffmanovho stromu.

Na vstupe bude na jednom riadku postupnosť znakov. Platné sú všetky písmená anglickej abecedy a všetky cifry. V prípade, že sa na vstupe vyskytne neplatný znak, vypíšte chybovú správu a skončite.

Zistite početnosť jednotlivých znakov a z nich zostavte Huffmanov strom.

Strom vypíšte vo formáte preorder, jeden uzol na jeden riadok. V prípade nelistového uzla vypíšte znak #. V prípade listového uhla vypíšte zodpovedajúci znak.

Príklad na vstup:

ass

Príklad na výstup:

#
a
s

r1 Kalkulačka

• cez Traktor do súboru r1/main.c
• za 20B, osobné hodnotenie
• doplňte dokumentáciu do súboru README.md
• pripravte a odovzdajte aj súbor Makefile s pravidlami pre preloženie programu.
• na git odovzdajte aj ostatné zdrojové súbory.

Naprogramujte 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:

• dekadické čísla s presnosťou na min. 2 desatinné miesta.
• sčítanie, odčítanie, násobenie, delenie, zátvorky.

Príklad použitia:

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

Zadanie P2R2

p2 Huffmanovo dekódovanie

• cez Traktor do súboru p2/program.c
• za 15B, automatické hodnotenie
• doplňte dokumentáciu do súboru README.md

Na vstupe dostanete Huffmanov strom a zakódovaný reťazec. Dekódujte reťazec zložený z núl a jednotiek na poslednom riadku vstupu.

Huffmanov strom je zapísaný vo formáte preorder. Ľavá strana znamená predponu 0, pravá strana predponu 1.

Huffmanov strom bude zadaný v preorder formáte. Každý uzol bude na samostatnom riadku. Nelistový uzol bude značený ako #, listový uzol bude znak anglickej abecedy alebo cifra.

V prípade, že strom nebude kompletný, vypíšte chybovú správu a ukončite program. V prípade, že nebude možné rozkódovať postupnosť núl a jednotiek, vypíšte chybovú správu a ukončite program.

V príprade, že na posledom riadku sa nachádza iný znak ako nula a jednotka vypíšte o tom správu a ukončite program.

Príklad:

#
a
#
b
c

kóduje takýto Huffmanov strom pre znaky a a b:

    #
  /  \
 a    #
     /  \
    b    c

Kódy znakov budú:

a: 0
b: 10
c: 11

Príklad na vstup:

#
b
n
1100

Príklad na výstup:

nnbb

r2 Kompressor

• stiahnite si šablónu a rozbaľte ju do Vášho repozitára.
• cez Traktor do súboru r2/compressor.c
• za 20B, osobné aj automatické hodnotenie
• doplnte implementáciu podľa šablóny. Dokončite program do používateľsky príjemnej podoby s riadkovým rozhraním.
• doplňte dokumentáciu do súboru README.md
• na git odovzdajte aj ostatné zdrojové súbory.
• na git nedávajte dátové veľké súbory.

Naprogramuj nástroj na kompresiu a dekompresiu. Na kompresiu použite aspoň dva kompresné algoritmy, napr. : Huffmanovo kódovanie, LZ77, LZ78, Run Length kódovanie alebo iný.

Meno vstupného a výstupného súboru načítajte ako argument príkazového riadka. V zadaní by mali byť implementované tieto dve funkcie:

/**
 * Skomprimuje súbor in a zapíše do súboru out. 
 * @arg in smerník na otvorený vstupný súbor (na čítanie)
 * @arg out smerník na otvorený výstupný súbor (na zápis)
 * @return počet bajtov skomprimovaného súboru
 */
int compress(FILE* in, FILE* out);
/**
 * Dekomprimuje súbor in a zapíše do súboru out. 
 * @arg in smerník na otvorený vstupný súbor (na čítanie)
 * @arg out smerník na otvorený výstupný súbor (na zápis)
 * @return počet bajtov dekomprimovaného  súboru
 */
void decompress(FILE* in, FILE* out);

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 Cantebury corpus

Zadanie P3R3

p3 Huffmanovo kódovanie

• cez Traktor do súboru p3/program.c
• za 15B, automatické hodnotenie
• doplňte dokumentáciu do súboru README.md

Zostavte program na Huffmanovo kódovanie. Zakódujte znaky do kódovania daného Huffmanovým stromom. Ľavá strana znamená predponu 0, pravá strana predponu 1.

Na vstupe dostanete Huffmanov strom a reťazec znakov. Reťazec vstupných znakov sa bude nachádzať na poslednom riadku.

V prípade, že sa nebude dať zostaviť Huffmanov strom, vypíšte chybovú správy a skončite. Ak sa v poslednom riadku budú nachádzať symboly, pre pre ktoré neexistuje kódovanie tak vypíšte chybovú správu a skončite.

Huffmanov strom bude zadaný v preorder formáte. Každý uzol bude na samostatnom riadku. Nelistový uzol bude značený ako #, listový uzol bude znak anglickej abecedy alebo cifra.

Príklad:

#
a
#
b
c

kóduje takýto Huffmanov strom pre znaky a a b:

    #
  /  \
 a    #
     /  \
    b    c

Kódy znakov budú:

a: 0
b: 10
c: 11

Na výstupe vypíšte pre každý znak jeho zodpovedajúci Huffmanov kód na samostatný riadok.

Príklad vstupu:

#
a
s
ss

Príklad výstupu:

1
1

r3 Slovné vektory

• cez Traktor do súboru r3/main.c
• za 20B, osobné hodnotenie
• doplňte dokumentáciu do súboru README.md
• pripravte a odovzdajte aj súbor Makefile s pravidlami pre preloženie programu.
• na git nedávajte dátové veľké súbory.

Slovný vektor vyjadruje význam slova v 300 rozmernom príznakovom priestore. Významovo podobné slová majú blízke slovné vektory. Vzdialenosť slovných vekorov je vyjadrená pomocou kosínusovej podobnosti.

Slovenské slovné vektory boli odhadnuté z textov na slovenskej wikipédii pomocou programu FastText.

Vytvorte program na načítanie slovenských slovných vektorov do indexu, ktorý by umožnil ľahké vyhľadávanie najbližšieho slovného vektora. Program by mal umožniť vyhľadanie slovného vektora pre zadané slovo a ku nemu 5 významovo najbližších slov.

Príklad použitia programu:

./vektory wiki.sk.vec piesok
Načítaných 316098 vektorov.
Najbližšie slová sú:
pieskovisko
piesok
piesku

Navrhnite program tak, aby jeho najhoršia zložitosť vyhľadanie pre jedno slovo bola O(n log n).