Pravidla cvičení z Datových struktur 1
Převzato ze stránek Martina Mareše a upraveno.
Struktura předmětu
K předmětu patří přednášky a cvičení.
Ke splnění předmětu je potřeba složit zkoušku (ústní
zkouška s písemnou přípravou, pokrývá teorii z přednášky)
a získat zápočet z cvičení.
Předpokládáme následující znalosti
- Programování (v rozsahu základního kursu)
- Základní algoritmy a datové struktury (např. vyvažované binární
vyhledávací stromy)
- Diskrétní matematika (kombinatorika, základy teorie čísel)
- Základy teorie pravděpodobnosti (linearita střední hodnoty, …)
Pokud v čemkoliv z tohoto máte mezery, ozvěte se prosím brzy.
Doporučíme vhodné materiály k doplnění znalostí.
Úkoly
Požadavky:
- Zadáme
- alespoň 8 programovacích úkolů po 10 bodech a
- alespoň 4 experimentální po 15 bodech.
- Na zápočet je potřeba získat aspoň 90 bodů.
- Termín: 2 týdny od zadání (více ke konci semestru)
Programovací úkoly:
- Dostanete částečnou implementaci datové struktury.
- Máte za úkol implementovat chybějící části. Původní části můžete upravovat.
- Úkol je nejprve testován automaticky, testovací data jsou veřejná.
- Cvičící si prohlédne váš program a případně koriguje bodové ohodnocení.
- Automatické testy ověřují jen základní funkčnost, konečné hodnocení se může výrazně lišit.
- Lze řešit v C++ a (obvykle) také v Pythonu.
Experimentální úkoly
- Cílem je změřit chování zadané implementace.
- Odevzdáváte zprávu s naměřenými hodnotami a diskusí (jako PDF).
- Snažte se výsledky zdůvodnit teorií z přednášek.
Všeobecná pravidla
- O úkolech můžete diskutovat s ostatními, ale nesdílejte s nimi
své programy ani zprávy (ukázat je přednášejícímu nebo cvičícímu
samozřejmě můžete).
- Nesdílejte vzorová řešení úkolů s lidmi mimo vaši skupinu.
- Termíny jsou pevné.
- Před termínem můžete své řešení odevzdávat vícekrát, platí maximum
získaných bodů.
- Program musí projít všemi testy.
- Kvalita vašich programů a zpráv se promítá do hodnocení.
- V programovacích úkolech nepoužívejte netriviální kód, který jste nenapsali sami.
To zahrnuje cizí implementace datových struktur a jiné než zřejmé knihovní funkce.
Základní použití natahovacích polí (vkládání na konec
std::vector
v C++ nebo list.append()
v Pythonu) je povoleno,
nic složitějšího už ne.
Pokud si nejste jistí, poraďte se s cvičícím.
- Předchozí pravidlo zahrnuje také kód stažený z internetu, např. ze StackOverflow.
Zjistit si, jak se používají základní knihovní funkce, je nejspíš v pohodě.
Pro informace k implementaci konkrétní datové struktury použijte poznámky z přednášky.
- Pokud jste se kdekoliv inspirovali, citujte všechny zdroje.
Chybějící citace jsou (nejen zde) považovány za významný prohřešek proti akademické etice.
- Pokud se rozhodnete použít jinou verzi datové struktury, než zazněla
na přednášce, čeká se od vás důkaz, že také má požadované vlastnosti.