Co to jsou grafy, jak je v programech reprezentovat a hlavně k čemu se dají použít. Prohledávání grafu do šířky i do hloubky. Hledání nejkratších cest: Dijkstrův a Floydův algoritmus. Minimální kostry a Union-Find problem.

O problému hledání cest v grafech trochu podrobněji. Obecné relaxační schéma, Bellmanův-Fordův a Dijkstrův algoritmus a jejich zrychlení pomocí různých datových struktur. Potenciálová redukce a heuristiky (třeba A^*), zaokrouhlování délek hran. Souvislosti s násobením matic: tranzitivní uzávěr, Seidelův algoritmus, Kleeneho algoritmus a regulární výrazy.

Předvedeme si několik rychlejších algoritmů pro problém maximálního toku. Dinicův algoritmus a jeho mnohá vylepšení. Všelijaké příbuzné problémy: assignment problem, aneb hledání nejlevnějšího bipartitního párování. Maximální tok minimální ceny, aneb co když za průtok trubkami musíme platit? Ukážeme si algoritmus založený na postupném vylepšování a předvedeme si na něm obecnou myšlenku, kterou můžeme použít u optimalizačních problémů. Nahlédneme, že všechny zmíněné problémy můžeme popsat jako lineární programy, a proč se to občas vyplatí dělat. Pokud zbyde čas, řekneme si, co se změní, když budeme chtít vedle ropy v jedné síti zároveň přepravovat i čaj a Kofolu, a proč je to problém výrazně těžší, ale přesto řešitelný.

Důmyslnější varianty vyhledávacích stromů: splay stromy, BB-α stromy, rankové stromy, vícerozměrné stromy. Chytřejší haldy: binomiální, Fibonacciho, rank-pairing. Amortizovaná analýza složitosti. Též několik přátelských randomizovaných datových struktur: skip listy a treapy.

Zapomeňte na pracné vyvažování vyhledávacích stromů. Místo toho zavedeme triviální pravidlo: pokaždé, když pracujeme s nějakým prvkem, vytáhneme ho do kořene stromu. Ukážeme, že toto pravidlo stačí na dosažení logaritmické složitosti, tedy aspoň amortizovaně. Také dokážeme, že Splay strom je nejhůře konstanta-krát horší než libovolný jiný strom, a možná i spousta dalších magických vlastností.

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

Některé algoritmy (kešování, kupování lyží, chytání krav) fungují tak, že vstupní data dostávají jaksi postupně. Máte-li se rozhodnout, kdy si půjčit lyže a kdy si je lepší je koupit, je to jednoduché, když víte, kdy si zlomíte nohu. Ale jaká je optimální strategie, když to nevíte?

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.

Suffixový strom je zajímavá datová struktura, pomocí níž jde vyřešit většinu řetězcových problémů v lineárním čase. Podíváme se, jak suffixový strom vypadá, k čemu se hodí a jak ho sestrojit. Též prozkoumáme několik příbuzných zvířátek, jako třeba suffixové pole a suffixový automat.

Při analýze algoritmů a datových struktur nás většinou zajímá chování na nejhorším vstupu. Reálný svět ale často není tak pesimistický – čas od času třídíme skoro setříděné pole nebo ve vyhledávacím stromě přistupujeme k těm samým prvkům stále dokola. Ukážeme si datové struktury, které se umí přizpůsobovat obtížnosti vstupu a na snadných vstupech pracovat klidně i v konstantním čase na operaci.

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.

TypeScript je nadstavba nad JavaScriptem, která do něj přidává statické typování. A nejen ledajaké! Umí spoustu pěkných věcí, jenž v ostatních mainstream jazycích nenajdeme. Ukážeme si, jak v něm pohodlně popsat i velmi složité koncepty, a jak moc nám tento jazyk zpříjemní psaní webových věcí oproti JavaScriptu, který je notorický svou náchylností na nenápadné chyby, které odhalíte, až jakmile vám aplikace spadne.

