Omylem jsem z replu smazala odkazy na úlohy z ksp. Ostatní kódy by měly zůstat zachované.

Přednáška 26. 5. 2021
Probrali jsme haldu (repl) a její použití na hledání minimální kostry grafu. K haldě: video, naskenované poznámky k videu: před lekcí, po lekci.
K výkladu Jarníkova algoritmu jsme použili kapitolu 7.2 z průvodce labyrintem algoritmů.
Věnceslav prezentoval použití binárního stromu na úlohu firewall (33-4-2).
Ve zbylém čase jsme si povídali o písmenkových stromech -- použili jsme kapitolu 4.3 z průvodce.

Cvičení 20. 5. 2021
Veronika Macháčková prezentovala svoje řešení praktické úlohy Přerovnávání čísel. Rozebrali jsme řešení teoretických úloh. -- sken

Cvičení 13. 5. 2021
Olbram Zub prezentoval řešení úlohy z KSP.
Probrali jsme úlohy 31-Z3-5 Scrabblová, 31-Z3-6 Vyzvednutí výhry, 27-Z2-6 Povrch dálnice -- sken.
Ukážeme si obrázky k BFS a DFS, na úloze 26-Z1-4 budeme ještě jednou demonstrovat prohledávání do hloubky -- repl III.

Přednáška 12. 5. 2021
Vrátili jsme se k úloze 26-Z1-4, ukázali rozdíl při použití zásobníku/fronty na prohledávání grafu. Použitím fronty (FIFO) dostaneme prohledávání do šířky (BFS), použitím zásobníku (LIFO) prohledávání do hloubky (DFS). Dále jsme ukázali použití globálních a lokálních proměnných -- repl, repl II.
Další použití prohledávání do hloubky jsme ukázali na řešení úlohy 31-Z3-2 (repl II). Dále jsme ukázali design (návrh) programu za použití tříd. Zmínili jsme se o rozdělení kódu na privátní a veřejný -- privátní je pro programátora a uživatelům zůstává skrytý.

Cvičení 6. 5. 2021
Analyzovali jsme dobu běhu našeho a vzorového řešení úlohy 30-Z4-4 -- repl I, repl II, repl KSP, sken.
Na úloze 26-Z1-4 jsme vysvětlovali prohledávání grafu do šířky -- repl, sken.
Na úloze 31-Z3-2 jsme vysvětlovali prohledávání grafu do hloubky -- repl.

Cvičení 29. 4. 2021
Dokončili jsme úlohu z minula a otestovali na cvičišti -- repl, sken.
Chtěli jsme se věnovat úloze 26-Z1-4, ale stihli jsme jen krátký úvod.

Přednáška 28. 4. 2021
Shlédněte video o datové struktuře halda, naskenované poznámky: před lekcí, po lekci.
Dijkstrův algoritmus, Sken k rozdílu mezi frontou a haldou a k rozdílu mezi Bellman-Fordem a Dijkstrou, sken z přednášky k Dijkstrovu algoritmu.
Sken k výkladu kostry grafu.
Sken k Jarníkovu algoritmu na hledání minimální kostry.
Ukázali jsme rozdíl v rychlosti běhu při použití list a deque na implementaci fronty -- repl, sken.

Cvičení 22. 4. 2021
Barbora Lidová předvedla úlohu 29-Z2-2.
Probrali jsme úlohu 30-Z4-2 -- repl.
Probrali jsme pomalý algoritmus na úlohu 30-Z4-4 -- repl. K úloze se vrátíme příště a naprogramujeme rychlejší algoritmus.

Cvičení 15. 4. 2021
Dokončili jsme povídání o Bellman-Fordovu algoritmu na hledání nejkratší cesty -- sken (kromě důkazu správnosti algoritmu obsahuje i analýzu časové náročnosti), repl.
Definivali jsme symbol velké O, který používáme k popisu rychlosti algoritmů -- sken.
Dokončili jsme úlohu 31-Z3-3 -- repl V.

Přednáška 14. 4. 2021
Základní pojmy o grafech. Na grafu z obrázku jsme vyložili Bellman-Fordův algoritmus na hledání nejkratší cesty z počátečního vrcholu do všech ostatních vrcholů -- skeny (důkaz správnosti algoritmu se mně nepovedl, napravili jsme následující den), repl. Využili jsme frontu (queue) -- repl.

Cvičení 8. 4. 2021
Ještě jednou jsme se vrátili ke zpracování vstupu -- repl.
Pokračovali jsme v práci na úloze 33-Z2-2 o plotýnkách a hrncích -- repl z minula, pokračování: repl I, repl II.
Pokračovali jsme v práci na úloze 31-Z3-3. Repl z minula, poračování -- repl III, repl IV. Další pokračování bude příště použitím fronty (queu, FIFO -- first in firs out) -- dokumentace, repl.

Cvičení 1. 4. 2021
Vyložili jsme, jak pracuje quicksort (včera kvůli chybě v kódu nefungoval) a znovu jsme vykládali rekurzi -- repl.
Pokračovali jsme v práci na úloze 31-Z3-3 -- repl, v druhém replu jsme poukázali na zpracování vstupu.
Pracovali jsme na úloze 33-Z2-2 -- repl.

Přednáška 31. 3. 2021
Vrátili jsme se k rychlým řadícím algoritmům, ukázali, jak pracuje mergesort a jak pracuje rekurze -- repl.
Ukázali jsme jedno úskalí při práci s rozsáhlými listy na úloze 30-Z2-1: repl.
Pracovali jsme na úloze 31-Z3-3.

