Cvičení z algoritmů a datových struktur 2014/15

Na pravé straně této stránky vizte obsah. Silně doporučuji pečlivě vše pročíst.

Paralelní cvičení vedou mimo jiné Pavel Veselý (cviko z roku 2012/13) a Karel Tesař.

Co se dělalo na cvičení

Co se dělalo na cvičení bude vždy reflektováno i v základní mapě; i zde však budu pro rychlou přístupnost dávat PDFka ze cvičení.

Obsah cvičení.

V malých týmech (3-4 lidé) vytváříte mapu pojmů z ADS, zakreslujete do ní úlohy a jejich řešení.
V pondělí po přednášce přidám zadám úlohy; vy budete hlasovat, kterými se chcete nejvíc zabývat na cvičení.
Nabízím (a doporučuji) možnost pravidelných konzultací s týmy, osobně či přes skype. Během konzultace bych s vámi prošel vaši mapu a řekl své připomínky k jejímu rozvržení a vašim řešením úloh.
Na začátku cvičení budeme psát bleskové písemky, abyste měli přehled o tom, čemu rozumíte a čemu ne.

Podmínky zápočtu.

Zápočet dostane tým za odevzdání dobré mapy; ta splňuje následující:

Mapa je přehledná, obsahuje všechny základní pojmy (ty zavádím já) a všechny úlohy. Též obsahuje řešení úloh, každé s vaším ohodnocením (0-10), jak kvalitní je.
Úlohy jsou členěny do skupin (sloupce úloh), z každé skupiny musíte získat alespoň tolik bodů, kolik je na šipkách k dané skupině vedoucích
- Příklad: k prvním dvěma úlohám „Jak tvrdé je vajíčko (2)“ a „Největší díra v matici (4)“ vedou šipky s popiskem „4“, což znamená, že za tyto dvě úlohy musíte v součtu získat alespoň 4 body.
- Body získané za úlohu = náročnost úlohy × kvalita řešení; v příkladu výše to znamená např. vyřešit úlohu „Největší díra v matici“ s maximální kvalitou (10), nebo tutéž úlohu s kvalitou 7 a navíc první úlohu s kvalitou 6.
Každý člen skupiny přispěl alespoň 20% vašeho skóre.
Mapu jako skupina obhájíte: předvedete mi některá řešení, která jste označili za kvalitní, a já vám vysvětlím řešení některých úloh, které jste nezvládli vyřešit, čímž si ověřim, čemu rozumíte.
Zápočet není za: prezenci, bleskové písemky, aktivitu ve cvičení atd.

Technické řešení

Pište mi na koutecky@kam.mff.cuni.cz, předmět mailu začněte [ADS1_2015].
Mapy budeme vytvářet na serveru http://metamaps.cc a budou veřejné (na škále metamaps oprávnění PR-PU-CO zvolte PU = public; všichni vidí, jen vy můžete upravovat.) Jak pracovat s metamaps — rychlý úvod.
Úlohy
- Jako řešení úlohy dáte do své mapy odkaz na co nejkvalitnější text (viz další bod)
- Hodnocení: Úlohy hodnoťte pomocí následující škály. Řešení je kvalitní a zasluhuje nejvyšší hodnocení (10), je-li korektní, přehledné, srozumitelné. Řešení je polovičaté a zasluhuje hodnocení 5, pokud něco chybí, ale řešení (návrh algoritmu, důkaz správnosti, důkaz časové složitosti) obsahuje správnou myšlenku, nebo pokud jste přesvědčeni, že řešení je správné, ale nepřehledné či nesrozumitelné. Řešení je nanicovaté a zasluhuje hodnocení 0, pokud neexistuje či je špatně.
  - Tip: Pokud se začnete ve formulacích zamotávat, zaveďte si značení. Označte objekty nebo kvantity přesnými názvy nebo proměnnými a v textu používejte tyto proměnné, nikoliv ukazovací zájmena. (Je častá chyba, že autor důkazu mluví o té a tamté množině a cvičící je v okamžiku ztracen. Proč ne množina $A$ a množina $B$?). V prostém textu dolní index označujte pomocí podtržítka (tzn. $a_1$ je a_1), horní pomocí stříšky ($a^2$ je a^2).
- Formáty řešení (v pořadí dle mé preference)
  - Text ve formátu Markdown s matematikou v TeXu; viz např. Mathb.in tutorial
  - PDF vygenerované pomocí sázecího systému LaTeX (jako referenci doporučuji wikiknihu o LaTeXu)
  - PDF vygenerované jiným editorem (LibreOffice Writer, MS Word atd.)
  - Nascanované řešení čitelně psané rukou, v PDF.
- Technické řešení odevzdávání úloh
  - Ve své mapě vytvoříte nový uzel se jménem „Řešení: [název úlohy]“, který napojíte na danou úlohu a který bude obsahovat odkaz na řešení úlohy.
  - Protože všechna řešení musí být neveřejná, odkaz povede buď na zaheslovanou instanci softwaru mathb.in běžící na mém serveru (každá skupina dostane heslo), nebo na OwnCloud běžící na mém serveru, kde můžete jak vkládat řešení v PDF, tak psát v MarkDownu s TeXem (každá skupina dostane heslo). Alternativně (pokud se na tom jako tým shodnete) můžete používat platformu Google Drive nebo DropBox a řešení tam mít v PDF, nebo v MD+TeX pomocí editoru Stackedit.io.
Při řešení úkolů můžete spolupracovat (zejména v týmech to očekávám), ALE:
- Vždy doporučuji, abyste příklad nejdřív zkusili vyřešit sami, více se toho naučíte.
- Přestože jste na úkolu s někým spolupracovali, musíte řešení vypracovat a zformulovat sami. Pokud ve mně vaše řešení vzbudí podezření, že příkladu vlastně nerozumíte na úrovni (0-10), na jaké jste ho ohodnotili, a mé podezření se potvrdí, nedostanete žádné body a do vašich dalších úkolů budu obzvlášť šťourat (abych si byl jistý, že jste je pochopili).

Rozcestník

Pro rychlé nalezení potřebného odkazu:

Metamaps.cc, Základní mapa pojmů a úloh
OwnCloud @ koutecky.name (možná vyhodí varování o bezpečnostním certifikátu, ten přijměte) (o heslo mi napište)
Mathb.in @ koutecky.name veřejný mathbin (o heslo do soukromého mi napište)
Jak pracovat s metamaps — rychlý úvod