MK's wiki

Uživatelské nástroje

Nástroje pro tento web

Historie: • ads12021_cviceni
teaching:ads12021_cviceni

Obsah

Cvičení z ADS1 2020/21

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

Zadání úloh na cvičení i domácích úkolů bude v zde na webu. Pro komunikaci kolem DÚ budu používat systém OWL. Pokud vám do něj nepřišel ode mě kód, napište mi email.

Při emailové komunikaci se mnou prosím vždy uveďte do předmětu text [ADS1].

Co se dělalo na cvičení

Užitečné zdroje

Požadavky na zápočet

Zápočet vám udělím, získáte-li celkově 100 bodů. Váš aktuální počet bodů uvidíte v OWLu.

Body lze získávat následujícími způsoby:

  • Řešení úkolů: celkově zadám úlohy za cca 100 bodů. Každý úkol má termín, typicky dva týdny, pak klesnou body na polovinu. Úlohy budou rozděleny do skupin označených písmeny a z každé skupiny chci, abyste vypracovali aspoň jeden úkol. Více o vypracovávání domácích úloh…
  • Opravování úkolů: pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, máte možnost získat navíc až pětinásobek bodů tím, že se stanete korektorem pro tuto úlohu. Přesný počet bodů je dán vzorcem $r \cdot b/5$, kde $b$ je počet bodů za úlohu a $r$ je počet řešení, které opravíte, tedy např. pokud je úloha za 6 bodů a opravíte ji 10 kolegům, dostanete $10 \cdot 6/5 = 12$ bodů. Korektorem se můžete stát max. třikrát za semestr. Více o korektorství…
  • Zápočťák: body můžete získat taky za zápočtový projekt, který může být praktický (implementace algoritmu) či teoretický (popis a analýza nějakého složitějšího algoritmu). Více o zápočťácích…

Domácí úkoly

Další informace

Vypracovávání domácích úloh

  • Úkoly odevzdávejte pouze elektronicky přes OWL a to buď jako prostý text, markdown s matematikou (nejlepší varianta), nebo PDF soubor. PDFko může být vytvořené z prostého textového dokumentu, MS Wordu, LibreOffice Writeru, vysázeno (La)TeXem , nebo to může být i dobře čitelný scan nebo fotka (použijte appku Office Lens (iOS, Android) nebo podobnou, zejména chcete-li ilustrovat řešení obrázkem.)
  • Pokud není řečeno jinak, vyřešením úlohy myslím, že dokážete dané tvrzení.
  • Důkaz musí být korektní, přehledný a srozumitelný.
  • V důkazu smíte používat bez důkazu tvrzení z přednášek.
  • 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).
  • Za dobré (korektní, přehledné, srozumitelné) řešení příkladu dostanete plný počet bodů. Pokud něco chybí, ale důkaz obsahuje dobrou myšlenku, nebo pokud je důkaz správný, ale nepřehledný či nesrozumitelný, dostanete přibližně poloviční počet bodů. Pokud úlohu nevyřešíte nebo je důkaz zcela špatně (včetně myšlenky), dostanete 0 bodů.
  • Silně doporučuji naučit se používat základy sazby matematiky pomocí systému LaTeX. Asi jako nejlepší zdroj se mi osvědčila wikikniha o LaTeXu. Nejjednoduší způsob, jak se do toho pustit, je přímo v OWLu (funkce preview) nebo v hackmd.io, kde můžete vidět živý náhled po straně se zdrojem (malá ukázka syntaxe (klikněte na „edit“, abyste viděli kód.)) Případně můžete používat nějaký webový LaTeXový editor (rozchodit LaTeX na vlastním počítači může být oříšek) – např. Overleaf.
  • Při řešení úkolů doporučuji spolupráci, 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, ale řešení jste opsali, a mé podezření se potvrdí, nedostanete žádné body a příště budu do vašich úkolů obzvlášť šťourat (abych si byl jistý, že jste je pochopili).

Korektorství

Pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, po odevzdání úlohy mi napište email s předmětem [DM/ADS1/KG1][korektor] název-úlohy (první část podle předmětu, vyberte samozřejmě jen jedno). Já vaše řešení zhodnotím přednostně a pokud bude v pořádku, za opravení řešení vašich kolegů navíc až pětinásobek bodů. Přesný počet bodů je dán vzorcem $r \cdot b/5$, kde $b$ je počet bodů za úlohu a $r$ je počet řešení, které opravíte, tedy např. pokud je úloha za 6 bodů a opravíte ji 10 kolegům, dostanete $10 \cdot 6/5 = 12$ bodů. Korektorem se můžete stát max. třikrát za semestr.

Technicky to bude fungovat tak, že korektorovi zpřístupním danou úlohu v OWL, kde on opravuje a uděluje body, ale já vše taky vidím a můžu případně korigovat :) Korektor si tedy řešení pečlivě přečte a zhodnotí ho. Je toto řešení korektní? Pokud ne, kde udělal autor chybu? Čemu nerozumí a jak mu můžu pomoci – jakou otázkou ho nakopnu správným směrem? Dále – je toto řešení přehledné a srozumitelné? Prospělo by řešení rozdělit do více/méně odstavců? Zavést nějaké značení? Atd. Na základě tohoto zhodnocení pak korektor navrhne bodové ohodnocení. Například:

Řešení je v zásadě správné, ale doporučil bych místo značení A, B, C, … používat indexované značení A_1, A_2, A_3, … Jinak byl důkaz poměrně přehledný.

2b

Já zhodnotím řešení úlohy a korekturu, případně se k oběma vyjádřím a přehodnotím body (ale to se často neděje).

