Kuchařky
Na této straně najdete přehled učebních textů, které jsme pro vás během dlouhé historie semináře připravili.
Kuchařky byly začátkem 24. ročníku uspořádány do knihy Programátorské kuchařky.
Základní kuchařky
Základní algoritmy
Studijní text vysvětlující od základů, co to je program a algoritmus. Ukážeme si základní datové struktury (pole, spojové seznamy, grafy, stromy, …) a také některé z nejzákladnějších programovacích technik, které by měl znát každý programátor: rekurze, backtracking nebo třeba hladové algoritmy. Povinné čtivo pro každého začínajícího řešitele.
Složitost
"Už to počítá dva dny a ještě nevypadlo ani písmenko…" Jak se porovnává efektivita algoritmů, co je to složitost algoritmu, jak se počítá a jaké jsou její druhy, to všechno se dozvíte v této kuchařce.
Třídění
Dostaneme seznam lidí, chceme je seřadit podle jmen. Tomu se říká třídění. Jaké algoritmy řešící daný problém v různých podmínkách umíme vymyslet?
Grafy
Co je to graf? Vrchol, hrana? Sled, tah, cesta? K čemu všechny ty pojmy jsou? V této kuchařce najdete popis prohledávání do hloubky a do šířky a také topologické uspořádání.
Rozšiřující kuchařky
Binární vyhledávání
Binární vyhledávání je mocná technika, která se objevuje ve všemožných algoritmech a úlohách. S pomocí binárního vyhledávání umíme rychle vyhledat hodnotu v seřazeném poli nebo třeba zredukovat úlohu hledající největší možný počet hostů v hotelu na úlohu tázající se, jestli umíme ubytovat nějaký konkrétní počet hostů.
Halda, heapsort a Dijkstrův algoritmus
Halda je jednoduchá datová struktura, která nabízí rychlé vkládání prvků a výběr prvku největšího. To se dá využít ve dvou důležitých algoritmech: v třídění haldou a Dijkstrově algoritmu pro nalezení nejkratší cesty.
Rozděl a panuj
U mnoha problémů jsme schopni zvýšit rychlost tím, že je vyřešíme vhodným rozdělením na menší úlohy, zpracováním a následným sloučením navrácených částečných řešení.
Vyhledávací stromy
Vyhledávací stromy umí uchovávat proměnlivé množství dat se zaručeně logaritmickými časovými náklady na typické operace.
Treapy
Treapy jsou blízcí příbuzní vyhledávacích stromů. Mají logaritmickou časovou složitost jen v průměru, ale pracuje se s nimi mnohem příjemněji.
Dynamické programování
U mnoha problémů jsme schopni zvýšit rychlost tím, že je vyřešíme postupným zapracováváním větších a větších částí vstupu do řešení.
Hešování
Hešování umí uchovávat proměnlivé množství dat s průměrně konstantními náklady na typické operace.
Pokročilé kuchařky
Rovinné grafy
Rovinné grafy jsou takové, že je můžeme bez křížení hran nakreslit do roviny. Jaké mají vlastnosti?
Minimální kostry
Kostra je takový podgraf souvislého grafu, který je stromem, ale zároveň obsahuje všechny vrcholy. Minimální kostra v ohodnoceném grafu je taková kostra, kterýchžto hran ohodnocení má nejmenší součet. Jak ji najít je slavný, ale stále ještě ne-úplně-vyřešený problém.
Procházky po grafech
Jak při procházce právě jednou navštívit všechny vrcholy grafu? To je těžký problém, kýžené cestě se říká hamiltonovská. Jak projít všechny hrany grafu? To je naopak jednoduché – takovému tahu v grafu se říká eulerovský a tím se zabývá tento text.
Hledání v textu
Máme-li předlouhý řetězec S a hledáme-li v něm P, můžeme to zkusit porovnáváním každého podřetězce S délky |P| s P, ale jde to i rychleji a hlavně podstatně zajímavěji.
Geometrie
Máme souřadnice stromů v sadu a chceme sad oplotit co nejkratším plotem. Rozházíme po stole špejle a chtěli bychom vědět, kde všude se kříží. Podíváme se na to, jak se program může naučit zametat a předem si projdeme, naprosté základy analytické geometrie.
Intervalové stromy
Intervalový strom umí uchovávat posloupnost a rychle provádět změnu libovolného prvku a dotaz na nějakou operaci přes libovolný interval z ní (součet, maximum, …).
Toky v sítích
Jak přepravit co nejvíc materiálu po distribuční síti? Jak najít maximální párování v bipartitním grafu? Jak zjistit, kolik vede z vrcholu do vrcholu disjunktních cest?
Těžké problémy
Je P rovno NP? Jaké problémy jsou doopravdy těžké? Řešení podvodem a jiné bláznivosti.
Teorie čísel
V této spíše teoretické kuchařce najdete směsici různých užitečných poznatků souvisejících především s aritmetikou. Naučíte se z ní například rychle počítat mocniny nebo použití Čínské zbytkové věty.
Pravděpodobnost
V této kuchařce nahlédneme do základů teorie pravděpodobnosti a vybudujeme jí dost na to, abychom uměli zkoumat jednoduché randomizované algoritmy.
Práce s pamětí
V této kuchařce se, poněkud netradičně, nepodíváme pod pokličku nějakého algoritmu, ale povíme si něco o tom, co se děje na pozadí, když se v našem programu rozhodneme vytvořit nějakou proměnnou, číst z ní, nebo do ní zapisovat.
Nekuchařky
Ve dvanácté sérii jsme k řešení úlohy 12-2-1 sepsali povídání o konstrukci vyhledávacích automatů, a ačkoliv tento textík není vyloženě kuchařka, určitě je hoden pročtení.