Miloš Chromý

Studijní texty

Podmínky zápočtu

• Na každém cvičení bude zadána sada úkolů, ze kterých si jeden vyberte a vyřešte. Vyhotovený úkol musíte odevzdat do začátku dalšího cvičení.
• Za úkol je možné získat maximálně 5 bodů. V rámci jedné sady je možné dostat též 5 bodů (i když vyřešíte víc úkolů z dané sady).
• Zápočet je možné dostat za 3/5 z celkového množství bodů.
• Úkoly odevzdávejte buď na začátku dalšího cvičení nebo na mail. V mailu založte nové vlákno s názvem ADS1 a všechny úkoly pište jako odpověď na tento mail. Ideální text v samotném těle mailu nebo pdf (třeba vysázené v $\LaTeX u$. Pokud začínáte s $\LaTeX$em pak zkuste wysiwyg editor LyX. Na obrázky se dá použít balíček tikz který má i nějaká grafická udělátka.) Další možností je word(libre, microsoft, open). Ve vyjímečných případech přijmu i naskenovaný/nafocený úkol.

Aplikace ADS a další zajímavosti:

• Google CodeJam
• FB Hackers Cup
• Google Hash code

• Top Coder
• Code Wars
• Code Forces
• Timus

• IPS I a IPS II
• Kombinatorický seminář
• Filosofické problémy informatiky
• KAM úmluva kde se můžete dozvědět o spoustě zajimavých předmětech vyučovaných v daném semestru. Probíhá vždy na začátku semestru (1. týden)

Přůběh cvičení

18.2.2020 Notace $O,o,\Omega,\omega,\Theta$.

Podmínky zápočtu a organizace cvičení.
Vajíčka a 100 pater mrakodrapu. 1,2,100 vajec. Hledáme patro kde se rozbije a kolik potřebujeme hodů.
Podposloupnost s nejvyšším součtem.
Definice.

25.2.2020 Složitost 2.0

PDF s příkladama: tady
Příklady algoritmů k jednotlivým třídám ($\Theta(1),\Theta(\log n),\ldots,\Theta(n^c),\Theta(2^n)$).
Porovnávání dvojic funkcí
Důkaz/vyvrácení jednoduchých tvrzení.
RAM
K zamyšlení: Algoritmus se složitostí $O(n^c)$ pro různá $c$. Co nejlepší odhad $\log_n n$.

3.3.2020 BFS a DFS

PDF s příkladma: tady
BFS - hledání nejkratších cest v neohodnocených grafech a v grafech ohodnocenými malou konstantou. BFS na implicitním grafu (příklad 1a-1c z pdfka).
DFS - příklady 3 a 4. Strom prohledávání.
Pomocná paměť na DFS a BFS.

10.3.2020 Orientované grafy, DAG atp.

PDF s příkladma: tady
Příklady 1-3. Mosty, topologické číslování, kritické cesty.

17.3.2020 Korona

PDF s příkladma: tady
Djikstra, bellman-ford. Příklady 1-3.

24.3.2020 KaraNETa

PDF s příkladma: tady
Floyd-Warshall. Záporné hrany. Kostry. Příklady 1.,2.,3.,4.,5a).

31.3.2020 Počty pošty

PDF s příkladma: tady
Binární vyhledávací stromy. AVL stromy. Příklady 1.,2.,3.,4.,8.

7.4.2020 $(m,c)$-stromy

PDF s příkladma: tady
Příklady 1 a 3.

14.4.2020 Amor tizace

PDF s příkladma: tady
Praktický příklad amortizace hackmd.io
Příklady 1.4.6.7.

21.4.2020 Hashujeme

PDF s příkladma: tady
Příklady 1.2.3.4.7.

21.4.2020 Rozděl a panuj

PDF s příkladma: tady
Příklady 1.2. a 3.

21.4.2020 Quick...

PDF s příkladma: tady
př. 0: navrhněte implementaci quickselect s konstatním prostorem. Př 1.2.4(pro trojice)6.

21.4.2020 ...and dynamic

PDF s příkladma: tady
Příklady 1.-5.

Úkoly

1. Úkol (do 25.2.2020 15:41)

Počátek.řešení, pseudokód, časová složitost, správnost. Vybeřešte jeden ze tří.
1. Na vstupu je text složený z písmen české abecedy a mezer. Navrhněte algoritmus, který najde nejkratší úsek, který obsahuje všechna písmena abecedy (nerozlišujeme velká a malá písmena).
2. Na vstupu je text složený z písmen české abecedy a mezer. Navrhněte algoritmus, který najde nejdelší úsek, ve kterém se žádné písmeno neopakuje.
3. Pro posloupnost čísel $x_1,\ldots, x_n$ a číslo $S$ najděte dvojici indexů $i,j$ takovou, že $S=x_i+x_j$.

2. Úkol (do 3.3.2020 15:41)

Složitost 2.0
1.Dopočítejte konstanty $c_1,c_2,n_0$ pro $f(n)=\Theta(g(n))$ kde $f(n)=1/2n^3+15n^2-12n+5$.
2.Dokažte nebo vyvraťte: $f(n)=\Theta (h(n))\wedge g(n)=\Theta(i(n))\implies f(n)+g(n)\in\Theta(h(n)+i(n))$
3.Dokažte nebo vyvraťte $2^{O(\log n)}=O(n)$.
4. Dokažte $f\in \Theta(h)\wedge g\in o(f)\implies f+g\in\Theta(f)$.