Funkcionální programování je přístup ke stavbě programů, který se stává rok od roku populárnějším, a to i mimo jazyky, které se běžně považují za funkcionální. Ukážeme si krásy jazyka Haskell, kde je vše funkce a sideefekty neexistují. I tak v něm ale jde zapsat úplně vše, často navíc velmi elegantně.

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.

Procesor nerozumí proměnným, podmínkám, cyklům ani jiným věcem, které jsou pro nás při programování běžné. Podíváme se, jak lze výše zmíněné konstrukce přepsat do procesorových instrukcí. Co přesně se děje při volání funkce? Jak kód vytunit, aby běžel rychleji? Také se podíváme na souvislosti s návrhem dnešních procesorů.

Jak vypadá rozhraní mezi jádrem Linux a uživatelskými programy. Co se doopravdy stane, pokud ve svém céčkovém programu zavoláme printf nebo malloc. Jak napsat program, který vůbec nepotřebuje standardní céčkovou knihovnu. Co všechno se umí chovat jako soubor a co jako signál. A což takhle komunikovat po síti?

Jak funguje Internet a počítačové sítě vůbec: od elektronů v drátech (fotonů v optických kabelech nebo elektromagnetických vln) přes komunikaci na jedné malé síti až ke komunikaci v celém Internetu. Vysvětlíme si rámce, pakety, MAC a IP adresy, routování v malých i ve velkých sítích. Jak to reálně funguje s IPv4 a NATem, co to jsou porty a jak se od sebe liší TCP a UDP. A na závěr radosti a strasti IPv6 (až ho konečně zavedeme).

Co se děje za oponou, když do prohlížeče zadáte adresu svých oblíbených stránek? A jak si takovou stránku taky pořídit? Přelet nad protokolem HTTP, seznámení s HTML a předvedení kaskádových stylů. Jak fungují dynamické stránky od formulářů až po JavaScript běžící v prohlížeči.

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

Kryptografie čili tajuplná nauka o šifrách, jejich konstrukci a hlavně o jejich luštění. Šifrovací systémy jako lego: základními kostičkami nám budou symetrické a asymetrické šifry, jednosměrné funkce a náhodné generátory. Stavět z nich budeme kryptografické protokoly na bezpečný přenos, autentikaci, digitální podpisy a třeba i na házení korunou po telefonu. Předvedeme nerozluštitelnou šifru a dokonce to o ní i dokážeme.

Programátoři si často myslí, že pro bezpečnou komunikaci stačí vybrat si z knihovny osvědčenou silnou šifru. Jak naivní! Navrhnout bezpečný protokol není maličkost a dá se při tom ledacos zpackat. Replay útoky (jak otevřít auto krabičkou za 30 dolarů), útoky na padding a na blokovou strukturu. Čí že je ten podpis? Jak nepoužívat RSA a jak nehešovat hesla. Jak náhodná jsou vaše čísla? Postranní kanály: časování, spotřeba, záření. K čemu se crackerům hodí termoska s tekutým dusíkem.

Že jsou v programech bezpečnostní chyby, na to jsme si už zvykli. Ale teprve zvolna si zvykáme na to, že mohou být i v hardwaru, dokonce v samotném procesoru. Poslední tři roky přinesly několik ošklivých překvapení tohoto druhu s veselými jmény, jako je Meltdown a Spectre. Budeme se zabývat fungováním procesoru uvnitř, zejména všelijakými triky na zrychlení výpočtu: superskalárním zpracováním instrukcí, kešováním a predikcí skoků. A ukážeme, co pokazil Intel, co AMD a jak toho jde zneužít.

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.

Máme například nemocného pacienta s určitými symptomy a chceme odhadnout, jaká nemoc ho trápí. Nebo máme nějaký stroj a chceme odhadnout, zda se porouchá. Nebo máme nějakou situaci a chceme odhadnout, co se stane dál. Bayesovské sítě jsou jedním z nástrojů, které nám umožní takovéto problémy řešit. Na rozdíl od moderních nástrojů strojového učení, které jsou často černou skříňkou, Bayesovské sítě nám umožní vidět, jak ke svému rozhodnutí došlo, a umožní nám to i vysvětlit. Povíme si, co to jsou Bayesovské sítě, jaká je za nimi motivace, jak se staví a jak se v nich provádí inference, a to jak exaktní, tak aproximační.

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.

