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íkazumake
. Príkazmake
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í
- Automatické prvej úlohy (p) hodnotenie je len odporúčaním. (max 15 bodov)
- Prezentujete Vaše riešenie druhej úlohy. (max. 20 bodov).
- 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)
.