Warning
This page is located in archive.

Domácí úkoly

Úkoly jsou automaticky testovány systémem BRUTE.

Seznam domácích úkolů

Číslo úkolu a název Body celkem Body, které je nutné získat Termín odevzdání Počet uploadů
HW 01 - Prohledávání do hloubky 10b 5b 24. 3. 2024 20
HW 02 - Řadící algoritmy 10b 5b 21. 4. 2024 20
HW 03 - Hašování 10b 5b 5. 5. 2024 20
HW 04 - Dynamické programování 15b 5b 26. 5. 2024 20
Termíny domácích úkolů jsou stanoveny tak, aby nedošlo k časové tísní. Procvičována témata jsou ale obvykle probírána mnohem dříve. Doporučujeme na úkolech pracovat průběžně v dostatečném předstihu před termínem odevzdání!

Obecné pokyny pro vypracování úkolů

Úkoly jsou zaměřeny na implementaci algoritmů, které jsou probírány na přednáškách a cvičeních. Důraz je kladen na algoritmus, jeho použití, správnou implementaci, ale také na jeho časovou a prostorovou náročnost.

Úlohy je možné zpracovat v jenom z programovacích jazyků C/C++, Java nebo Python. Každou úlohu můžete odevzdat v jiném programovacím jazyce. U testů je řešení konfrontováno s referenčním řešením ve stejném programovacím jazyce. Přesto doporučujeme přemýšlet nad výběrem programovacího jazyka podle typu úlohy.

Podle zadání je nutné odevzdat řešení v jednom souboru s daným názvem.

Řešení čte vstup vždy ze standardního vstupu (stdin) a výsledky vypisuje na standardní výstup (stdout) nebo v případě chyby na standardní chybový výstup (stderr). Součástí implementace řešení je čtení a výpis dat podle zadání. Odevzdáváte zdrojový kód, který je podle zvoleného jazyka (C/C++, Python, Java) přeložen a následně spuštěn s tím, že řeší úlohu podle zadání.

Pro testování úloh jsou připravené testovací vstupy uložené v souborech. Při testování řešení jsou data ze souboru posílána na standardní vstup a kontrolován je standardní výstup. Důvodem je správné čtení vstupu a také jeho časová složitost, která může mnohdy významně ovlivnit celkovou složitost řešení. To stejné platí o výstupu programu a výpisu výsledků.

Jednotlivé testy mají své jméno. To je využito jednak v popisech testovacích vstupů a rovněž ve výpisech z odevzdávacího systému. Veřejné testovací vstupy jsou připravené ke stažení v souborech, jejichž název odpovídá názvu testu s příponou “.in”.

Obecné principy hodnocení

Úlohy jsou členěny na části, které jsou hodnoceny samostatně - podle popisu v zadání úlohy. Celkem lze za řešení úlohy získat až 10 bodů.

Úloha je uznána jako splněna, pokud za ní získáte alespoň na 5 bodů. Takové řešení zahrnuje základní funkcionalitu programu, tj. načtení vstupu, výpis výsledků a základní algoritmus úlohy, který je funkční na “menších” vstupech.

Dalších pět bodů je možné získat za řešení, které zahrnuje optimalizaci, ať již časovou nebo prostorovou. Počítáme, že takové řešení je nutné více testovat a ladit, kontrolovat jeho funkčnost s referenčním řešením. Povoleno je proto až 20 uploadů bez penalizace. Přesto doporučujeme základní část řešení testovat na počítači pomocí dostupných vstupních dat a uploady využít spíše k testování optimálního řešení.

Nenechte se zmást počtem uploadů, který ukazuje BRUTE. Penalizaci za překročení limitu uploadů řídí přímo evaluační skript.

Penalizace je po překročení limitu 20 uploadů řízená vztahem $ points = points_{max} \cdot \frac{20}{uploads_{num}} $.

Kromě penalizace za překročení povoleného počtu uploadů systém uděluje penalizaci i za pozdní odevzdání úlohy.

Testy na “velkých” datech jsou často generovány náhodně, výsledky hodnocení se v BRUTE zobrazují pouze orientačně.

Technické informace o odevzdávacím systému

Operační systém (lsb_release -da)

Distributor ID:	Debian
Description:	Debian GNU/Linux 11 (bullseye)
Release:	11
Codename:	bullseye

Jazyk C/C++

Použitý kompilátor (clang –version)

Debian clang version 11.0.1-2
Target: x86_64-pc-linux-gnu
Thread model: posix

Jazyk Python

Verze (python3 –version)

Python 3.9.2

Jazyk Java

Použitý kompilátor (javac -version)

javac 16.0.2

Verze (java -version)

java version "16.0.2" 2021-07-20
Java(TM) SE Runtime Environment (build 16.0.2+7-67)
Java HotSpot(TM) 64-Bit Server VM (build 16.0.2+7-67, mixed mode, sharing)

Technické parametry odevzdávacího systému jsou dány pluginy instalovanými v BRUTE a nelze je ovlivnit.

courses/b6b36dsa/ukoly/start.txt · Last modified: 2024/02/09 13:15 by nagyoing