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?

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


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

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 ke kuchařce o minimálních kostrách

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.

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.

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

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?

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