Záznam z 28. května
Opakovvání a shrnutí prohledávání grafu do šířky (BFS -- breadth first search) a do hloubky (DFS -- depth first search) a fronty (FIFO -- first in first out) a zásobníku (LIFO -- last in first out). Zaměřili jsme se na to, jak fungují a rozebírali konkrétní implementace.
Shrňme jejich použití: obě, tedy BFS i DFS lze použít k nalezení komponenty grafu (tj. vrcholů, které lze navzájem spojit cestou), BFS jsme používali k nalezení nejkratší cesty, DFS k nalezení jakékoliv cesty (v úloze zkrat, kde k rychlému vyřešení vede nalezení maximálního počtu hranově disjunktních cest mezi jádrem a zkratem).
Naskenované poznámky z lekce.

Záznam z 27. května
Výklad spojového seznamu (při tom jsme vyložili, co je třída).
Prezentace o spojovém seznamu.
Spojový seznam na replu.

Záznamy z 21. května
Prezentace úlohy 32-Z3-4.
Prezentace úlohy 32-Z1-4.

Záznamy z 20. května
Výklad prohledávání do hloubky (dfs -- depth first search) s kódem na replu. Náčrtky grafů pro prohledávání do hloubky.
Prezentace úlohy 30-Z1-5.

Záznamy ze 14. května
K důkazu správnosti Jarníkova algoritmu.
Toky v sítích.

Záznamy z 13. května
Dijkstrův a jarníkův algoritmus.

Záznamy ze 7. května
Prezentace úlohy 32-3-1 (zkrat).
Programování haldy, kódy jsou na replu.

Výklad o datové struktuře halda (předtočená lekce). Naskenované poznámky z lekce: pred, po.

Záznamy ze 6. května
Prezentace úlohy Sářina omalovánka (32-Z3-2).
Výklad Bellman-Fordova algoritmu, souvislost se Sářinou omalovánkou, výklad základních pojmů teorie grafů, prohledávání grafu do šířky. Naskenovaný výklad.

Záznam prezentace úlohy 31-Z2-1 ze dne 30. dubna.
Záznam prezentace úlohy 32-Z2-4 ze dne 30. dubna.

Záznam z přednášky ze dne 29. dubna. Mluvili jsme blíže o časové složitosti, počítali počty operací SelectSortu, MergeSortu a QuickSortu. Schéma k výkladu časové složitosti řadících algoritmů. Na příkladu QuickSortu jsme vysvětlili, co je rekurze. Kódy k přednášce jsou na replu.

Byla jsem požádána o návrh okruhů k szz. Pro širší (tematický) rozhled se podívejte na okruhy na matfyzu.

Můj neúspěšný pokus urychlit quick sort tak, aby byl srovnatelný s metodou sort(). Metoda sort pro python je pravděpodobně implementovaná rychlejším jazykem. Repl pro python 2.7 se tváří obdobně, ale asi to tak není.

Záznam z prezentace úlohy 32-Z3-1 dne 23. 4.

