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áklady

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.

Algoritmizační techniky

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í.

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í.

Datové struktury

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.

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.

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.

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, …).

Algoritmy

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?

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.

Grafy

Ilustrace grafů

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í.

Ilustrace ke kuchařce o minimální kostře

Minimální kostra

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.

Ilustrace rovinných grafů

Rovinné grafy

Rovinné grafy jsou takové, že je můžeme bez křížení hran nakreslit do roviny. Jaké mají vlastnosti?

Ilustrace eulerovských tahů

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.

Ilustrace toků

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?

Teorie složitosti

Těžké problémy

Je P rovno NP? Jaké problémy jsou doopravdy těžké? Řešení podvodem a jiné bláznivosti.

Jiné kuchařky

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.

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í.