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

O algoritmech značně magických a nečekaných. Jak násobit n-ciferná čísla rychleji než v kvadratickém čase. Kouzlo na slévání setříděných posloupností v konstantním prostoru. Isomorfismus stromů pomocí přihrádkového třídění. Bitové kejklířství. Hledání největší díry.

Některé úlohy jsou tak těžké, že je za dobu existence tohoto vesmíru nedokážeme vyřešit (naneštěstí to zatím o většině takových úloh ani nesvedeme dokázat). Co kdyby nám ale stačilo i řešení, které je nejhůře o 10 % horší, než to optimální? Ukážeme si pár klasických aproximačních algoritmů a aproximačních schémat: 2-aproximace bin packingu, obchodní cestující ve 2D, množinové pokrytí, MaxSAT a další.

Ukážeme si, co dělat když běžné intervalové stromy nestačí. Intervalové stromy na maticích, řídké intervalové stromy, rozšíříme intervalové stromy do více rozměrů a nakonec ukážeme Segment Tree Beats, podporující divoké intervalové updaty.

Ukážeme si dynamické programování tak, jak ho neznáte. Od subsetové dynamiky, přes meeting at the middle až po geometrii v dynamickém programování. Bude doprovázeno množstvím příkladů.

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řednáška o tom, co se stane, když do vrcholů grafu umístíme počítače a necháme je, ať si mezi sebou povídají. Některé grafové problémy, jako například vrcholové obarvení, umíme v takovém modelu vyřešit skoro v konstantním čase – a to přesto, že žádný vrchol v tak krátkém čase ani nemá šanci zjistit, jak vypadá celý graf. Projdeme si různé klasické grafové problémy, podíváme se, jak se chovají v tomhle světě a ukážeme si na ně různé algoritmy – některé vypůjčené z klasického světa, jiné vybudované na zelené louce. Taky se podíváme, kdy už to rychleji nejde, proč jsou nějaké sítě lepší než jiné a jak s tím vším souvisí toky v sítích.

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.

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.

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

Zrychlovat procesory už moc neumíme, tak si jich pořídíme více. Jak psát programy, které běží paralelně ve více procesech nebo vláknech. Jak vlákna usměrnit, aby nám nerozbila program na nečekaných místech. Rozebereme, jak fungují zámky, kdy je musíme použít a jakou cenu za to platíme.

Používáte Git pro všechny své programy a k svačině místo novin čtete commit logy svých oblíbených projektů? V tom případě pojďme nahlédnout pod pokličku, jak Git funguje uvnitř. Reprezentace historie pomocí hešování grafů. Pracovní strom, index, commity a jejich adresy, větve. Pack files jako elegantní způsob komprese dat na disku i na síti. Kouzelnické triky: hledáme bugy půlením historie, přepisujeme dějiny, automaticky konvertujeme soubory. Git v praxi: jak se liší správa zdrojáků v projektech o jednom, deseti a tisíci programátorech. Udržujeme patche k cizímu programu aneb StGit.

Odložme na chvíli své myše a pojďme si vyzkoušet textový editor, který umí poslouchat na slovo. Pravda, budeme se ta slova muset chvíli učit, ale výsledek bude proklatě efektivní. Základní příkazy, textové objekty, regulární výrazy, makra, kouzla. Neovim, Lua a language servery. Vimovité ovládání jiných programů, třeba webového prohlížeče.

Po chvíli zjistíme, že nám lokální a globální proměnné nestačí a je potřeba paměť alokovat dynamicky. Co všechno si musíme udělat sami a co se děje programátorovi „za zády“. Mapování adresního prostoru, ruční alokování a vracení paměti a problémy s tím spojené (chyby programátora), počítání odkazů a daň s nimi spojená (a hele, cyklus), odklízeče odpadu (mark & sweep, kopírovací, generační a jiné triky).

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

Multiplikativní konstanty se sice „schovají pod óčko“, ale často mohou dělat rozdíl mezi instantní odpovědí a něčím, na co se nikomu nebude chtít čekat. Dnešní procesory už opravdu nejsou jednopáskové Turingáče, ale multijádrová monstra plná vektorových instrukcí a podivných optimalizací. Ukážeme si zpoustu nástrojů, které nám pomohou schopnosti našeho CPU využít na plno – OpenMP, vektorové extenze a intrinsika, argumenty kompilátoru, profilování a mnoho dalšího.

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. Něco si vyzkoušíme i prakticky na STM32.

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.

