Příležitostně se vrátíme k tématům: výuka informatiky na základních a středních školách a změny, které tento předmět čeká; role algoritmů a datových struktur v informatice. (Původně byla plánovaná na první či druhý týden, ale nedošlo na ně.)

Na webu KSP je pátá série. Změkčuji podmínky následovně: Lze řešit i úlohu 34-Z5-1 za celkových 16 bodů; Budete-li řešit grafovou úlohu, můžete za vysvětlení prohledávacího algoritmu (dfs nebo bfs) dostat až 6 bodů navíc.

Přednáška 25. 5. 2022
Probereme lepší návrh proměnných na Jarnikův algoritmus repl_2,
Budeme se věnovat analýze a programování Dijkstrova algoritmu (bude to překvapivě snadné, využijeme podobnost s Jarníkovým algoritmem, kód jen upravíme).
A diskutovat co je P a NP.

Cvičení 26. 5. 2022
Budeme se věnovat rozboru úloh z páté série.


Cvičení 19. 5. 2022
Prošli jsme kód, který jsem vložila po minulém cvičení (kombinace cyklu a podmínky místo původních vnořených cyklů) 27-Z1-3c.
Programovali jsme Jarníkův algoritmus repl, trápili jsme se s nešikovným návrhem proměnných.

Cvičení 12. 5. 2022
Věnovali jsme se úloze 27-Z1-3. Řešení, pro které jsme vygooglili funkci vracející nejčetnější prvek v poli 27-Z1-3b. Po cvičení jsem si uvědomila, že dva vnořené cykly (pokus ze cvičení, který jsem poté vzdala) lze nahradit kombinací cyklu a podmínky 27-Z1-3c.
Probírali jsme další úlohy teoretické i praktické.

Přednáška 11. 5. 2022
Probrali jsme Jarníkův algoritmus na hledání minimální kostry, z Průvodce labyrintem algoritmů jsme zopakovali na str. 159 definici základních pojmů, na str. 161 dole obrázek 7.2 demonstrující Jarníkův algoritmus, na str. 160 dole pseudokód Jarníkova algoritmu. Řekli jsme, co je hladový algoritmus (greedy algorithm), vysvětlili jsme řezové lemma na str. 162 včetně důkazu a řekli, že dokazuje správnost Jarníkova algoritmu v případě unikátně ohodnocených hran. Naznačili jsme, jak se při důkazu postupuje v obecném případě. Zabývali jsme se časovou složitostí Jarníkova algoritmu při použití různých datových struktur na vybrání nejlevnější hrany (pole, halda obsahující hrany, halda obsahující vrcholy). Na závěr jsme se stručně zmínili o Kruskalově a Borůvkově algoritmu.
Ukázali jsme, jak může kód v pythonu na výstup vypsat sám sebe -- repl.

Cvičení 5. 5. 2022
Zmínili jsme se o datové struktuře dictionary (hodí se k řešení jedné z úloh páté série) a o jejích metodách. Srovnali jsme ji s listem.
Věnovali jsme se teoretické úloze 27-Z1-5 a rozpracovali jsme praktickou úlohu 27-Z1-3, repl.

Cvičení 28. 4. 2022
Věnovali jsme se obhajobám úloh. Návštěvu z České Lípy jsme využili k diskusi o výuce informatiky.

Přednáška 27. 4. 2022
Probrali jsme binární haldu, časovou složitost jejích operací, ukázali jsme použití tříd při programování binární haldy. (Halda se používá v následujících dvou algoritmech -- Dijkstrovým a Jarníkovým.)
Vysvětlili jsme Dijkstrův algoritmus na hledání nejkratší cesty v grafu a jeho časovou složitost.
Řekli jsme, co je kostra grafu, co je minimální kostra grafu a představili jsme Jarníkův algoritmus na hledání minimální kostry.

Cvičení 21. 4. 2022
Řekli jsme si, že příští týden budeme mít návštěvu a zahájíme diskusi k tématům nahoře.
Věnovali jsme se úloze 28-Z1-4, repl ze cvičení. Podle vzorového řešení jsem kód ze cvičení upravila (28-Z1-4b): jednak jsem vytvořila funkci dfs a dále jsem list tridy nahradila listem navstiveny.
Zamyšlení nad tím, jestli může kód v pythonu na výstup vypsat sám sebe necháme na jindy.

Cvičení 14. 4. 2022
Oznámili jsme změnu harmonogramu odevzdání úloh: třetí a čtvrtou úlohu lze odevzdat o týden později, tedy do neděle v 9. a 11. týdnu semestru. Velikonoční neděle je termín pro první i druhou úlohu pro studenty, kteří tak dosud neučinili.
Věnovali jsme se úloze na binární vyhledávání 34-Z1-3, repl 34-Z1-3.
Dále jsme se věnovali úloze 28-Z1-3, repl.

