Pravděpodobně dvoudílná přednáška pro ty, kdo potřebují dohnat základní znalosti nutné pro ostatní přednášky. Zadefinujeme si základní pojmy jako je algoritmus, program, rekurze a jak se počítá jejich časová složitost, bude následovat přehled základních algoritmů – převážně třídění, rychlé hledání k-tého nejmenšího prvku, práce s výrazy a další.

V rámci této přednášky se budeme zabývat problémy tak těžkými, že nikdo na světě pro ně neumí vymyslet efektivní (rozuměj polynomiální) algoritmus. Spousta lidí dokonce věří, že to vůbec možné není. Abychom mezi tyto problémy pronikli, seznámíme se s pojmy NP-úplnosti a NP-těžkosti. Především si však konkrétní těžké úlohy ukážeme a naučíme se i některé těžké úlohy rozpoznat. Závěrem si řekneme, jak se s těžkými úlohami vypořádat v praxi.

K čemu je dobré, když grafem teče voda. Předvedeme si klasický problém toků v sítích a jeho všelijaké, mnohdy dosti překvapivé aplikace. Jak rozestavět n věží na šachovnici a jak ji místo toho pokrýt dominovými kostkami? Další souvislosti, jako třeba násobná souvislost grafů.

Jak si ukládat data natolik šikovně, abychom je nejen neztratili, ale také našli dříve, než si pro nás přijde Smrť. Klasické struktury jako pole, seznamy, fronta a zásobník, trie, vyhledávací stromy (vyvážené, AVL, a-b, splay), haldy (binární a obecně regulární) a v neposlední řadě hešování.

Na přednášce si ukážeme některou z méně známých složitějších datových struktur. Pokud Ti ostatní přednášky přijdou moc jednoduché, tato je ta pravá pro Tebe.

Stromy jsou jednou z nejtypičtějších (a nejjednodušších) odrůd grafů. Ledacos pro ně umíme řešit mnohem rychleji než pro obecné grafy, tak se pojďme podívat, jak se to dělá. Předvedeme několik obecných technik pro práci se stromy: DFS očíslování, „vandalskou indukci“, intervalové reprezentace. Různé rozklady: heavy-light, Fredericksonův, separátorový a ST-stromy.

Ukážeme si (téměř) obecný způsob, jak naučit datové struktury zapamatovat si celou svou historii. Předvedeme si, jak tuto historii modifikovat a k čemu to je celé dobré.

Při návrhu algoritmů nás nejčastěji zajímá časová složitost na nejhorším možném vstupu. Co když ale většinou potkáváme lehké vstupy? V reálném světě občas seznamy, které chceme setřídit, už jsou skoro setřízené a plno grafů, ve kterých hledáme cesty, jsou řídké, rovinné, nebo jinak krotké. Ukážeme si, že u nějakých problémů jde mít to nejlepší z obou světů: algoritmus, který je na těžkých vstupech rychlý a na lehkých ještě rychlejší. Povíme si taky něco o splay stromech a pairing haldách, dvou beyond-worst-case datových strukturách.

Dynamické programování je programátorská technika využívající velice prostinkého nápadu: Proč něco počítat několikrát, když to mohu spočítat jednou a výsledek si uložit? Na této přednášce si ukážeme, že tento jednoduchý nápad může pomoci efektivně vyřešit i poměrně obtížné úlohy.

Někdy potřebujeme najít podřetězec ve velkém množství textu. Stromeček trochu připomínající ten biologický aneb trie. Proč se ve vstupu vracet neboli Knuthův-Morrisův-Prattův algoritmus. Hledání více řetězců najednou podle Aha a Corasickové. Okénkové hešování Rabina a Karpa.

Jazyk C patří k nejrozšířenějším jazykům, hodí se pro low-level programování i kusy kódu, které mají zejména být rychlé. Představíme si datové typy a běžné programové konstrukce, vysvětlíme si základy práce s ukazateli a také se seznámíme se standardními knihovnami jazyka C.