Dnes již není grafická karta jen placka převádějící digitální pixely na analogový signál. Dá se na ní počítat kde co. Zde si představíme trochu technologie CUDA a compute shadery v OpenGL a zmíníme, že tento ďábelský kus HW umí počítat zatraceně rychle, ale pokud tam uděláme malou chybičku, tak také zatraceně pomalu. Zmíníme, proč tomu tak je, jaké druhy paměti můžeme v programu používat a co je to multiprocesor.

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.

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

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

Příroda je nádherná a celá tisíciletí se jí inspirujeme. Kolik už inspirovalo spisovatelů, básníků a malířů. Nyní jsou na řadě programátoři. Když si nebudeme vědět s nějakým těžkým problémem rady, tak zkusíme nenápadně opisovat od přírody.

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.

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.

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.

Jak zařídit, aby fotka nezabírala 40 MB? Povíme si o typických formátech PNG a JPEG, prozkoumáme, kdy se hodí který, a podíváme se jim pod pokličku. Naučíme se vymýšlet nové pixely při zvětšování obrázků. Také nakousneme vektorové obrázky a Bézierovy křivky.

Stručný úvod do kvantového počítání. Kvantová superpozice stavů výpočtu a její kolaps při měření. Základní kvantové operace: negace, řízená negace, permutace, Hadamardovo hradlo, Tofolliho hradlo. Kvantová teleportace a jakto, že není v rozporu s teorií relativity. Groverův algoritmus na hledání v odmocninovém čase. Kvantová Fourierova transformace a Shorův algoritmus pro faktorizaci.

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

Stručný úvod do bioinformatiky. Ukážeme si základní algoritmy na local a global alignment (BLAST, Smith-Waterman a jejich modifikace). Dále se zaměříme na algoritmy na sestavování referenčních genomů z jednotlivých readů a ukážeme si některé moderní algoritmy založené na k-merových metodách.

O světě jde sehnat spousta zajímavých dat ve strojově zpracovatelné podobě: obce a domy v nich, linky hromadné dopravy, katalogy hvězd, slova v češtině, katalog pokémonů, ... Pojďme se podívat, jak s daty zacházet. Naučíme se číst různé formáty dat od CSV až po XML, data zkoumat, filtrovat a kreslit podle nich pěkné grafy. Vyzkoušíme si prakticky v Pythonu. Předvedu své oblíbené nástroje, pojďte ostatním předvést ty své.

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?

Jak zjistit, jaký tvar má graf nějaké funkce? Jak najít její minimum? Jak spočítat délku spirály nebo objem sudu (třeba i čtyřrozměrného)? Jak spočítat sin x nebo třeba π? Na to všechno se hodí limity, derivace a integrály. Nejprve si o nich vybudujeme jednoduchou geometrickou představu, pak je nadefinujeme pořádně a naučíme se s nimi počítat.

Teorie grafů trochu teoretičtěji. Grafy nakreslitelné jedním tahem a ty, které jdou nakreslit bez křížení hran. Jak se dají obarvit mapy a jak všechny grafy? Co znamená graf popárovat a kdy to jde dokonce perfektně?

Pokračování teorie čísel, které nás dovede až k RSA – asi nejpoužívanějšímu asymetrickému šifrovacímu algoritmu dnešní doby. Počítání modulo složené číslo a Eulerova věta. Jak RSA funguje, proč funguje a jestli bude ještě fungovat. Generování klíčů, faktorizace kontra testování prvočíselnosti. Časová složitost aritmetiky.

Historie matematiky je dlážděna trampotami s nekonečnem. Začalo to roztomilým problémem s želvou pana Zénona a vedlo až k poněkud děsivým paradoxům 18. století. V moderní době jsme se proti tomu obrnili teorií množin, na níž je dnes takřka celá matematika postavena. Jak se taková teorie buduje a jak se pomocí ní popisují nekonečné objekty. Množiny a jejich velikosti. Cantorův diagonální trik. Ordinály a houšť kardinálů. Potenciální kontra aktuální nekonečno. Jak si pořídit přirozená čísla a jak ta reálná. Potíže s axiomem výběru.

