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.

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?

Vyhledává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.

	Grafy Co je to graf? Vrchol, hrana? Sled, tah, cesta? K čemu všechny ty pojmy jsou? V dané kuchařce najdete popis prohledávání do hloubky a do šířky a také topologické uspořádání.
	Minimální kostra Kostra je takový podgraf souvislého grafu, který je stromem, ale zároveň obsahje 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.
	Rovinné grafy Rovinné grafy jsou takové, že je můžeme bez křížení hran nakreslit do roviny. Jaké mají vlastnosti?
	Eulerovské tahy 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é – a zabývá se tím tento text.
	Toky 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.

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

KSP

Korespondenční seminář z programování