Povídání o méně známých částech Pythonu. Datový model: objekty, třídy, metatřídy, dekorátory a deskriptory. Magické metody a na nich postavené protokoly. Generátory, generátorové výrazy a funkcionální styl programování. Asynchronní a paralelní programování. Zajímavé moduly nejen ze standardní knihovny. Propojení Pythonu s C, ...

Rust je relativně nový jazyk, co si dělá ambice nahradit C. Programy napsané v Rustu zaručeně bezpečné, pro vhodně zvolenou definici slova „bezpečné“. Ukážeme si, co dělá borrow checker, co je to discriminated union a co dokáží generické funkce.

Jak vyvíjet program delší dobu a nezbláznit se u toho. Různé systémy pro správu verzí od diff/patch přes CVS a SVN až ke Gitu. Jak Git funguje: stromy, commity, větve, tagy. Merge mezi větvemi nebo mezi různými počítači.

Tvrdí se, že číst kód je mnohdy těžší, než ho psát – dokonce i po sobě, stačí krátká doba. Je několik obecně uznávaných pravidel, jak kód psát a jak ne, aby byl hezký a dobře čitelný. Od základních (rozumná pojmenovací konvence, systematické odsazování), až po to, kdy opravdu použít goto, jak členit program na funkce a jak využít nějaké třídy, moduly a podobně. Jak napsat užitečný komentář nebo dokumentaci. A kdy se vyplatí se na všechna tato pravidla vybodnout.

Jak si schovat data do relační databáze a jak je tam zase najít, ideálně rychle. Definice tabulek a indexů. Dotazy a jejich skládání a vnořování. Pohledy, funkce a triggery. Transakce a různé druhy konzistence. Rozdíly mezi dialekty SQL.

Vydáme se do země skřítků, kteří pohánějí počítače. Počítačové architektury od hodinek po superpočítač od Craye, jejich křivolaká historie i současnost. Co je to procesor, jak se programuje a jak se chová. Různé druhy pamětí a jejich cacheování. Jak procesory komunikují s okolím – sběrnice, čipové sady, vstupní a výstupní zařízení. A co když je procesorů několik, nebo třeba pár tisíc? Přednáška bude praktická: pár počítačů při ní rozebereme a možná i nějaký postavíme.

Operační systémy jsou pro mnohé programátory black box – víme co od nich chceme a co všechno za nás umí zařídit, ale málokdo si umí představit, jak to ty operační systémy vlastně dělají. Povíme si, jak vypadá architektura dnešních operačních systémů, tedy co všechno za nás umí takový operační systém zařídit, co naopak za něj zařídí procesor a jak to všechno funguje dohromady. Správa procesů a vláken, plánování, synchronizace. Paměť, adresace a její přidělování. Volání syscallů.

Dnešní procesory mají několik úrovní vyrovnávacích pamětí (cache), což způsobuje, že ačkoliv si jsou všechny části paměti rovny, některé si jsou rovnější. Jak taková cache funguje? Jak se procesor rozhodne, co si v ní zapamatuje a co vyhodí? Jak toho můžeme využívat při programování, aby naše programy běžely rychleji? Předvedeme kousek teorie i několik praktických ukázek s poněkud překvapivým chováním.

Jak vytvořit jednoduchý Linuxový server, který poskytuje služby vaší domácnosti, nebo třeba nějaké větší síti. Co se tam hodí provozovat? Povíme o SSH, kličích, šifrování, systemd, Apache a Nginxu, nastavení mailového serveru i DNS. Jak server zabezpečit před útočníky, jak před ztrátou dat a jak před uklízečkou. Vše si vyzkoušíme prakticky, třeba na virtuálním počitači.

Volné navázání na NET aneb máme fungující síť a chceme nad ní provozovat složitější komunikaci. ICMP aneb servisní protokol Internetu, DNS a překlad doménových jmen, jednoduché textové protokoly jako je FTP, SMTP, IMAP nebo nejpoužívanější webové HTTP. U HTTP se zastavíme trochu déle – hlavičky, návratové kódy, cookie, více domén na stejné IP adrese a SSL certifikáty.