Pokud budeme v životě věřit všemu, co je „přeci zřejmé“, dostaneme se brzy do potíží a v matematice to platí dvojnásob. Proto své teorie musíme stavět pečlivě. Na to si filosofové a matematici pořídili logiku. Ukážeme, jak funguje výroková a predikátová logika, co je to výrok, axiom a důkaz. Vybudujeme pár jednoduchých teorií a podíváme se, co dovedou, a co už ne. Důkazy za nás ověří počítač, aspoň když mu trochu pomůžeme. Nadšení trochu ochladí Gödelova věta: ať děláme, co děláme, vždy zbude nějaké nerozhodnutelné tvrzení. Pomůže přidávat axiomy? Asi ne, ale za odměnu získáme mnoho různých matematik. A dá-li bůh, stihneme dokázat jeho existenci i neexistenci :–).

Jak se na počítači kreslí křivky, které „vypadají hezky“, třeba tvar karoserie auta nebo tvar písmenka? Kružnice a jiné kuželosečky se k tomu moc nehodí, tak se poohlédneme po obecnějších křivkách. Základy matematiky okolo Bernsteinových polynomů, Bézierových křivek a spline funkcí. Práce s křivkami pomocí rekurzivního rozkladu a de Casteljauova algoritmu. Matematické modelování estetiky.

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.

O češtině časů minulých, současných i (potenciálně) budoucích. Kde se čeština vzala a jak souvisí s ostatními evropskými jazyky. Co jsme během staletí získali, o co jsme přišli a o co nejspíš brzy přijdeme. A je to škoda? Vykrádáme cizí jazyky a ony zase nás. Kolik je češtin a která je ta správná? Proč už Jan Hus spílal Pražanům? Pojďme navrhnout pravopisnou reformu!

Jak ze neztratit v terénu a jak se neztratit na moři. Vývoj umění navigace. K čemu je důležité slunce a hvězdy, ale proč mořeplavcům nestačí, alespoň dokud neobjevíme hodinky. Použití mapy, busoly a GPSky. Orientace bez pomůcek a použití Ariadniny nitě. Bleskový úvod do sférické astronomie a časomíry čili jak (ne)postavit sluneční a třeba i měsíční hodiny. Jak reprezentovat mapu v počítači a jak raději ne. Jak zapisovat polohu místa na Zemi (přestože Země má tvar podivně nakousnuté hrušky) a kolika způsoby to jde. Různé druhy map a jejich (z)kreslení. Jak se neztratit v kartografii. Praktické cvičení v terénu.

Čá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, ...

Když se počítače poprvé staly dostupné pro běžné smrtelníky, nic moc ještě neuměly. Ale měly k sobě přibalený manuál od nějakého programovacího jazyka. A tak lidi začali programovat. A začali si hrát. Psali malé hry, ale také prográmky, které kreslily něco hezkého jen tak. Takzvané „intra“ nebo „dema“. A pak se začali předhánět a soutěžit v tom, kdo udělá lepší, hezčí, technicky propracovanější demo. Někdy s limitem na velikost 64 kb, někdy 4 kb, někdy bez limitu. A tak se v průběhu desetiletí vyvinula demoscéna. Pojďme se podívat na ty nejhustější dema! A možná si i říct něco o tom jak fungují.

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.

Rozebereme si akordeón a ukážeme si, z jakých částí pozestává, jak se ovládá a kde se berou tóny. A jak některé tyto části svoupomocně opravit. Rěkneme si jak na akordeón (ne)hrát a třeba si něco i zaspíváme.

Praktický workshop, na kterém si zalétáme. Akrojóga je párová aktivita kombinující prvky jógy a akrobacie. Zní to strašidelně? Je to lehčí (a bezpečnější), než název napovídá, žádná salta ani žonglování s nožemi nad propastí dělat nebudeme. Pokud rád/a visíš hlavou dolů a/nebo rád/a ležíš, přijď!

Po letech člověk začne mít pocit, že už vše zná, vždyť přece umí udělat interaktivní rebase z příkazové řádky, parametry rsyncu zná nazpaměť a vimovým makrem za pár chvil přechroupe tisíci řádkové dokumenty. Je tak ještě co objevovat? Zjistil jsem, že je, a rád se o zkušenost podělím. Řeč bude o editoru Emacs z dílny GNU. Ten je známý pro svou skriptovatelnost (pravda, ve vlastním dialektu LISPu), klávesové zkratky o nichž se ani uživatelům vimu nezdálo a též pro svou těžkotonážnost. Na všech těch podhledech něco je a v tom je právě to kouzlo. Neodpovím, který textový editor je ten nejlepší na světě, ale ukážu další možné pohledy na svět, jež se hodí znát, i kdyby se přes ně člověk nakonec dívat nechtěl.