Přednáška 13. 4. 2022
Řekli jsme, že u algoritmů nás zajímá: popis, což je návod pro programátora, jak má algoritmus naprogramovat; důkaz, že algoritmus dělá to, co od něj očekáváme; časová a paměťová náročnost, vysvětlili jsme symbol O.
Při vysvětlování symbolu O jsme se vrátili ke srovnání lineární a logaritmické náročnosti: spočítali jsme, jak dlouho trvá tisíc vteřin, milión vteřin, miliarda vteřin, zatímco dvojkové logaritmy těchto čísel jsou (zhruba) 10, 20, 30.
Probrali jsme domácí úkol na Bellman-Fordův algoritmus. Popis Bellman-Fordova algoritmu je na str. 150 Průvodce labyrintem algoritmů s tím, že na uložení otevřených vrcholů použijeme frontu. K důkazu a analýze časové náročnosti jsme použili rozbor na fáze, viz sken z minulé přednášky.
Vysvětlili jsme princip Dijkstrova algoritmu na hledání nejkratší cesty -- popis je též na str. 150 průvodce s tím, že na uložení otevřených vrcholů použijeme datovou strukturu zvanou halda.
Vysvětlili jsme, jak funguje binární halda, viz video, naskenované poznámky k videu: před lekcí, po lekci. Řekli jsme, že časová náročnost operací insert, extractmin a decrease je log(n).

Cvičení 7. 4. 2022
Na šachovnici jsme pro dvě zadaná pole našli nejkratší cestu koněm kód ze cvičení: 31-Z1-2b, kód upravený k větší přehlednosti: 31-Z1-2c.
Probrali jsme teoretickou úlohu šíření zpráv: 34-Z1-4.
Upozornila jsem, že budu přísněji požadovat vysvětlení konstrukcí použitých při obhajobě v kódu. Tento týden jsme narazili na konstrukci while-else, for-else. Zde máte vysvětlení, jak funguje.

Cvičení 31. 3. 2022
Probrali jsme 33-Z1-3b, vysvětlovali jsme rozdílnou dobu běhu 33-Z1-3b a 33-Z1-3c.
Šachovou úlohu 31-Z1-2 jsme upravili: spočítali jsme minimální počet tahů koněm ze zadané počáteční pozice do všech koncových pozic 31-Z1-2a.

Přednáška 30. 3. 2022
Dokončili jsme analýzu řadících programů -- vrátili jsme se k mergesortu a probrali quicksort a ukázali jak rekurze souvisí s prohledáváním grafu do hloubky. K demonstraci algoritmů jsme použili kód na replu.
Na 33-Z1-3c jsme vysvětlili prohledávání grafu do šířky BFS.
Dalším použitím BFS je Bellman-Fordův algoritmus hledání nejkratší cesty v grafu. K výkladu jsme použili pseudokód z Průvodce labyrintem algoritmů na str. 150.

Cvičení 24. 3. 2022
Vrátili jsme se ke kódům z minulého cvičení: repl 29-Z3-2b, repl 29-Z3-2c, vysvětlili na nich, jak budou probíhat obhajoby a dokončili jsme úlohu repl 29-Z3-2d. (Na vzorové řešení z KSP jsme se nedívali.)
Ukázali jsme, že algoritmus 29-Z3-2b má kvadratickou dobu běhu v závislosti na velikosti vstupu a algoritmus 29-Z3-2c je také v nejhorším případě kvadratický (tj. existuje vstup, pro který je závislost kvadratická). Algoritmus používající trii je lineární.

Věnovali jsme se úloze 33-Z1-3, došli jsme k repl 33-Z1-3a. Pro zjednodušení jsme zacyklení detekovali dlouhou cestou a konstatovali jsme, že to může být pro některé vstupy problém.
Příště probereme algoritmus, který lépe ošetří krátká zacyklení: repl 33-Z1-3b a probereme algoritmus prohledávání grafu do šířky.

Cvičení 17. 3. 2022
bylo zrušeno rozhodnutím rektora TUL.

Přednáška 16. 3. 2022
Vysvětlili jsme základní pojmy teorie grafů (co je graf, cesta v grafu, kružnice, jaký graf nazýváme stromem).
Podle vzorového řešení úlohy 29-Z3-2 jsme vyložili datovou strukturu trie (trie je speciální strom umožňující uložit slovník, vyhledávat v něm, přidávat a odebírat slova). Použili jsme obrázek z 29-Z1-5, případně z kuchařky o hledání v textu. Vysvětlili jsme, jak do trie vložit slovo a jak pomocí trie spočítat počet prefixů daného slova.

Ve zbylém čase jsme opakovali princip řadicích algoritmů vyložených na poslední přednášce: repl sort.

Cvičení 10. 3. 2022
Stručně jsme se vrátili k úloze 33-Z2-1 z předminulého týdne.
Věnovali jsme se úloze 29-Z3-2, začali jsme výkladem repl 29-Z3-2a (bylo za úkol na doma místo posledního cvičení). Úlohu jsme naprogramovali algoritmem repl 29-Z3-2b, otestovali na cvičišti a zjistili, že algoritmus zvládá jen menší vstupy. Pustili jsme se do rychlejšího algoritmu: repl 29-Z3-2c.

Cvičení 3. 3. 2022
Cvičení jsem zrušila pro nemoc.

Přednáška 2. 3. 2022
S kolegou Kalouskem jste si zahráli hru myslím si číslo a probrali řadící algoritmy včetně jejich časové složitosti (tedy informaci o rychlosti běhu jednotlivých algoritmů) podle https://www.itnetwork.cz/algoritmy/razeni.

Cvičení 24. 2. 2022
Seznámili jsme se s podmínkami absolvování předmětu a s korespondenčním seminářem z programování. Věnovali jsme se úloze 33-Z2-1.
Zahráli jsme si hru: myslím si číslo od jedné do sta, dávej otázky, na které odpovím ano/ne, na kolik otázek číslo zjistíš? Do příští středy si studenti rozmyslí strategii na číslo do tisíce a do miliónu.