Praktické ukázky různých útoků na webové stránky. Od útoků na server samotný (neošetřené parametry, SQL injection, template injection) přes kradení přihlašovacích cookies pomocí XSS útoků až po přinucení udělat uživatele něco, co udělat nechce pomocí CSRF útoků. Vše si budeme prakticky ukazovat a zároveň demonstrovat, jak se proti těmto útokům bránit.

Pokročilejší a občas nečekané aplikace základních kryptografických primitiv. Jak přesvědčit server, že známe heslo, aniž bychom mu ho posílali? Jak zajistit, aby útočník nemohl dešifrovat komunikaci, ani když dodatečně získá soukromý klíč? Jak funguje BitCoin (decentralizovaná digitální měna) či Tor (protokol znemožňující komukoli po cestě vědět, kdo s kým komunikuje)?

Matrix je moderní chatovací protokol navržený tak, že každý si může provozovat svůj server, který se domluví se všemi ostatními servery. Pojďme nahlédnout, jak taková věci uvnitř funguje. Synchronizace stavových grafů a spousta zajímavé kryptografie. Zkušenosti (dobré i špatné) z provozování vlastních serverů.

Ukážeme si, jak počítače přemýšlí při řešení problémů a jakým způsobem hledají řešení. Volně se dostaneme k prohledávání stavového prostoru (který bývá exponenciálně velký) a ukážeme si různé jak informované, tak neinformované techniky pro jeho procházení. Setkáme se třeba s algoritmy, které jsou použity v GPS.

Co je to strojové učení? Jaké typy strojového učení existují? Začneme u jednoduché lineární regrese, přes perceptron až skončíme u kouzelného slovíčka neuronové sítě. Povíme si rozdílné druhy neuronových sítí a nakonec si odskočíme k algoritmu, který nepotřebuje kromě surových dat nic navíc a dokáže dělat užitečné věci.

Tato navazující přednáška na Neuronové sítě se zabývá transformery, což je pokročilý model pro zpracování přirozeného jazyka. Transformery se staly revolučním nástrojem v oblasti strojového učení a jsou základem mnoha moderních aplikací, jako jsou strojový překlad, rozpoznávání řeči nebo generování textu. Během přednášky se seznámíte se základními principy transformerů, jako je self-attention mechanismus a enkodér-dekodér architektura. Budeme také diskutovat o jejich výhodách a omezeních a představíme některé příklady jejich úspěšného využití v různých oblastech. – Anotaci napsal ChatGPT

Vyhlídkový výlet světem rychlé herní počítačové grafiky (na rozdíl od pomalé fotorealistické v HIPPOGOD). Dozvíte se, jak se vyráběly hezké pixely rychle a efektivně na různých érách hardwaru i softwaru, od konce devadesátek až po současnost. Jak funguje vykreslování a GPU zevnitř a co jsou všechny ty obskurní zkratky v grafických nastaveních. A taky pár her rozpitváme zaživa frame debuggerem.

Z předchozí přednášky máme představu o tom, jak vypadá pěkná sazba. K její výrobě nám pomůže typografický systém TeX. Praktická přednáška s ukázkami použití TeXu od hladké sazby knihy až po zběsilosti hraničící s programováním. Jak do TeXu vkládat obrázky a jak to raději nedělat. Kde shánět další informace: TeXbook, TeXbook naruby a další zajímavá literatura. Praktické rozdíly mezi různými dialekty TeXu. Všelijaká rozšíření: pdfTeX, eTeX, LuaTeX.

Rádi byste své řešení KSP ozdobili hezkými obrázky? Dají se nakreslit ručně, ale často je snazší obrázky programovat. Předvedeme Asymptote, což je programovací jazyk určený na kreslení 2D a 3D obrázků. Také se zastavíme u jeho předchůdců MetaPostu a MetaFontu a knihovny pro vektorové kreslení Cairo.

