KSP-H	2. série se opravuje, 3. sérii odevzdávejte do 16. 2. 2025
KSP-Z	3. série se opravuje (praktické ještě dnes za ⅓ bodů)

Programátorská encyklopedie
Korespondenčního semináře z programování

Na této stránce naleznete studijní materiály o programování a informatice všeobecně. Encyklopedie obsahuje:

Články na algoritmická i technická témata (včetně kuchařek – studijních textů přikládaných k zadání sérií)
Seriály vycházející v ročnících KSP (vícedílné studijní texty proložené úlohami)
Videozáznamy přednášek z našich soustředění, Smrští a dalších akcí
Knihy vydané KSP: Programátorské kuchařky a Ročenky
Seznam doporučených odkazů a knížek pro další prohlubování programátorských znalostí a dovedností.

Seznam článků

Základní algoritmy – Co to je program a algoritmus? Základní datové struktury (pole, spojové seznamy, grafy, stromy, …) a také nejzákladnější programovací techniky: rekurze, backtracking, hladové algoritmy.
Složitost – Jak se porovnává efektivita algoritmů, co je to složitost algoritmu, jak se počítá a jaké jsou její druhy.

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

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

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. V připomeneme naprosté základy analytické geometrie.

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í.
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.
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é – takovému tahu v grafu se říká eulerovský a tím se zabývá tento text.
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?
Maximální párování – Vysvětlení problému párování, zlepšující cesty.
Hopcroft-Karp – O něco lepší varianta základního párovacího algoritmu.

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.
Vektory – Základní pojmy pro práci s vektory.
Integrály – Základní uvedení do integrálů pro účely grafického seriálu.

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

Protokol HTTP – HTTP je síťový protokol, který slouží ke komunikaci s webovými servery, ale také různými API.
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.
Prolog – Instalace interpreteru.

WSL2 – Linuxové prostředí pro Windows – Jak si pořídit linuxové prostředí na Windows.
Python – instalace PyCharm – Jak nainstalovat vývojové prostředí PyCharm určené pro programování v Pythonu.
Python – instalace balíčků pomocí Pip – Jak se v Pythonu dají jednoduše doinstalovat scházející knihovny.
Python 3 – parsování vstupu – Jakým způsobem načítat v Pythonu 3 vstup, abychom s ním mohli něco dělat.
C – základní parsování vstupu – Jakým způsobem načítat v C vstup, abychom s ním mohli něco dělat.
C – pokročilé parsování vstupu – Čtení vstupu po znacích a práce se stringy
Cygwin – shell ve Windows – Starší způsob, jak si pořídit Linuxový shell na Windows. Hodí se pro počítače s malou pamětí.