KSP

Cílem této přednášky je naučit základní přemýšlení o algoritmech a jejich rychlosti a představit základní nejužitečnější datové struktury a kdy kterou z nich použít. Užitečným základem je pole, které se ale nehodí na všechno. Na dynamičtější věci jsou šikovnější spojové seznamy, ze kterých lze vytvořit například fronty nebo zásobníky. Pokud potřebujeme rychle hledat minima nebo maxima, mohou se nám hodit haldy a pro vyhledávání zase vyhledávací stromy. Pokud tyto struktury neznáš, je tato přednáška to vhodné místo, kde se je naučit. V opačném případě spíše doporučíme nějakou pokročilejší.

Jedním z nejmocnějších algoritmických nástrojů jsou rekruzivní funkce – tedy takové, které volají samy sebe. Ukážeme, k čemu může být rekurze užitečná a jak se v ní neztratit. A kdy je naopak lepší se rekurzi vyhýbat.

Často se stane, že máme velký objem textu (knihu, všechny dokumenty na našem disku, celý internet), ve kterém opakovaně hledáme krátké řetězce (slova či sousloví). Pak se vyplatí předpočítat si pro text pomocnou datovou strukturu, která nám hledání urychlí. V našem případě touto strukturou bude sufixové pole, které nám umožní vyhledávat v čase logaritmickém k délce prohledávaného textu. Ukážeme si i další vyhledávací algoritmy, které se vyplatí třeba pokud naopak hledáme hodně dlouhá „slova“. To se hodí na trochu překvapivých místech – například se pomocí hledání v textu dají řešit některé úlohy o stromech.

Jak se na počítači řeší geometrické úlohy. Začneme jednoduchými otázkami, jako jsou průsečíky přímek nebo poloha bodu vůči polorovině. Ukážeme algoritmus na konvexní obal a výpočet obsahu mnohoúhelníka. Pomocí matic popíšeme transformace souřadnic. A pak si vezmeme koště a budeme zametat rovinu.

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.

Jak vypadá víceprocesorové či vícejádrové PCčko a co to znamená pro programátora. Procesy, vlákna a úskalí komunikace mezi nimi. Jak se snese n kohoutů na jednom smetišti? Synchronizační primitiva: mutexy, semafory, podmínkové proměnné. Spinlocky, deadlocky a livelocky. Jde to i bez synchronizace: atomické operace, transakční paměť. Které jazyky nám pomáhají a které spíš škodí. Kdy je lepší vlákna použít, a kdy ne.

Často potřebujeme načíst nějaký složitý textový vstup: matematický výraz, webovou stránku v HTML, zdroják programu, .... Ukážeme si, jak texty analyzovat (neboli parsovat), aniž bychom v nich zabloudili: rozdělení na lexikální a syntaktickou vrstvu, železničářský algoritmus na parsování výrazů, popis syntaxe pomocí regulárních výrazů a gramatik. Cestou zjistíme, že uživatelé jsou ještě větší potvory, než jsme si mysleli.

Jak funguje Internet a počítačové sítě vůbec. Lokální sítě s dráty i bez nich a různé způsoby, jak je mezi sebou propojovat. Protokoly rodiny TCP/IP a nad nimi postavené aplikační protokoly: DNS, SMTP, HTTP a celý zvěřinec dalších. Bezpečnost sítí a všelijaké útoky na ni. Pár taktů hudby budoucnosti: IPv6, multicasting, přenos v reálném čase atd.

Ukážeme si proč programy fungují tak, jak jsme zvyklí. Co umí procesor, co dělá paměť a jak se to dá k něčemu použít. Ukážeme si nějaký program v Céčku a v Asembleru a koukneme se, kolik toho řeší Python za nás. Co dělá operační systém, jak je třeba možné, že na jednom procesoru běží najednou několik procesů. Ukážeme si, že počítače jsou překvapivě hloupá stvoření, co umí jenom základní počty, ale na programování nám to stačí.

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. Podle možností rozešleme zájemcům před soustředěním mikrokontroléry, na kterých si můžou sami něco zkoušet a/nebo bude možnost si vyzkoušet svůj program vzdáleně.

Jsme v pozici dodavatele softwaru. Přijde za námi ředitel řetězce supermarketů s požadavkem, že systém na pokladnách není dostatečně efektivní a že by ho chtěl zrychlit. Co budeme dělat? Můžeme si systém proklikat a hledat problémy s uživatelským interfacem. Můžeme začít spouštět systém pod profilerem a hledat výkonnostní problémy. Nebo můžeme dojít na opravdovou prodejnu, dívat se nějakou dobu odbavování zákazníků a promluvit si s různými lidmi. Jako řešení pak koupit pokladním rukavice, protože se zmrzlými prsty dělají na dotykových obrazovkách spoustu chyb. Design Thinking je metodologie na obecné řešení kreativních problémů vytvořená na Stanfordu, aktivně používaná například v Googlu. Na tomto workshopu si ji ukážeme a dokonce i prakticky vyzkoušíme. Zapnutá kamera nutností.

V seriálu o shaderech jsme kreslili pevné objekty. Jak ale nakreslit něco, co nemá žádný povrch? Krok po kroku projdeme, jak se něco takového programuje. A vy si to do předem připravené kostry naprogramujete taky. Ideálně byste měli znát shadery na úrovni cca 4. dílu letošního seriálu. Pokud jste seriál neřešili, ale znáte nějakou analytickou geometrii (k čemu je skalární součin?) a libovolný céčkovský jazyk, také byste se měli chytat.

Ať už vás po dni plném programování trochu bolí ruce, nebo je zrovna máte obě v sádře, nemusíte hned házet flintu do žita. Ukážeme si, jak ovládat počítač pomocí hlasu, pohledu, mlaskání a dalších netradičních vstupních metod. Povíme si, jak bez rukou brouzdat na internetu, třídit maily, programovat nebo dokonce hrát hry. Nahlédneme, že hláskovat program po znacích není zdaleka ten nejefektivnější způsob, a že s trochou cviku a lenosti můžeme občas dokonce být rychlejší bez klávesnice než s ní. To všechno doprovázené ukázkami programu Talon, který nejen, že umí všechno tohle, ale ještě navíc si v něm člověk může doprogramovat v podstatě cokoliv dalšího. Na závěr si povíme něco málo o tom, jak Talon funguje vevnitř a ukážeme si, že dosáhnout lepší přesnosti než Google není zase až tak těžké, když tušíme, co můžeme od uživatele čekat.

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, práce s regulárními výrazy, makra, kouzla. Vimovité ovládání jiných programů, třeba webového prohlížeče.

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? Ukážeme si, jak si pomocí Jekyllu vytvořit, spravovat a v neposlední řadě také publikovat webovou stránku.