Cvičení 25. 3. 2021
K organizaci obhajoby druhé úlohy: Do neděle 4. dubna pošlete emailem kód (odkaz na repl) a screenshot cvičiště, kde jste úlohu otestovali. Ve stagu se přihlaste na některý z termínů, které jsem vypsala na 6. dubna.
Doporučení k výběru úlohy: Pokud máte stále problém se syntaxí pythonu, doporučuji vám vybrat si úlohu za 8 bodů. Pokud syntaxi zvládáte a chcete se pocvičit v algoritmech, vyberte si náročnější úlohu.

Dali jsme praktické rady na zpracování vstupu a výstupu. Získala jsem je z vašich řešení úloh.
Metody read(), readline(), split(), splitline() na zpracování vstupu.
Konverze stringu na int, použití funkce map na list.
Konverze int na string.

Filip Chaloupka stručně popsal, jak řešil úlohu 33-Z4-2.

Věnceslav Chumchal stručně představil web, na kterém se učil programovat.

Programovali jsme úlohu 31-Z3-3. Zatím jsme jen zpracovali vstup -- vytvořili jsme pole sousedů. Použili jsme metodu append -- odkaz na repl.
Na přednášce úlohu vyřešíme pomocí hladového algoritmu.

Cvičení 18. 3. 2021
K úloze 33-Z4-2 jsme k radám z minula (práce s poli, vyhledání hvězdičky) přidali radu, jak otestovat, zda je znak číslice či malé nebo velké písmeno anglické abecedy -- repl.
Na větších testovacích sadách jsme ukázali pomalost našeho "bruteforce -- silového" algoritmu na úlohu 29-Z3-2. Naprogramovali jsme rychlejší algoritmus -- repl.
Pustili jsme se do úlohy 31-Z3-3, na konkrétním vstupu jsme rozebrali, jak se úloha řeší. Protože je to grafová úloha, uvedli jsme definici grafu. Skeny k úloze.

Přednáška 17. 3. 2021
Probírali jsme vyhledávání v uspořádaném souboru dat (repl) (dokončení z minula).
Povídali jsme si o metodách řazení neuspořádaného souboru (insertsort, selectsort, quicksort).
Stručně jsme se zmínili, jak se měří rychlost algoritmů (počet operací v závislosti na velikosti vstupu). Vysvětlili jsme, co znamená, když řekneme, že insertsort a selektsort jsou kvadratické algoritmy.

Cvičení 11. 3. 2021
Probírali jsme i/o (vstup/výstup) práci se soubory.
Dokončili jsme úlohu 26-Z2-1 a otestovali ji na cvičišti. Studenti si vyzkoušeli testování na cvičišti.
Zabývali jsme se úlohou 29-Z3-2. Při ladění jsme si uvědomili, že funkce readline načítá řádek včetně znaku odřádkování a ukázali jsme si, jak ze vstupu tento znak odstranit. Úlohu jsme otestovali jen na dvou nejmenších testovacích vstupech. Příště ukážeme rychlejší řešení a otestujeme ho na ostatních vstupech.
Probírali jsme práci s listy.

Cvičení 4. 3. 2021
Práci se soubory v pythonu jsme nechali na příště.
Pokračovali jsme v úloze 26-Z2-1 (repl), za týden doděláme vstup a výstup a otestujeme na cvičišti KSP.
Rozebírali jsme úlohu 29-Z3-2 -- repl sken

Přednáška 3. 3. 2021
Upozornili jsme na drobnou změnu bodování úloh na zápočet. Cílem změny je podřídit se situaci, kdy v půlce semestru už žádná "živá" úloha v začátečnické kategorii nebude. Vedlejší cíl je podpořit spolupráci mezi vámi. "Živé" úlohy budou mít časově odstupňované hodnocení, nejvyšší hodnocení budete moci získat při obhajobě do pátku 12. března (bude to více než původně avizovaný dvojnásobek). Při obhajobě těsně před zveřejněním řešení na webu KSP naopak dostanete jen něco málo přes jednonásobek. Přesný harmonogram bodování se dozvíte na zítřejším cvičení.

Vyložili jsme, co je binární vyhledávání a naprogramovali jej v pythonu na replu. Přitom jsme zároveň vyložili datové struktury pole (list) a spojový seznam (linked list), upozorníme na některé rozdíly. K rozšíření znalostí o spojových seznamech doporučuji tutoriál z realpython.com.
Videozáznam z přednášky je na sdíleném disku.

Cvičení 25. 2. 2021
Probrali jsme podmínky pro absolvování předmětu.
Doporučili jsme web code.org pro ty, kteří dosud nemají zápočet z UDP (a nejen pro ně).
Věnovali jsme se odpovědím na otázky v dotazníku.
Zadali jsme úkol do příštího cvičení: pokud to neumíte, naučte se v Pythonu pracovat se vstupy a výstupy z a do souboru. Vysvětlili jsme, proč je nutné učit se takové problémy řešit.
Probírali jsme úlohu 26-Z2-1 z korespondenčního semináře programování, doděláme i s kódem v Pythonu příště -- sken. Videozáznam z probírání této úlohy je na sdíleném disku.
Hráli jsme hru: myslím si číslo od jedné do sta, pokládej otázky, na které odpovím ano nebo ne. Přemýšleli jsme nad strategií, kterou získáme dané číslo na co nejméně otázek.