3. Úkol (do 10.3.2020 15:41)

Pseudokód, prostrová a časová složitost, slovní popis řešení, důkaz správnosti.
1. Nejkratší objížďka.(4. př 2. stránka z cvičení.) Pro neorientovaný graf $G$ a hranu $e$ nalezněte nejkratší cyklus obsahující hranu $e$.
2. Cyklus? Tady je. Popište algoritmus, který v lineárním čase ($O(n+m)$) detekuje libovolný cyklus v grafu a vypíše ho.
3. Theseus a Minotaur.(5. př 1. stránka z cvičení.) Hrdina Théseus se vypravil do hlubin labyrintu a snaží se najít poklad. Chodbami labyrintu se ovšem pohybuje hladový Mínótauros a snaží se najít Thésea. Labyrint má tvar čtvercové sítě, jejíž každé políčko je buďto volné prostranství, anebo zeď. Známe mapu labyrintu a počáteční polohy Thésea, Mínótaura a pokladu. Théseus se v jednom tahu pohne na vybrané sousední políčko. Poté se vždy dvakrát pohne o políčko Mínótauros: pokaždé se pokusí zmenšit o 1 rozdíl své a Théseovy $x$-ové souřadnice, pokud to nejde, pak $y$-ové, pokud nejde ani to, stojí. Poraďte Théseovi, jak má dojít k pokladu a vyhnout se Mínótaurovi.
4. Robotická dvojčata.(6. př 2. stránka nahoře z cvičení.)Máme dvě bludiště a v každém se nachází jeden robot na dálkové ovládání. Bohužel máme rozbitý ovladač, takže můžeme dávat jen příkazy kterým směrem mají jet (S,J,V,Z). Jak najít nejkratší sekvenci pro jejich osvobození?

4. Úkol (do 24.3.2020 15:41)

Pseudokód, prostorová a časová složitost, popis a důkaz správnosti.
Úkoly z příkladů.:
Příklad 4. DU v čase $O(m+n)$.
Příklad 5. Bosa PRA v čase $O(n)$.
Příklad 8. Počet všech cest. v čase $O(n+m)$.
Příklad 10. Hodně cest. Tady stačí příklad s důkazem počtu cest.

5. Úkol (do 31.3.2020 15:41)

Pseduokód, popis řešení, důkaz správnosti, časová a prostorová složitost
Úkoly z příkladů.:
Příklad 2.(c) DU.
Příklad 3. Nejen nalezení, ale i výpis libovolného záporného cyklu. (Pozor na dosažitelnost.)
Příklad 4.(b)
Příklad 5.

6.úkol (do 7.4.2020 15:41)

Pseduokód, popis řešení, důkaz správnosti, časová a prostorová složitost. Z pdf tady
Příklad číslo 5(b) a 5(c) (oba dva).
Příklad číslo 6 Revoluce u Bobří řeky.
Příklad číslo 7 Borůvka progresivní suterén.
Příklad číslo 8 Borůvková marmeláda.

7.úkol (do 14.4.2020 15:41)

Pseduokód, popis řešení, důkaz správnosti, časová a prostorová složitost. Z pdf tady
Příklad číslo 6 Klátící korona.
Příklad číslo 7 Zrychlování.
Příklad číslo 9 Korupce za časů korony.
Příklad číslo 10 Maxima.

8.úkol (do 21.4.2020 15:41)

Pseduokód, popis řešení, důkaz správnosti, časová a prostorová složitost. Z pdf tady
Příklad 2 Průmět. (modifikace AVL stromu)
Příklad 3 $(a,b)$-stromy. Udělejte jen preemptivní delete pro B-stromy, což jsou $(a,b)$-stromy pro $b=2a$, tedy delete, který se nevrací z listů do kořene, ale provede úpravy už při cestě do listu tak, aby i po smazání prvku byl strom validní (splňoval definici B-stromů).
Příklad 7 Minimový strom.

9.úkol (do 28.4.2020 15:41)

Pseduokód, popis řešení, důkaz správnosti, časová a prostorová složitost. Z pdf tady
Příklad 2. Split. Časová složitost $O(\log n)$
Příklad 3. Prázdná paměť.
Příklad 5. Přičítání jedničky 3.
Příklad 8. Arnold Schwarzeneger.

10.úkol (do 5.5.2020 15:41)

Pseduokód, popis řešení, důkaz správnosti, časová a prostorová složitost. Z pdf tady
Příklad 5. Palin d’romatik
Příklad 6. Zapomnětlivý Karel.

11.úkol (do 12.5.2020 15:41)

Vše jako vždy. Pokud si nejse jisti, ptejte se na mailu nebo discoord. Pořadí úkolů nemusí odpovídat jejich obtížnosti. Z pdf tady
Příklad 4. KA.3
Příklad 5. KA patch
Příklad 7. Jedlík.2
Příklad 8. Kuchaři

Bonus úkol (18.5.2020 15:41)

Z pdf: tady
Příklad 3. Skoroskoromedián.
Příklad 4. Lineární k-select. Verze rozdělení na sedmice.
Příklad 5. Medián dvou.
Příklad 7. Šroubky a matičky.