Záznam z přednášky 22. 4. Je dlouhý přes dvě hodiny.
Pokud vás zajímají organizační záležitosti, poslechněte si začátek a konec.
Komentář k lekci:
Programování má tři fáze: analýza problému, něco odpovídajícího pseudokódu a kód. Je důležité být si vědoma, které z fází se právě věnuji. A je dobré dodržovat výše uvedené pořadí. Mně se to v lekci úplně nedařilo. Navíc jsem se zbrkle vrhla na první pseudokód v učebnici, aniž bych si přečetla, co je u něj napsáno. Považuji to za užitečnou ukázku, kolik nakonec ztratíte času, když si práci pořádně nerozvrhnete. Kromě vyložených algoritmů tak považuji lekci za docela užitečnou ukázku, čeho se vyvarovat.
Výsledek najdete na replu. Chcete-li si prohlédnout úseky, které se v průběhu řazení slévají, odkomentujte řádky 56, 60, 83 a na řádku 79 zvolte malý počet.
Z cílů přednášky jsme splnili: Ukázat práci s pseudokódem a programování s jeho pomocí. Vysvětlit, co je časová složitost algoritmu a proč je důležité se jí zabývat.
Na příště zbývá: Spočítat časovou složitost pro oba řadící (ne úplně správně se běžně říká třídící) algoritmy. Vysvětlit princip metody rozděl a panuj. Ukázat, jak se mergesort naprogramuje rekurzí.
Pokyny pro práci během koronavirové karantény:
Každý týden, vždy do neděle, pošlete zprávu o svém studiu.
V případě, že vám dělá problém řešit i úlohy za 8 bodů z KSP-Z, pošlete informaci o tom, kam jste postoupili v kurzu na code.org. V případě problémů je popište, jsem tu od toho, abych vám poradila.
V opačném případě posílejte svoje řešení úloh z KSP-Z, a to bude dvojího typu: Pošlete hotové řešení s informací, že se jedná o zápočtovou úlohu. Nebo pošlete jen část řešení, a v tom případě ode mě dostanete komentář. Neváhejte v takovém případě formulovat otázky, ráda na ně odpovím. Úlohu, kterou s vámi budu takto konzultovat, nemůžete zařadit mezi zápočtové.
Upozorňuji, že na webu ksp byla zveřejněna třetí série začátečnické kategorie. Věnujte proto přednostně pozornost těmto úlohám (jednu takovou musíte na zápočet vyřešit), ale pokud vám řešení nepůjde, nevěšte hlavu, bude v květnu ještě čtvrtá série. Do té doby se v řešení úloh vytrénujete a zvládnete to.
Cvičení 5. 3. 2020
Upřesnili jsme požadavky na zápočet, viz poslední odstavec požadavků.
Probrali jsme domácí práce: úlohu 26-Z2-1 a částečně úlohu 26-Z3-1 (vrátíme se k ní příště).
Ukázali jsme si kurz z code.org a doporučili ho k pochopení základů algoritmizace.

Cvičení 27. 2. 2020
Ještě jednou jsme napsali pseudokód pro úlohu 26-Z1-1, stanovili jsme pravidla psaní pseudokódu. Naprogramovali jsme úlohu v Pythonu.
Řešili jsme problém spuštění skriptu z příkazové řádky (umožní nám přesměrovat vstup ze souboru na standardní vstup). Neuspěli jsme, vyřešíme příště.
Podrobně jsme ještě jednou rozebrali select sort, psali pseudokód, téměř jsme stihli.

Úkol na doma: vybrat si jednu z úloh začátečnické kategorie KSP z 26-Z[2-4]-1, napsat pseudokód, naprogramovat v Pythonu. Poslat e-mailem do večera úterý 3. 3. V případě problémů, popsat v čem je problém.

Přednáška 26. 2. 2020
Věnovali jsme se odpovědím na otázky z dotazníku.
Seznámili jsme se s korespondenčním seminářem v programování (KSP) a s kategorií P matematické olympiády.
Seznámili jsme se s podmínkami získání zápočtu.
Na příkladu řazení prvků jsme si vysvětlili, co je časová složitost algoritmu. Předvedli jsme rychlost běhu řadících algoritmů: quick sort, merge sort, heap sort a bubble sort na datech různé velikosti, konkrétně pro tisíc, deset tisíc, dvacet tisíc, čtyřicet tisíc prvků. Vysvětlili jsme si, jak funguje select sort a vysvětlili, že počet operací pří řazení N prvků bude řádově N^2 (kvadratická časová složitost). Konstatovali jsme, že časová složitost ostatních algoritmů (quick, merge, heap) je N log N. Konstatovali jsme, že nezáleží na základu logaritmu (mezi logaritmy při dvou různých základech je přímá úměrnost). Rozebrali jsme, jak se změní doba běhu při zdvojnásobení počtu dat pro jednotlivé řadící algoritmy. Učinila jsem pokus o zápis pseudokódu select sortu, ale vzdala jsem to.
Rozebrali jsme úlohu 26-Z1-1 začátečnické kategorie KSP.

Úkol na čtení doma: Část první: Základní pojmy, Algoritmus a program.
Při psaní programů budeme načítat vstup a vypisovat výstup. K tomu se nám bude hodit Parsování vstupu v Pythonu 3.