Jak funguje znaková sada Unicode, která se snaží zapsat všechny jazyky světa? Codepointy versus glyfy. Kombinující znaky, čtvero normálních forem a pátá lehce nenormální. Typografické a neviditelné znaky. Co všechno prozradí Unicode Character Database. Uložení v paměti: formáty UCS-2, UCS-4, UTF-8 a UTF-16, nešvar s BOM. Tajemný svět emoji. Jak se s Unicode programuje? A jako vždy: bezpečnostní problémy.

Když nevíme, jak se v algoritmu rozhodnout, někdy pomůže ponechat to náhodě a prostě si „hodit kostkou“. Dokážeme sestrojit algoritmy, které jsou rychlé, i když spravný výsledek vydají jen v 99 % případů. Ale i takové, které odpoví správně vždycky, ale rychlé jsou jen v průměru (třeba QuickSort). Též ukážeme, jak pomocí náhody zabraňovat kolizím v hešování.

O jazycích přirozených, programovacích a matematických, jejich popisu a rozpoznávání. Začneme těmi nejjednoduššími: regulární jazyky a výrazy, konečné deterministické a nedeterministické automaty. Pak budeme stoupat po příčkách Chomského hierarchie, kam až to půjde. Jak výpočetně silný je třeba takový automat na kafe?

Game of Life je dvojrozměrný svět, ve kterém se buňky vyvíjí podle průzračně jednoduchých pravidel. Už desítky let v tomto světě objevujeme další a další zajímavé jevy. Tak do něj také nahlédneme, prozkoumáme souvislosti s evoluční biologií i s algoritmy. Též uvidíme, jak Život zapadá do obecnějšího světa buněčných automatů.

Jak dokázat, že jsme našli nejrychlejší možný algoritmus na danou úlohu? To je docela těžká otázka, ale aspoň u několika úloh na ni dokážeme najít odpověď. Nutnost přečíst celý vstup (opravdu?). Měříme množství informace: vážení kuliček, hledání, třídění a různost prvků v porovnávacím modelu. Omezená paměť a princip holubníku: závorkování. Komunikační složitost: palindromy na jednopáskových strojích. Nekonstruktivní důkazy existence těžkých problémů.

Pokud jsou data příliš velká, můžeme je zkusit zkomprimovat. Předvedeme základní kompresní algoritmy: triviální (RLE), slovníkové (LZ77), statistické (Huffmanovo a aritmetické kódování) a některé pokročilejší techniky, jako třeba Burrowsovu-Wheelorovu transformaci (BZIP). Zmíníme se o kompresi zvuku, obrazu a videa (prediktory, wavelety, všelijaká ztrátová komprese).

Jak pracovat s pravděpodobností matematicky. Ukážeme si pravděpodobnosti jevů, nezávislé jevy střední hodnotu, náhodné proměnné a další. Také si vše procvičíme na několika příkladech. Pravděpodobnost bývá mnohdy neintuitivní, proto poukážeme na časté nachytávky z reálného života. Pokud zbyde čas, tak si také ukážeme, jak se dá pravděpodobnost využít v informatice.

Jak komunikovat po lince, která průměrně každý k-tý bit přenese špatně? K tomu se hodí teorie samoopravných kódů, která nás naučí: vzdálenost slov a jejich souvislost s detekcí a opravou chyb, paritní a lineární kódy, perfektní kódy, Reed-Solomonovy a vůbec polynomiální kódy a několik dolních odhadů nádavkem. A jak s teorií kódů souvisí třeba čeština?

Lineární programování je ohromně užitečná optimalizační technika. V přednášce se nebudeme zabývat teorií, a raději si ukážeme co nejvíce praktických využití této techniky zejména pro návrh efektivních algoritmů. Od problémů, kde lineární programování číhá v přestrojení, až k efektivnímu řešení NP-těžkých problémů, pokud nám stačí jen řešení přibližné. Zaokrouhlování, randomizace, celočíselné programování a další triky.

Něco málo o vektorech, maticích a jak pomocí nich řešit lineární rovnice. Pokud zbyde čas, tak také o tom, jak matice souvisí s otáčením nebo zvětšováním a jak málo stačí k tomu, abyste si z pár předpokladů vyrobili použitelný výpočetní systém.

