Jarní soustředění KSP 2008
Seznam přednášek
Tento spisek jest nabídkou přednášek, které byste na soustředění mohli slyšet, čili jakási obdoba matfyzácké Karolínky (ta je ale, pravda, ještě stále o něco tlustší). Přednášek je daleko víc, než kolik se dá za pár dní stihnout, a tak je na vás, abyste si vybrali, o které máte opravdu zájem; pokud byste rádi slyšeli ještě o něčem dalším, klidně to k přednáškám připište, třeba se najde někdo, kdo by vám o tom rád pověděl. Berte a vychutnávejte!
Údaje o jedné přednášce vypadají asi takto:
Úvod do moderní teorie vlkodlaků, čili též praktická dæmonologie a naiadologie.
Předpoklady: Měsíc v úplňku.Dozvíte se (čteno v obvyklém pořadí): jméno přednášky, v uvozovkách motto přednášky, kód (pro snadnější odkazování na konkrétní předměty), jméno přednášejícího a nakonec stručný obsah přednášky.
Povinně dobrovolné přednášky
Úvodní několikadílná přednáška pro ty, kteří mají s programováním malé nebo dokonce žádné zkušenosti. Od základů si vysvětlíme problematiku programování a představíme programovací jazyk Pascal, který byl navržen speciálně pro výuku programování. Od jednoduchých problémů se postupně přesuneme k složitějším úlohám, ukážeme si základní datové typy (pole, záznamy) a datové struktury (fronta, zásobník) a základní algoritmy a programátorské techniky, jako je rekurze, backtrack (řešení hrubou silou) a další. Vše bude doprovázeno příklady.
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. Union-find problem, hledání minimální kostry, topologické třídění grafů a kreslení grafů jedním tahem.
Jak si ukládat data natolik šikovně, abychom je nejen neztratili, ale také našli dříve, než si pro nás přijde Smrť. Klasické struktury jako pole, seznamy, vyhledávací stromy (vyvážené, AVL, a-b, splay), haldy (binární a obecně regulární) a v neposlední řadě hashování.
Problém, algoritmus a program. Časová a paměťová složitost problémů i algoritmů. Složitost rekurzivních algoritmů, složitost v průměrném případě.
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.
Základní výbavou každého informatika jsou různé standardní algoritmy, zde si ukážeme ty nejdůležitější z nich: Třídící algoritmy včetně vnějšího třídění. Vyhledávání v polích, hledaní mediánu, resp. k-tého největšího prvku v lineárním čase. Vyhodnocování výrazů, předzpracování vstupních dat.
Volitelné přednášky
Datové typy jazyka C, programové konstrukce, základy práce s ukazateli. Seznámení se standardními knihovnami jazyka C.
Objektově orientované programování přináší jiný náhled na návrh řešení problémů. Vysvětlíme, jak se liší objektové a procedurální programování. Co je to objekt a co třída. Základní vlastnosti objektů (dědičnost, zabalení, polymorfismus). Co je to metoda, překrývání metod, virtuální metody (pozdní vazba) a čistě virtuální (abstraktní) metody. Syntaxe deklarací tříd v C++ a Delphách, viditelnost a přístupová práva ke členům tříd.
Předpoklady: Znalosti procedurálního programování v Pascalu a/nebo v C.Povídání o tom, jak překladače fungují uvnitř – jak se program parsuje, jak se optimalizuje kód atd. Co je to front end, back end, „middle-end“, mezikód a jiná arkána umění kompilátorového. Jak psát programy tak, aby kompilátoru chutnaly, co optimalizovat ručně a co naopak udělá kompilátor lépe než my.
Předpoklady: Základní povědomí o tom, co to je procesor a co dělá.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 packety a jejich routing až k jednotlivým síťovým službám. Protokoly rodiny TCP/IP, síťové topologie (a proč Internet vlastně nemá žádnou), internetworking. Pár taktů hudby budoucnosti: IPv6, multicasting, přenos v reálném čase atd.
Jak vypadá architektura dnešních operačních systémů aneb co musí programátor vědět, aby mu nepadala Wokýnka/Tučňáci. Správa procesů a vláken, plánování, synchronizace. Paměť, adresace a její přidělování. Správa souborů, filesystémy. Čemu se říká jádro a proč se spojuje s pudlem.
Kamarád u černobílého textového okna září blahem. Chcete poznat, proč? Jak UNIX vznikl, k čemu je dobrý a k čemu třeba není. UNIXová filosofie. Kouzlo scriptů. Kouzlo speciálních souborů. Kouzlo propojování programů. Kouzlo nechtěného. UNIX byl napsán v C a C vzniklo pod UNIXem.
Historie a vývoj počítačových technologií a současných architektur. Co je to procesor, jak se programuje (instrukční sady) a jak se chová. Přehled tříd procesorů (skalární a vektorové, RISC). Jak procesor komunikuje s okolím (čipová sada). Nezbytné periferie: vnitřní a vnější paměti, vstupní a výstupní zařízení.
Proč psát dlouhé a složité programy, když stačí dostatečně přesně popsat situaci a pak se prostě zeptat? Toť princip logického programování, který si ukážeme na Prologu.
Kryptologie čili tajuplná nauka o šifrách, jejich konstrukci a hlavně o jejich luštění. Přísně tajné. Šifrovací systémy jako lego: základními kostičkami nám budou symetrické a asymetrické šifry a jednosměrné funkce, stavět z nich budeme kryptografické protokoly na bezpečný přenos, autentikaci, digitální podpisy a třeba i jak si hodit korunou po telefonu. Předvedeme nerozluštitelnou šifru a dokonce to o ní i dokážeme.
Rozličné kombinatorické hry se zápalkami, kamínky, barvičkami či grafy. U některých si ukážeme výherní či obranné strategie, u některých dokážeme, že sice příslušná strategie existuje, ale nikdo ji ve skutečnosti nezná. Zmíníme například: piškvorky, kruhové a zobecněné piškvorky, hex, různé varianty Nimu, vojáčci v poušti, speciality à la Herkules a Hydra, a další. Můžeme se zapovídat i o tom, jak podobné hry programovat na počítači.
Kreslení a zpracování obrazu na počítači. Souřadnice (rovinné, prostorové i barevné) a jejich transformace. Základní grafická primitiva: body, úsečky, kružnice, elipsy, Bézierovy křivky a jejich rasterizace. Vyplňování n-úhelníků a křivkou ohraničených oblastí, flood fill. Pár triků navíc: maticové filtry, anti-aliasing a dithering. Grafické formáty a komprese obrázků. Základy trojrozměrného promítání a vykreslování scény.
K čemu jsou při programování dobrá náhodná čísla a jak je generovat. Algoritmy pravděpodobnostní a randomizované, časová složitost v průměrném případě. Proč používat a proč nepoužívat Quicksort. Inkrementální algoritmy (třeba na konvexní obal), vyhledávání v poli v konstantním čase za pomoci hashování, konstrukce perfektního hashování, randomizované datové struktury (skip listy a treapy). Interaktivní protokoly aneb jak vyhrát nad falešným hráčem. Problém studny na Pražském hradě. Míchání karet.
K čemu je dobré, když grafem teče voda. Předvedeme si klasický problém toků v sítích a jeho všelijaké, mnohdy dosti překvapivé aplikace. Jak rozestavět n věží na šachovnici a jak ji místo toho pokrýt dominovými kostkami? Další souvislosti, jako třeba násobná souvislost grafů.
Předpoklady: Umět plavat (zejména v matematice)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. Ale co s tím? Přírodní vědy si vymyslely verifikovatelné experimenty a matematici logiku a dokazování. Co je to výrok, co jeho důkaz a proč se axiomy nedokazují. Jenže jak si je zvolit? A jak se z toho všeho postaví celá matematika? A bude vůbec matematika někdy celá? Studená sprcha pana Gödela coby sebevražedné dovršení snahy získat dokonalý jazyk. Logika coby hra a problém líného profesora. Důkazy boží existence a neexistence.
Předpoklady: LOGIÚvodní minikurs diskrétní matematiky (to je opak matematiky spojité, čili mimo jiné kombinatorika). Seznámení s relacemi a jejich vlastnostmi. Dozvíte se také něco o uspořádaných, nezávislých a jiných množinách, setkáme se i s Dlouhým a Širokým. S pomocí kombinatoriky možná vyřešíme problém zmatené šatnářky.
Nezávazné povídání o Matfyzu a základním matfyzáckém folklóru. Určitě si přečteme matfyzáky sepsaný Úvod do matfyzáka a zazpíváme pár matfyzáckých písní. Zbytek už bude záležet na tom, co budete chtít slyšet.
Shrnutí hradlového seriálu KSP. Tedy krátký úvod do historie, nástin vnitřností, schémata, schematické značky, konvence. Trocha teorie, Booleova algebra a De Morganovy zákony. V neposlední řadě si ukážeme, jak rychle a efektivně umíme problémy hradly řešit.
Úvod do problematiky vytváření dynamicky generovaných webových stránek. Syntaxe jazyka PHP, netypovost, (ne)pole. Základní postupy pro boj s uživatelem (a proti němu). Zamícháno s XHTML, JavaScriptem, CSS a možná i (My)SQL.
Trochu hlouběji o složitosti: amortizovaná časová složitost, dolní odhady, nedeterministické výpočty a třída NP, NP-úplné problémy a příklady redukcí.
Předpoklady: SLOZDůmyslnější datové struktury: trie, intervalové stromy, splay stromy, BB-α stromy; geometrické struktury pro lokalizaci bodů v rovině; binomiální a Fibonacciho haldy, leftist haldy a 2-3 haldy. Též několik přátelských randomizovaných datových struktur: skip listy a treapy.
print "Ffff".decode("rot13")")
[Pyth]
Základy programování v Hroznýši (Pythonu), syntaxe, datové (ne)typy, funkce, třídy, moduly aneb všechno je slovník nebo prvek slovníku (nebo oboje). Výhody interaktivního interpretu.
Zobecníme pojem vzdálenosti a získáme nové geometrické světy. Jak se cestuje v New Yorku a jak přes Paříž. Jak se otvírají a zavírají množiny. Naučíme se srolovat kus roviny a narovnat povrch koule (za cenu jednoho bodu). Můžeme též lehce nahlédnout do topologie, kde není rozdílu mezi hrnkem a kakaovým věnečkem.
Nekonečně složité obrázky, které jdou ale často matematicky popsat velmi jednoduše. Necháme počítač nakreslit fraktální kapradí, vločku a mořského koníka. Na programu jsou také fraktály v komplexní rovině a v Pascalově trojúhelníku. Ukážeme si, jak vlastně fraktály vznikají.
Povídání o grafech, které jde nakreslit na papír bez křížení hran. O tom, 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ž zbude čas, zkusíme grafy kreslit i na jiné plochy: kupříkladu Möbiovu pásku, pneumatiku nebo ušatou kouli.