Jeden z nejrozšířenějších formátů na předávání dokumentů má za sebou spletitou historii i dokumentaci. Ukážeme si, jak vypadá uvnitř a co se do něj dá uložit: grafické objekty, text, fonty, odkazy, všelijaké anotace a meta-data, a dokonce i kryptografické podpisy. Zmíníme se o profilech, třeba PDF/X a PDF/A. Při troše štěstí si vytvoříme jednoduchý PDF soubor ručně a možná půjde i otevřít.

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?

Teorie výpočetní složitosti opravdu důkladně. Různé definice výpočetního modelu a velikosti vstupu. Složitostní třídy a vztahy mezi nimi. Různé druhy redukcí. Třídy P, NP, L, NL, PSPACE a NPSPACE. Nedeterministické stroje, orákula, alternující stroje a polynomiální hierarchie. Neuniformní složitost.

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

Řízení těchto dvou věcí sdílí teoretický základ, který je ale aplikovatenlý na mnohem širší spektrum aplikací. Na přednášce si nejprve vybudujeme něco málo z teorie, povíme si o zpětnovazebním řízení, PID regulátorech a dalších užitečných technikák, které se v automatickém řízení uplatňují. Poté se vrhneme na nejrůznější aplikace, podle toho, kam nás přednáška zanese.

Jak rychle umíte násobit n-ciferná čísla? My to umíme lineárně. Hodí se k tomu chytrý trik pana Fouriera, který už dávno patří k matematické a fyzikální klasice. Ukážeme, co je Fourierova transformace zač, jak ji rychle spočítat a k čemu je dobrá: rychlé násobení polynomů i čísel, digitální zpracování zvuku a obrazu (spektrální analýza či třeba komprese).

Jakýkoliv problém, který lze popsat soustavou lineárních nerovnic lze vyřešit v polynomiálním čase. A to metodou lineárního programování. Povíme si základy k tomu, jak lineární program vypadá, jak se vyřeší a jak se různé úlohy dají popsat pomocí lineárního programu. Přednáška se může buď více zaměřit na samotnou teorii lineárního programování, a nebo na jeho aplikaci v různých algoritmických úlohách.

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.

Ukážeme si, jak zkoumat matematické operace, aniž bychom řešili, jestli se bavíme o sčítání, násobení, nebo třeba skládání geometrických zobrazení. Co jsou grupy, podgrupy, okruhy, tělesa a další zviřátka v algebraickém zvěřinci.

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.

Když nám někdo zadá diferenční rovnici, můžeme si ji elegantně převést na úplně jinou polynomiální rovnici, kterou už umíme snadno vyřešit. A potom řešení převedeme zpátky na posloupnost, která je řešením původní diferenční rovnice. Kouzla a čáry? Ani ne – to jen Z-transformace. Tu na přednášce nejprve vybudujeme a povíme si, jak s její pomocí řešit výše uvedené. Poté se podíváme k čemu dalšímu je vhodná a možná zbyde čas i na aplikace v teorii řízení nebo to, jak z ní odvodit transformaci Fourierovu.

Převážně nevážné a mírně nepřed-vídatelné po-vídání o jazyku i jazyce. Základní jazykové rodiny a jejich podobnosti i odlišnosti. Co má společného čínština s angličtinou a co nikoliv. Proč jeden jazyk potřebuje 15 pádů, zatímco jiný se bez nich obejde úplně. Jak se jazyky vyvíjejí a jak se navzájem ovlivňují. Kde se berou jazyková pravidla. Kde se vzalo písmo a proč se mluvený a psaný jazyk tolik liší. Jak se na jazyk dívá matematik a jak se na matematiku dívají lingvisté.

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.