Co a k čemu je teorie čísel. Počítání v kongruenci, Euklidův algoritmus a jeho použití. Konečná tělesa a Malá Fermatova věta. Prvočísla a Eratosthenovo síto. Čínská zbytková věta a její algoritmická verze. Jak si odvodit kritéria dělitelnosti.

Při navrhování algoritmů a počítání jejich složitosti narazíme na celou řádku zajímavých a ne úplně triviálních kombinatorických problémů, a tak se naučíme, jak na ně. Základní triky s faktoriály a kombinačními čísly, sčítání konečných a občas i nekonečných řad, rekurentní rovnice a princip inkluze a exkluze. Možná se také potkáme s Dlouhým, Širokým a poněkud zmatenou šatnářkou.

Jak matematici dokáží vzít „obecné“ a ještě více jej zobecnit. Ukážeme si, jak zkoumat matematické operace, aniž bychom řešili, jestli se bavíme o sčítání, násobení, nebo skládání zobrazení. Pár magických slov pro představu: monoidy, grupy, okruhy, obory integrity, tělesa, vektorové prostory, polynomy, částečná uspořádání, booleovy algebry, filtry, ideály. Také si povíme, na co se takové věci dají použít – a jak to celé souvisí s prvočísly, jak se šifrováním a jak s osovou souměrností.

Kolik existuje binárních stromů? Kolika způsoby jde uzávorkovat výraz? A kolika způsoby projít čtvercovou mřížku, aniž bychom překročili úhlopříčku? Kam oko pohlédne, všude se skrývají Catalanova čísla. Kromě případů, kdy za ně zaskakují čísla Fibonacciho. Povídání o dvou zajímavých posloupnostech a jejich početném příbuzenstvu. Dlouhá cesta od hezkého vzorečku k rychlému algoritmu.

Možná vás už také zarazilo, že některé fraktály nejsou ani dvourozměrné, ani třírozměrné, ale něco mezi tím. Pojďme se podívat, co to znamená. Cestou potkáme různé zajímavé partie matematiky (jako třeba metrické prostory a teorii míry) a různá podivuhodná zvířátka: Cantorovo diskontinuum, von Kochovu vločku a Hilbertovu křivku.

Malá inventura zvuků, které lidé dovedou vytvářet, a jejich použití v komunikaci. Různé způsoby vytváření a modulace zvuku. Kolik různých B dokážete říci? Fonetické kontrasty a co si z nich různé jazyky vybraly. Rázy, polosamohlásky a jiní obyvatelé polosvěta. Přízvuk kontra délka. Asimilace, přehlasování a další „principy líné huby.“ Vše prakticky procvičíme.

Hodí se vám, aby postavy ve vaší hře nebo povídce mluvily neznámým jazykem? Tak si vymyslete vlastní! Ale jak na to? Jak se vytváří různé vrstvy jazyka: slovní zásoba, morfologie, gramatika, frazeologie, ale i písmo a výslovnost. Proč si pořídit imaginární uživatele a imaginární historii. Jak najít správnou míru nepravidelnosti. Čím se můžeme inspirovat z existujících jazyků a čím raději nechceme.

Řekneme si něco o tom jak funguje burza a co přesně znamená, že akcie má nějakou hodnotu. Také si ukážeme jak jednoduše začít obchodovat na burze a co takoví obchodníci na burzách řeší za problémy.

Tanec za doprovodu hudby doprovází lidstvo od nepaměti. Může mít podobu pečlivě nacvičovaného rituálu, ale také nám může sloužit jako jazyk, kterým vyjadřujeme své pocity a sdílíme je s ostatními. Zkusme zapomenout na všechnu taneční teorii a jen tak se ponořit do hudby, pohybovat se podle ní a vyprávět tím svůj příběh. Až nám to trochu půjde, zkusíme se naladit na ostatní a propojit svůj příběh s jejich.

