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.

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.

Někdy potřebujeme najít podřetězec ve velkém množství textu. Základní řetězcové algoritmy a datové struktury (např. trie). Indexování: jak si pro velké množství textu předpočítat datovou strukturu (v našem případě sufixové pole), která umožní vyhledávat v něm rychleji než v lineárním čase? Další témata dle zájmu časových možností, např. regexy a vyhledávací automaty.

Přehled základních kompresních algoritmů: triviální algoritmy (RLE), statistické metody (Huffmanovo a aritmetické kódování), slovníková komprese (LZ77, LZ78, LZW), Burrowsova-Wheelerova transformace (BZIP). Pokud zbude čas, tak i něco o ztrátové kompresi obrázků a zvuku (prediktory, wavelets, JPEG, MPEG, fraktály).

Pojďme spolu na výlet krajinou datových struktur. Vyšlapané cestičky lesem vyhledávacích stromů mineme a raději zahneme do opravdové džungle. Potkáme struktury pracující ve skoro konstantním čase, dynamické reprezentace grafů, roztodivné druhy hešováni a cokoliv dalšího, o co si průvodci řeknete.

Na pomezí mezi lineární algebrou a teorií grafů se nachází algoritmus PageRank. Jedná se o zajímavé dílo Larryho Page, na kterém ve svých začátcích stál celý Google. Povíme si o tom, co jsou to vlastní vektory, co to má společného s Markovovskými procesy a proč občas může fungovat definice kruhem.

Jednoho dne se Larry Wall rozhodl, že nasype do jednoho velkého kotle spousty programovacích jazyků a unixových utilit, za stálého míchání povaří, posléze přecedí, přikoření a implementuje. Tak vznikl Perl, jazyk původně určený hlavně na zpracování textu, ovšem jak se ukázalo, též šikovný na spoustu dalších věcí. Asociativní pole, libovolně složité datové struktury za pomoci referencí, balíčky a objekty zdarma a hlavně regulární výrazy zde a všude. Zkrátka jazyk, který lze jedině milovat nebo nenávidět, nic mezi tím. Co se Perl 5 přiučil od Perlu 6.

Povídání o méně zmiňovaných částech Pythonu. Dekorátory, metaclasses, generátory, funkcionální styl programování v Pythonu. Jak napsat quicksort jako lambda funkci. Představení zajímavých modulů nejen ze standardní knihovny. Další témata dle přání účastníků: paralelní programování (asyncio, multiprocessing), síťová komunikace, GUI, matematické výpočty, propojení Pythonu s C, ...

Jak nečekat až se něco stane, ale místo toho reagovat až když se to opravdu stane. Jak pracovat s událostmi, jak programovat událostmi řízené systémy. Ukážeme si jaké problémy za nás řeší Promises a vrátíme se od řešení událostí k normálnímu programování. Jak se nezbláznit z toho, že se děje několik věcí současně.

Podívejme se, na jakých počítačích programují čistokrevní 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ě.

První Gödelova věta o neúplnosti je jedním z nejznámějších a nejpodivnějších tvrzení v historii matematiky. Říká, že v každé rozumné matematické teorii existují tvrzení, která jsou pravdivá, ale nelze je dokázat. Ukážeme si, že Gödelovy věty poměrně úzce souvisí s informatikou a ve světle informatiky si místo „Jak takováhle divná věc může platit?“, budete říkat „No to je naprosto jasné, že to musí platit, a nikdy by to nemohlo být jinak.“ Podíváme se i na další zajímavé partie teorie vyčíslitelnosti, třeba věty o rekurzi a Riceovu větu.

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.

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.

Čtení cizího kódu se na přednášce spíš nenaučíte, tak se na to zkusme podívat více prakticky. Projdeme si nějaké kousky kódu a zkusíme se v nich vyznat, zjistit co dělají a co by třeba dalo opravit/zlepšit.

Ako sú dáta uložené na disku? Rozdelenie disku na partície pomocou MBR a GPT schémy. Ako funguje FAT (12, 16, 32) a jej rozšírenia VFAT, TFAT. Krok dozadu v podobe exFAT. Linuxové filesystémy EXT2 až EXT4. Multiplatformový UDF nielen na optické disky. Čo použiť na SSD? A ak ostane čas, tak niečo o UBIFS používaný na flash pamätiach bez radiču.