Povinností korektora je opravit všechny přidělené úlohy do týdne od chvíle, kdy se v OWLu objeví.

Jak zápočťáky fungují

Zápočtová práce může mít podobu:

  1. programu implementující nějaký algoritmus z přednášky,
  2. teoretického rozboru algoritmu, který vás zaujme.

V prvním případě jde o implementaci nějaké varianty datové struktury či algoritmu z přednášky. Jazyk je omezen jen schopnostmi cvičícího (tedy [v pořadí preferencí] Python, Lua, Java, C#, hezké C, Pascal, Haskell, Lisp, Prolog,; na další se případně zeptejte), implementace musí být funkční a obsahovat krátký popis (co a jak je implementováno) a testovací data či testovací kód (knihovna tedy nemusí řešit načítání dat ze souboru a pod.). Za tento druh práce budu udělovat max. 30b, pokud se bude jednat o něco velmi jednoduchého, bodů bude méně. Zeptejte se předem, kolik lze za dané téma očekávat nejvýše bodů.

V druhém případě, tedy zejména pokud bude algoritmus či datová struktura složitější, bude práce jen teoretická, tzn. očekávám důkaz správnosti, rozbor složitosti a pseudokód. Za tento druh práce můžete očekávat do 40b, to zejména v případě, kdy si vyberete nějaký akademický článek a převyprávíte ho do mně (nezasvěcenému) srozumitelné podoby. Opět platí, že půjde-li o něco velmi jednoduchého, bodů bude méně. Zeptejte se předem, kolik lze za dané téma očekávat nejvýše bodů.

Termín na domluvení programu je do 15. června, termín odevzdání hotové verze pak konec června. Ostatní domácí úlohy mají až na výjimky termín do konce května.

Nápady na zápočťáky

  • Implementovat R-B-stromy a (2,4)-stromy a graficky ukazovat jejich korespondenci. Za prostou implementaci datové struktury dám 30b, pokud vytvoříte interaktivní aplikaci, ve které bude uživatel zadávat operace na stromech a aplikace bude zobrazovat změny datových struktur a jejich korespondenci, dám 40b. Zcela ideální platformou by byl (kvůli přístupnosti) Javascript nebo cokoliv webového; přijmu to ale i v jakémkoliv jiném (výše zmíněném) jazyce. Řešení Petra Mánka. Řešení Honzy Kytky.
  • Shellsort je velice zajímavý třídící algoritmus. Je v jistém smyslu zkřížením bubblesortu a insertsortu, ale může mít lepší časovou složitost. Možností, co byste s ním mohli dělat, je několik:
    • Implementovat ho pro několik variant parametru mezery (Gap sequences) a porovnat jeho chování pro tyto parametry experimentálně. (Hotovo, github)
    • Nejlepší posloupnost mezer v průměrném případě je prý 1, 4, 10, 23, … (vizte poslední odstavec této podkapitoly); toto bylo zjištěno experimentálně. Ověřte správnost těchto výsledků pro co největší čísla (aktuálně je známo jen prvních osm členů této posloupnosti, kdybyste přišli na devátý, dostanete celý zápočet ;). Pokud byste si vybrali toto témai, jistě by nebylo těžké vám zařídit přístup k výpočetní kapacitě fakulty.)
    • Co kdyby se měl Shellsort přednášet? Sestavte co nejzajímavěji materiál k výkladu na hodinu a půl (jako přednáška z ADS), kde se ukáže princip fungování tohoto sortu a pak dokáže několik (jednodušších) odhadů na časovou složitost pro různé hodnoty parametru mezery. Nejvhodnějším médiem by byl IPython notebook (rád předvedu, jak funguje), protože do něj lze psát matematickou notaci i kód a interaktivně vše zkoušet.
  • Splay tree je velice zajímavá datová struktura. Jedná se o binární vyhledávací strom, který se přizpůsobuje dotazům, které na něj přichází – pokud přichází mnoho dotazů na tytéž prvky, strom je vynese blízko ke kořeni, aby se k nim dalo přistupovat rychle. Samozřejmě má i svoje nevýhody. Implementujte ho a napište k němu několik generátorů posloupnosti operací, které budou demonstrovat, v čem je Splay strom lepší než jiné stromy (AVL, R-B, …) a kde naopak selhává. (Generátorem posloupnosti operací myslím nějakou funkci, které řeknu, kolik operací INSERT/FIND/DELETE chci na stromu udělat [třeba za účelem testování] a on mi je vygeneruje.)
  • Implementujte Rabinův-Karpův algoritmus na vyhledávání podřetězce v řetězci pomocí hashování.
  • Implementujte kterýkoliv exponenciální algoritmus z přednáškových poznámek Jeffa Ericksona a pochopte důkaz správnosti a časové/prostorové složitosti dostatečně, abyste mi ho uměli vysvětlit na tabuli.
  • Implementujte algoritmus, který najde modulární rozklad grafu v lineárním čase dle článku Linear-time modular decomposition of directed graphs. Pokud úkol splníte, dám za něj 45b (+5b za prezentaci); i pokud se vám to nepodaří úplně, nebude bodová odměna malá. (Potenciálně je to taky dobrý základ pro ročníkový projekt nebo bakalářskou práci do příštích let.)

Hotové

Články k rozebrání

Obecně je dobrým zdrojem konference SOSA, která se soustřeďuje na *hezké* (jednoduché) algoritmy, ačkoliv i tak mohou být přístupné spíš magisterským studentům.

teaching/ads12021_cviceni.txt · Poslední úprava: 2021/05/31 12:13 autor: Martin Koutecky