Jarní soustředění KSP 2010
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 Python, který je jednoduchý na naučení, ale přitom není jen dětskou hračkou a je používaný ve spoustě důležitých projektů. Ukážeme si základní datové typy (n-tice, seznamy, slovníky) a datové struktury (fronta, zásobník) a základní algoritmy a programátorské techniky, bez kterých se žádný programátor neobejde.
Jak má správně vypadat řešení KSP? Na co si dát pozor, co je úplně špatně a za co organizátoři strhávají body a sobě vlasy. Přednáška, která by mohla pomoci i mnohým déle aktivním řešitelům.
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
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.
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.
Co je kombinatorika a čím se zabývá. Kolika způsoby lze uspořádat prvky? Kolika způsoby lze vybrat několik prvků z množiny? Je více podmnožin liché, nebo sudé velikosti? Tyto a další otázky si zkusíme společně odpovědět a možná objevíme další nečekané souvislosti.
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.
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.
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)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í a naprogramujeme si jednoduché kreslítko Mandelbrotovy množiny.
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.
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.
Lineární algebra vznikla jako formalizace geometrie a tuto souvislost si ukážeme. Popíšeme vektorové prostory, které se skládají z vektorů. Jaké operace s nimi umíme provádět a co všechno musí splňovat? Kdy jsou vektory závislé a kdy nezávislé? Co je to lineární kombinace, obal a generátor? Co je to dimenze vektorového prostoru a jaké má souvislosti s předchozími pojmy?
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.
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.
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í.
Datové typy jazyka C, programové konstrukce, základy práce s ukazateli. Seznámení se standardními knihovnami jazyka C.
C#
("Co se stane, když strčíme Céčko za mříže?")
[CIS]
C# je moderní objektově orientovaný jazyk, který za deset let svého bouřlivého vývoje
dostal do vínku některé funkcionální rysy. Mimo popisu základních konstrukcí si projdeme zajímavé
části dotnetí Base Class Library.
Úvod do servírování informací skrze World Wide Web. Co znamená
http://, jaký je rozdíl mezi HTML a XHTML a na co se hodí
znát kaskádové styly.
Ú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.
Předpoklady: WWWZáklady jazyka Perl pro lidi, kteří už mají solidní programátorský základ. Perl je mocný jazyk, který dává programátorům možnost výběru, jakým stylem budou psát. Každý si tedy přijde na své, ale zároveň to znemožňuje rozumnou spolupráci na velkých projektech. Mnoho problémů se v Perlu dá velice elegantně vyřešit na několik málo řádek. Striktní zákaz vstupu pro letošní účastníky základního kurzu programování.
Předpoklady: netriviální zkušenosti s programováním v jiných jazycíchProč 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.
fac n = product [1..n]")
[HASK]
Funkce v obvyklých (imperativních) programovacích jazycích nejsou funkce v matematickém slova smyslu: mají „vedlejší efekty“, projevují se na běhu programu i jinak, než svou návratovou hodnotou. Ve funkcionálních jazycích, mezi něž Haskell patří, mají takové chování zakázano. K čemu to?
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á.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 několik nástrojů, jak si pomoci z nejhoršího. Mezi nimi
třeba gdb, řádkový debuger (odvšivovač), nebo valgrind. Kdy je použít a kdy se více hodí
printf. Proč assert je tak užitečná věc.
Jak vyvíjet program delší dobu a nezbláznit se u toho. Něco o tom, jak verze radši nespravovat, a pak dál přes správu ruční pomocí diff a patch, přes CVSku a Subversion až k Archu, Gitu a Mercurialu. Něco o tom, jak udržovat patche proti vyvíjejícímu se mainlinu, a.k.a. quilt. Návod, jak si pořídit zálohu na jiném kontinentě, bude jako perlička na závěr.
Napsal jsem zdroják, co teď s ním? Počítač mu nerozumí a překládat to podle slovníku je otrava.
Aneb kdo je to kompiler, jeho kamarád linker, kde se vezmou (nebo kam se dají) knihovny.
Otrokář zvaný make a jemu podobní, k čemu je dobré nechat si ten celý blázinec zautomatizovat a jak
to udělat, aby nebyl ještě větší.
Při používání počítače se vám občas stane, že program spadne. Když nechcete jen neužitečně čekat, můžete to nahlásit autorům, kteří možná o chybě ještě neví. Nicméně napsat kvalitní chybové hlášení bývá umění, a to bude obsahem přednášky. Projdeme si možnosti od obyčejného napsání hlášení přes hledání chyby až po její opravu a odeslání patche.
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í. Probereme základy TeXu, jeho využití při psaní řešení KSP, ale třeba také povídek, ročenky, slajdů pro prezentaci, zpěvníku nebo rovnou not.
Začneme Nimem a pak se podíváme, jak se dá co nejlépe hlasovat, soudit, pořádat reklamní kampaně či usilovat o zakázky. V druhé části se zameříme na vězňovo dilema a vyzkoušíme, kdo z vás by si užil kořisti a kdo zčernal v base.
Přednáška pro ty, kteří by si jednou chtěli zasoutěžit v týmových (a dalších) soutěžích, ale netuší, jak začít. Online soutěže a judge, minimum Céčka, Unixu a Vimu. Jak programovat v týmu a jak rychle odhadnout, který algoritmus nasadit a o co se nestarat. Určeno i pro úplné začátečníky, finalisté IOI by se mohli nudit.
Copyrighty, patenty, trademarky a podobný obtížný hmyz. V čem se liší a jak se vyhnout pobodání. K čemu jsou licence, oblíbené licence free softwaru a co dovolují. Jak škodí patenty, jak se jim vyhnout a kdy je lepší nevědět. Zbraně hromadného ničení v rukou velkých firem a co je patentový troll. Jak fungují trademarky a kdy se jim lze smát. Hudba, filmy, autorské svazy, poplatky, ACTA a co s tím má společného George Orwell.
Předpoklady: Silný žaludekNezá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.