Vysypeme z rukávu, jak se dá vyrobit procesor, a půjdeme ho zrychlit. Proč nejde jednoduše zvýšit frekvenci, a jak to teda udělat. Jak ušetřit čas při přístupu do paměti, na co je ta slavná predikce skoků a jak se dá spouštět víc instrukcí najednou a si přeházet program podle toho jak se to zrovna procesoru hodí.

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

Internetoví provideri nám pomaly začínajú ponúkať pripojenie do sveta IPv6 Internetu. Čo to IPv6 je? Čím sa líši od svojho staršieho kolegu IPv4? Prečo by sa o neho mal zaujímať aj obyčajný užívateľ? Pozrieme sa aké problémy IPv6 rieši, aké má výhody oproti IPv4 ako aj na súčasný stav podpory IPv6 v operačných systémoch. A hlavne s akými problémami sa človek bežne stretne než si bude môcť doma spraviť IPv6 sieť.

Dosť často sa programy nepíšu iba na jedno spustenie, ale sa používajú dlhé roky. Veľa z nich naviac bude používať úplne niekto iný. Na tejto prednáške sa pozrieme na časté chyby v programoch a ako im predchádzať. Ako klasifikovať či chyba je závažná a bezpečnostná. Ďalej si povieme, čo robiť v prípade, ak nájdeme nejakú (možno bezpečnostnú?) chybu. Komu ju oznámiť a komu radšej nie.

Organizátoři KSPčka rádi dělají pokusy na sobě samých, a tak při vývoji nového webu semináře pohrdli všemi vyzkoušenými webovými frameworky a napsali si potvůrku jménem Hippo. Trochu netradiční, ale v mnoha ohledech velice příjemnou. Namátkově: HTML coby datová struktura, triky s kryptografickými tokeny, kombinování programovacích jazyků a tvorba dynamickych stránek, které jsou přitom skvěle kešovatelné. Případně také nahlédnutí do dalšího zákulisí KSPčka.

Chtěl sis někdy vytvořit vlastní webovou stránku, ale ručně psát HTML a CSS tě otravuje? Zajímalo by tě, jak z Markdownu generovat pěkně vypadající, databázemi a jinou havětí nezatížené webové stránky? Nerozumíš názvům zbylých přednášek v tomhle slotu? Pokud jsou tvé odpovědi na některé z těchto otázek ano, pak je tato přednáška právě pro tebe! Ukážeme si, jak si pomocí Jekyllu vytvořit, spravovat a v neposlední řadě také publikovat webovou stránku.

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

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.

V čem programovat STM32, pokud vás neláká Arduino ekosystém, ale nechcete si to celé psát sami. Budeme se držet jazyka C, ukážeme si oficiální HAL knihovnu včetně toho, jak si většinu periferií naklikat a komunitní knihovnu libopencm3, která je stručnější a podporuje více mikrokontrolérových rodin.

Rychlokurz teorie čísel pro začátečníky. Číselné obory. Dělitelnost a prvočísla. Modulární aritmetika (aneb počítání jako na hodinách, kde 10 + 9 + 8 = 3). Kongruenční rovnice. Malá Fermatova věta.

Věty o rozložení prvočísel jsou tradičně považovány za jednu z nejmysterióznějších oblastí teorie čísel. Zde ukážeme, jak některé z nich odvodit snadným pozorováním vlastností kombinačních čísel: rozbor časové složitosti Eratosthenova síta, Bertrandův postulát („Mezi n a 2n je aspoň jedno prvočíslo.“), hustota prvočísel.

Teorie grafů trochu teoretičtěji. Různé druhy grafů a jejich vlastnosti. Stromy a lesy. Kreslení grafů jedním tahem. Princip sudosti a skóre grafu. Jaké speciální vlastnosti mají rovinné grafy a jak je lze obarvit šesti nebo možná i pěti barvami. Jak poznat, že dva grafy (ne)jsou isomorfní. Mosty, artikulace a ušaté lemma. Párování, střídavé cesty a Hallova věta.

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.