Pobavíme se o základech první pomoci. Jak správně vyhodnotit situaci a kdy je potřeba volat pomoc? Jak se postarat o člověka v bezvědomí, jak kontrolovat životní funkce a jak člověka stabilizovat do příjezdu pomoci? Ukážeme si, jak málo stačí k záchraně života a naučíme se nebát se první pomoci. A také, že naše bezpečí je v každé situaci na prvním místě.

Základy pájení jednoduchých obvodů. Budeme mít několik pájecích stavebnic a trénovacích destiček (jak pro pájení velkých „nožičkových“ součástek, tak i malých SMD součástek), několik páječek, držáků a dalších věcí. Co si kdo spájí si bude také moci odnést.

Umelý jazyk toki pona pozostáva zo slovnej zásoby veľkosti približne 120 slov a jednoduchej gramatiky, vďaka čomu je možné naučiť sa ho za pár dní. Pochopiť gramatické pravidlá sa však dá aj omnoho rýchlejšie, preto sa ich na tomto workshope skúsime naučiť a potom sa na základe nich porozprávať.

Srdcem mnoha dnešních technických hraček je mikrokontrolér. To je čip, na kterém je integrovaný nejen procesor, ale i paměť a spousta zajímavých periferií. Ukážeme si, jak se mikrokontroléry programují, jaké periferie typicky obsahují a jak je používat ke komunikaci s okolním světem. Pak si to vyzkoušíme prakticky na vývojových deskách s mikrokontrolérem rodiny STM32.

Linux (někdy též GNU/Linux) je open-source operační systém s širokým uplatněním od různých průmyslových zařízení přes WiFi routery až po osobní počítače a vysoce výkoné servery. Na tomto workshopu se s ním budeme moct prakticky seznámit s jeho použitím zejména na osobních počítačích (včetně instalace do vlastního zařízení). Pokročilejší uživatelé mohou pokračovat zprovozňováním osobního serveru či zaučování se s jinými doposud neznámými částmi ekosystému okolo Linuxu. Workshop bude probíhat formou samostatné práce účastníků na jejich noteboocích nebo virtuálních strojích s možnou konzultací postupu a případné pomoci při řešení zapeklitých problémů.

Godot je open-source herní engine, který se hodí pro vytváření 2D ale i 3D her. Během workshopu si postupnými krůčky ukážeme, jak se dá vytvořit jednoduchá 2D hra. Ukážeme si animace, práce s kamerou, zakomponování zvuků do hry a mnoho dalšího. Skončíme s menší hrou, která bude ideální startovní můstek pro další možné experimentování.

Volné povídání o tom, co se všechno skrývá za organizováním různých seminářů a podobných akcí, primárně pak KSPčka. Jaká práce, jaké radosti a jaké starosti s sebou organizování nese, co se přitom člověk může naučit a také pár cenných rad do života. Jak se z toho nezbláznit a pár bláznivých příhod k tomu.

Pojďme si popovídat o výbavě na pobyt v přírodě. Čím se liší jednotlivé druhy spacáků, jak se dají porovnávat? A co karimatky a vařiče? Do jakých se hodí podmínek? Podíváme se společně na to, jaká výbava se hodí kam a proč. Čím se liší věci na přespání zimě od těch na léto. O čem všem uvažovat při nákupech.

Přednáška, na které poodhalíme tajemství, která se skrývají za západním hudebním systémem. Od základů, jako jsou intervaly a akordy, až po hlubší koncepty jako je harmonie a fyzika zvuku. Jak si složit vlastní písničku, proč mollové akordy znějí smutně, a jak "lo-fi beats to relax/study to" do celého toho systému tak trochu (ale ne úplně) hází vidle. Když bude chuť, voicingy, substituce, Pythagorejské koma, nezápadní hudba a mnoho dalšího.

Stáže jsou skvělé, získáte nové kamarády a vaší kariéře to možná pomůže více než vysoká škola. Není ale jednoduché se tam dostat. Probereme, jak fungují pohovory v prestižních firmách jako Google, Meta nebo Jane Street. Ukážeme si, podle čeho se u pohovorů hodnotí, na co se zaměřit a jak jednoduše získat body navíc.