Čárové kódy dnes potkáváme na každém kroku, ale jak doopravdy fungují? Prozkoumáme klasické jednorozměrné kódy (UPC, EAN, Code39, Code128), jakož i novější dvojrozměrné (QR, Aztec, DataMatrix). Kódovací a dekódovací algoritmy plus trocha matematiky okolo zabezpečení proti chybám. Další počítačem čitelné značky: RFID, bíle křížky na asfaltu, ...

Programování nemusí být jen o terminálech a webech. Ukážeme si, jak i z několika málo řádků kódu může vzniknout něco hezkého a barevného. Shadery jsou krátké prográmky, které každému pixelu obrázku přiřadí nějakou barvu. Podíváme se s jejich pomocí do hlubin fraktálů a z trošky náhody uděláme mraky nebo vodní hladinu. Přednáška bude převážně praktická.

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.

Sbírka představ o světě, kterým většina programátorů věří, ale vlastně nejsou pravdivé. Jsou všechny dny stejně dlouhé? A všechny minuty? Kolik znaků má jeden znak? Čím jsou oddělené comma-separated values? Kde ve Zlíně je tř. Tomáše Bati č.p. 202? Kolikrát že? Má každý občan EU příjmení? A jméno? A právě jedno rodné číslo? Kolik zavináčů může obsahovat e-mailová adresa?

Přednáška, na které se pokusíme od základu vybudovat hudební teorii, od vibrující struny až k písničkám. Proč má klavír 7 bílých a 5 černých kláves a proč na 80% populární hudby stačí ty bílé. Povíme si o tónech, stupnicích, rytmu, melodii, akordech. Zaměříme se na co a jak, a když bude čas, dotkeneme se i proč. Pokud Tě zajímají základy toho, jak hudba funguje, ale zatím v tom tápeš, je tato přednáška přesně pro Tebe. Podle publika můžeme volně přejít v MUSIC2.

Pobavíme se o základech první pomoci. Jak se postarat o člověka v bezvědomí? Jak o člověka, ze kterého teče krev? A jak si ošetřit odřené koleno, aby se co nejdřív zahojilo? Proč nevysávat jed z rány a nepodkládat člověku hlavu. Pokud bude zájem, tak si můžeme i něco vyzkoušet prakticky. Cílem přednášky není z vás udělat zdravotníky (to v 90 minutách ani nejde), ale spíš ukázat, že první pomoc je překvapivě logická a zábavná, a ukázat si věci, se kterými máte reálnou šanci se potkat.

Malé drony, takzvané Tinywhoops, jsou kvadrokoptéry o velikosti dlaně, se kterými je kopec srandy. Ukážeme si, jak s dronem létat, jak ho nastavit, opravit a jak se o něj a o příslušenství starat, aby dlouho vydrželo. Řekneme si něco málo o protokolu ELRS a analogovém videu. Budete si moci vyzkoušet simulátor a pokud budou podmínky příznivé, zalítáme si i venku.

Jsa skaut rád cestuji poznávat kraje domácí i cizí a při tom se spíše než na neprůstřelný plán spoléhám na šťastné náhody a lidskou dobrosrdečnost. Povím, co krásného jsem zažil, na co jsem se při tom nachytal a doufám, že vás přesvědčím, abyste to zkusili taky. Jedná se o velmi volné pokračování povídání ze Smršti 25, které tenkrát vyteklo z vyhrazeného časového bloku, jak jen mohlo. Rozhodně ale nevadí, pokud jste předehru neslyšeli.

Medvěd se nachomýtl k organizování nejrůznějších olympiád – od naší matematické až po mezinárodní informatickou. Místy vážné povídání o jejich zákulisí, prokládané spoustou příhod, které jsou tak neuvěřitelné, že se musely stát. Proč je potřeba počkat na půlnoc? Kdo chytí vačici v serverovně? Počítáte s Godzillou?

Zajímalo vás někdy, co se děje v kokpitech dopravních letadel? Co před sebou piloti vidí, čím letadla ovládají, jak vlastně dokážou přistát v noci nebo za husté mlhy? Popovídáme si o tom, jak se pilotují moderní dopravní letadla, co mají za zajímavé systémy, jak s nimi piloti interagují a o cokoliv dalšího bude zájem (a budeme o tom dost vědět).