O podstatě světla a barevného vidění a různých pokusech o reprezentaci barev v počítačích, fotoaparátech, televizích a podobných zařízeních. Systémy RGB, CMY(K), HSV, XYZ, Lab s jejich výhodami i neduhy. „Systém“ Pantone. Reálné kontra imaginární barvy aneb proč nejde vyfotit duha.

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.

Donald E. Knuth napsal TeX před desítkami let proto, že mu nikdo nebyl schopen vysázet matematický text podle jeho požadavků. Od té doby se hojně používá pro sazbu nejrůznějších publikací. V této spíše praktické přednášce si ukážeme použití TeXu od hladké sazby knihy až po zběsilosti hraničící s programováním. Pozornost věnujeme i zdrojům informací a rozdílům mezi různými dialekty TeXu.

Oddychová interaktivní přednáška o historii a vzniku metalu a jeho subžánrů. Slavné i neslavné příběhy různých interpretů. V případě zájmu můžeme dát několik důležitých rad jak přežít metalový festival. Dozvíte například se co je to blastbeat nebo breakdown. Budeme si dělat srandu z metalových stereotypů. Bude i živá ukázka obskurdních hudebních nástrojů a možnost si je vyzkoušet. Ale hlavní otázka zůstává stejná... BUT DOES IT DJENT ?!

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.

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.

Evoluční teorie je asi jedním z největších převratů v lidském náhledu na svět. Jak se na takovou věc vůbec přišlo, proč to tak dlouho trvalo a proč si myslíme, že je to pravda? Jak si to vše alespoň trochu představit? Mnoho nečekaných překvapení, informatické a fyzikální souvislosti. Proč jsou stromy vysoké, jak souvisí pohlavní rozmnožování s počítačovou bezpečností, co má evoluce společného s Windows a co s halting problémem?

Altruismus znamená použití nějakého množství vlastních zdrojů (peněz, času, talentu, ...) na pomoc ostatním lidem a světu. Ale svět má mnoho problémů a k jejich řešení je možné přispět mnoha různými způsoby. Jak si vybrat? Většina lidí si vybere něco, co je jim emocionálně blízké. Ale to nemusí být úplně nejšťastnější. Ukazuje se totiž, že různé způsoby pomoci se výrazně liší efektivitou – tím, kolik reálného užitku (např. zachráněných životů) můžeme získat s daným množstvím vložených zdrojů. Často i o několik řádů. Jaké jsou nejvýznamnější problémy světa a nejefektivnější způsoby jejich řešení? Kdy je lepší finančně podpořit nějakou charitativní organizaci (a jak si vybrat kterou), dobrovolničit či přímo pracovat na řešení nějakého problému? Jak si vybrat kariéru s ohledem na pozitivní přínos světu? Efektivní altriusmus je rostoucí celosvětové hnutí, které se snaží vědeckou metodou hledat odpovědi na tyto a další otázky.

V první části projdeme způsoby aktivního i pasivního zaměřování všech možných věcí, zejména letadel a počasí. Ve druhé části ukážu, jak jsem z obyčejných USB klíčenek pro příjem televize postavil pasivní radar pro zaměřování vysílačů pracující na stejném principu jako Tamara. Funkcionalitou a citlivostí se sice nemůže skutečné Tamaře rovnat, ale opravdu funguje a dokáže zaměřit reálné rozhlasové a televizní vysílače.

Kreslíte plošňáky fixou, krabičky vyřezáváte z překližky ručně a konektory krimpujete kombinačkami? V dnešní době je spousta věcí jednodušších, jen o nich vědět. Přednáška o tom, co si kde dnes můžete relativně levně nechat udělat, co si udělat sami a jaké na to použít nástroje a nářadí.

Popis fyzické vrstvy (solid i wireless), nejpoužívanější protokoly a problematika opravy chyb. Jako vždy bude prostor si probírané technologie vyzkoušet.

Neorganizovaný prostor pro sdílení nástrojů, postupů a triků, které používáte pro šetření času a zlepšení produktivity či jiných aspektů života. Od skriptů a automatizace přes zefektivnění každodenních činností po zlepšení soustředěnosti.