Zápis cvičení

14.5.

Třídění pdf.

Domácí úkoly: Bez rekurze (6 bodů) -- jeden programovací úkol, hodnotit se bude i čitelnost kódu

7.5.

Pokračování v příkladech na rekurence pdf.

Domácí úkoly: Kabel (6 bodů) -- deadline 21.5.

30.4.

Rozebírání DÚ, dokončování stromů, začátek rekurencí pdf.

Domácí úkoly: Žádnéi - dokončete opravy předchozích domácích úkolů

23.4. (záskok Radek Hušek)

Stromy, příklady z pdf.

Domrácí úkoly: Rozdělení BVS (6 bodů)

16.4.

Pokračování příkladů na kostry z pdf.

Domácí úkoly: Příklad 10b (6 bodů)

9.4.

Dokončení nejkratších cest a začátek koster, příklady 1-5 pdf.

Domácí úkoly: Internet (7 bodů) - deadline bude prodloužen o týden, protože jsme z koster udělali méně než bylo v plánu. Ale i další týden bude úkol.

2.4.

Velikonoční prázdniny

26.3.

Nejkratší cesty v grafech, příklady 1,2,3,4,6 z následujícího pdf.

Domácí úkoly: Lupiči (6 bodů)

19.3.

Pokračování BFS, DFS příklady 1-4 z pdf.

Domácí úkoly: Roboti v bludišti (6 bodů)

12.3.

Reprezentace grafů a BFS, DFS 1,2,4,9 z pdf.

Domácí úkoly: Bludiště (6 bodů) -- Upřesnění: dveře a klíče jsou barevné (o každém klíči víme, ke kterým dveřim patří a opačně o každých dveřích víme, který klíč jim odpovídá. Berte k jako konstantu, ne součást vstupu.

5.3.

RAM, příklady 2,3,4,6 a část 1 z pdf.

Domácí úkoly: Rozmyslet si konstrukce z programovacích jazyků na RAMu (8 bodů)

26.2.

Asymptotická složitost - pokračování v příkladech z minula pdf.

Domácí úkoly: Asymptotické vztahy (2*3 body) -- překlep v zadání, máte určit asymptotické vztahy mezi funkcemi v případě (a) a třídami funkcí v případě (b)

19.2.

Motivační příklady, od triviálního pomalého k rychlejším řešením, definice O. Příklady 1,2,3 z pdf.

Domácí úkoly: Hledání nejdelší posloupnosti s omezeným rozdílem prvků (4 body) a mocnina matice (3 body)

Výsledky domácích úkolů.

Výsledky zveřejňuji jen pod přezdívkou. Pokud ji nemám, nezveřejňuji. Přezdívku mi můžete poslat mailem.

Zkontrolujte si prosím, že máte v tabulce správné body, odpověď byste měli mít ke všem úkolům odevzdaným před nedělí 6.5.

Stránka s body

Podmínky zápočtu

Výsledky zveřejňuji jen pod přezdívkou. Defaultní přezdívou je prázdný string. Jinak mi přezdívku můžete poslat mailem.

K udělení zápočtu je potřeba získat alespoň 2/3 bodů z domácích úkolů.

Co musí obsahovat správný domácí úkol

Slovně popsaný postup řešení

Pseudokód (v první polovině semestru vyžadován, později volitelný, ale doporučený)

Zdůvodnění správnosti algoritmu

Časová složitost a její zdůvodnění

Prostorová složitost (paměťová náročnost) a její zdůvodnění

• Užitečné odkazy

• Stránka přednášky
• Videa přednášek z MFF. Přihlašujte se loginem (jménem) do sisu. Obsahuje také přednášku ADS I (jiný link) od Martina Mareše.
• Algovize a kniha prof. Kučery.
• Skripta Martina Mareše.
• Přednáška Martina Mareše o dalších grafových algoritmech.
• Zjistěte, kde všude se využívají algoritmy, které se zde učíme (budete překvapeni) CS Theory StackExchange.
• Koukněte se, jak vypadá interview například u Google (anglicky). Zejména doporučuji komentář na konci!
• Pro zvídavé studenty: IPS
• Kombinatorický seminář je určen primárně studentům od druhého ročníku bakalářského studia. Ale pokud máte rádi kombinatoriku a chcete se dozvědět spoustu zajímavostí z hezkých článků a nebo si i nějaký referovat, tak se nebojte přijít.
• Zajímavý pokus o interaktivní učení: http://tutor.fi.muni.cz/. Po přihlášení zde jsou dostupné interaktivní příklady na lineární zobrazení v rovině (a také afinní zobrazení). Obsahuje celou řadu dalších typů úloh. Přihlášením podporujete výzkum učení!
• Jestli se chcete naučit psát hezky matematiku, zkuste se podívat na LaTeX. Pro kreslení obrázků se bude hodit například program ipe. LaTeX můžete psát i online například na sharelatex. V případě zájmu vytvořím nějaký ukázkový soubor.