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: transitivní 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ší.

Intervalový strom je datová struktura pracující s intervaly, se kterou se můžeme setkat v mnoha úlohách (zejména soutěžních). Řekneme si, co to intervalový strom je, jaké všechny druhy intervalových stromů existují a jejich použití si ukážeme na úlohách. Na závěr si představíme jednu „magickou“ datovou strukturu jménem Fenwickův strom.

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.

Teoretická 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ějaké problémy, jako například barvení grafu, umíme v takovém modelu vyřešit rychleji než logaritmicky – a to přesto, že poslat zprávu z jednoho konce grafu na druhý trvá až lineárně. Co když navíc omezíme velikost zpráv, aneb LOCAL vs. CONGEST. Rychlé barvení ve stromě i obecně, maximální nezávislá množina, minimální kostry. Problémy na úplném grafu: routování, třídění.

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.

Visual Studio Code je jednak univerzálním textovým editorem, jednak mocným vývojovým prostředím. Proč mít na každý jazyk jiný program, když VS Code stačí na všechno? Kromě editoru samotného si ukážeme, co všechno umí automatizovat a jak v něm vypadá efektivní workflow.

Kdo píše programy, které vždy hned fungují, ať se přihlásí. A kdo ne, ať se přihlásí na tuto přednášku. Ukážeme si různé (především nízkoúrovňové) ladicí nástroje a techniky: debugger (neboli odvšivovač) gdb, strace, a valgrind. Kdy je použít a kdy se více hodí printf a assert. Pokročilejší kouzla: reverzibilní debugger rr, profilování pomocí perfu a bpftrace.

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

Ž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. Nedávné 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.

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.

Navzdory plamenný internetovým debatám, považuji tento široký balík démonků za velmi mocný a užitečný. Začneme s initem, napíšeme pár služeb a prozkoumáme, jak je konfigurovat. Z toho pochopíme, jak psát a komponovat konfiguraci ostatních démonů, a na závěr projdeme i méně známé z nich.

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. Budeme si povídat o tom, co za data nám po síti běhá a jaké se k tomu používají protokoly – DNS, FTP, HTTP nebo třeba i mailové SMTP a IMAP. Zaměříme se více na ty nejpoužívanější (metody GET a POST v HTTP), nakousneme cacheování a nadlábneme se cookies. A pokud zbude čas, využijeme zranitelnosti některých protokolů a provedeme síťový útok.

Co se stane s e-mailem, když jej odešlete? Kudy chodí a kudy jej čerti nesou? Jaké máte záruky, že přijde; proč občas přijde pozdě nebo vůbec. Problém formátů a kódování, chyby webových i jiných klientů. Protokoly SMTP, POP, IMAP a co se stane, když do nich přimícháme SSL/TLS. E-mailová bezpečnost, SPAM a (nefunkční?) obrana pomocí SPF, DKIM a DMARC. Nakonec se podíváme na ne zrovna triviální grafový problém, který je v emailech skrytý.

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

O eliptických křivkách se v asymetrické kryptografii velice často mluví. Říká se o nich, že jsou bezpečnější než RSA, ale nejsou bezpečné vůči útokům kvantových počítačů. Proč tomu tak je? Jak takové šifrování funguje? Co vlastně jsou ty eliptické křivky? Všechny tyhle otázky se pokusí zodpovědět tato přednáška. Před přednáškou se hodí vědět základy kryptografie a RSA.

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.

Zahrajeme si na tlumočníky mezi stroji a lidmi. Ukážeme si ružné reprezentace lidského jazyka ve světě jedniček nul a ukážeme si základní algoritmy, co s nimi pracují.

Jak na počítači text nejen napsat, ale také vysázet tak, aby pěkně vypadal a aby (což je důležitější) se i příjemně četl. Jak se sází pohádka, jak báseň a jak vzorové řešení KSP plné komplikovaných vzorců. Jak jde dohromady staleté umění typografické a moderní technika. Přineste knihy i letáky, zkritizujeme sazeče, co se do nich vejde.

Pokročilejší přednáška o TeXu pro ty, kdo ho už nějaký čas používají. Budeme v TeXu programovat, kreslit obrázky, otáčet text, používat různé podivné fonty a třeba si i vysázíme odstavec ve tvaru kolečka.

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.

V HW se dozvíte, jak fungují „opravdové“ počítače, zde pro změnu na čem počítají teoretici. Všechny počítače jsou si rovny, jen některé jsou si rovnější. Turingův stroj obyčejný, vícepáskový, nedeterministický a univerzální. Random Access Machine (RAM) a Pointer Machine. Trocha minimalismu aneb stroj s počítadly. Až nám začne být smutno, pořídíme si klidně N² procesorů a spřáhneme je do paralelního počítače (PRAM). Rychlé paralelní slévání a třídění. Pokud zbude čas, ukážeme si buněčné a grafové automaty, nebo třeba dlaždičky v koupelně.

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.

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

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.

Pořídíme si ty nejkrotčejší funkce a potom z nich naprogramujeme vše. Jak výrazy s funkcemi zjednodušovat? A jak vybudovat z funkcí pravdivostní hodnoty a čísla? Funkce která vrací pevný bod funkce. A nakonec trocha Haskellu.

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.

Povídání o grafech, které jde nakreslit na papír bez křížení hran. Co všechno pro takové grafy platí a jak je poznáme, aniž bychom je museli kreslit. Existuje pouze 5 pravidelných mnohostěnů, a my se o tom pomocí teorie grafů přesvědčíme. Barvení rovinného grafu šesti a možná i méně barvami. Když zbyde čas, zkusíme grafy kreslit i na jiné plochy: kupříkladu Möbiovu pásku, pneumatiku nebo ušatou kouli.

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

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.

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

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

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

Pojďme usednout k šálku lahodného čaje a povídat si o tom, co se v něm skrývá. Kde se čaj vzal, kde se pěstuje, jak se zpracovává a jak ho připravovat. Trocha čajového zeměpisu, dějepisu i čajové chemie a čajové kultury. Též o všelijakých substancích čaji podobných.

Žijeme v době, kdy můžeme být svědkem velkých změn, a to dokonce i ve vnímání duchovna a životních hodnot. Řekneme si o historickém vývoji náboženského směru "new age" a jeho aktuální podobě. Cílem přednášky je pochopit vývoj hodnotových systémů a jak ovlivňuje jednotlivce. Přednáška z velké části vychází z pozorování Karla Gustava Junga.

Jednou ročně se sejde pár stovek šílenců, aby běhali po lese, snažili se neztratit, a během toho všeho řešili problém obchodního cestujícího dotažený do extrému. Tak nějak vypadá SMIK. Představíme si jeho princip, prohlédneme mapy z proběhlých závodů a zkusíme na nich najít nejlepší cestu.

Obecná teorie programovacích jazyků má asi tolik půvabu, jako biologická systematika. Tak se raději pojďme podívat do zoo: poznejme jazyky klasické, experimentální i dočista absurdní. Ada, Céčko a Python (tři pohledy na fungování typů). Pradědeček všech funkcionálních jazyků LISP (program a data jsou totéž). APL (algebraické inspirace, nebo též průvan ve skladišti písmenek). Forth (zásobníkový předchůdce Postscriptu, ale i javovského virtuálního stroje). Lingua::Romana::Perligata (programovací jazyk, který skloňuje a časuje). Shakespeare, Intercal, Oook! a jiné komedie. Samorozšiřitelné a hybridní jazyky.