Podzimní soustředění KSP 2007

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:

Stručný úvod do základů teorie vlkodlaků ("Za dne ukryt v hloubi lesa, děs temný zvečera se plazí...") [LYK]
RNDr. Á. Cula

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

Informatické přednášky – teoretické

Algoritmy a jejich složitost ("Čím menší je časová složitost algoritmu, tím větší je složitost kódu.") [SLOZ]

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

Složitější složitost [SLOZ2]

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: SLOZ
Třídy složitosti [SLOZ3]
Martin Mareš

Složitost opravdu důkladně: nejrůznější třídy složitosti a vztahy mezi nimi. Vztahy mezi časem a prostorem, odstraňování nedeterminismu a Savitchova věta. Jak víme, že všechny třídy nejsou stejné: dolní odhady a věty o hierarchii. Stroje s kvantifikátory, třída PSPACE a polynomiální hierarchie. Pravděpodobnostní třídy složitosti. Orákula a neuniformní složitost.

Předpoklady: SLOZ2
Vyčíslitelnost ("S Halting problémem na věčné časy!") [VYCIS]
Martin Mareš, Pavel Machek, Martin Kruliš

Některé problémy se dají vyřešit snadno, jiné obtížněji a některé dokonce vůbec. Obecněji: Ať si vymyslíte jakýkoliv rozumný programovací jazyk, vždycky existuje problém, který se v něm nedá vyřešit. Jak se ale dokazuje, že něco nejde? Matematický pohled na výpočetní modely a univerzální stroje, rekurzivně spočetné a rekurzivní množiny a funkce. Halting problem a diagonální důkazy.

Grafy & algoritmy I ("Pojďme si hrát s obrázky") [GA1]

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.

Grafy & algoritmy II [GA2]
Jan Bulánek, Martin Kruliš, Martin Mareš, Milan Straka, Jana Kravalová

Pokročilejší grafové algoritmy: toky v sítích, párování v grafech, testování vícenásobné souvislosti a silné souvislosti.

Matice a grafy ("Já pán, ty pán, ale kdo má graf v matici, je ještě větší pán.") [MATGR]
Milan Straka, Martin Mareš

Má smysl reprezentovat graf maticí? Co vlastně jsou matice a jak se násobí? Jak nejrychleji umíme matice násobit a jak souvisí násobení matic s hledáním sledů v grafu? Proč funguje Floyd-Warshallův algoritmus a jak ho zobecnit, aby počítal jiné věci, třeba nejspolehlivější sled? Nebo aby z konečného automatu vytvořil regulární výraz? A proč je tu tolik otázek? Nevíte?

Datové struktury pro začátečníky ("Pole oraná a neoraná, stromy ovocné a okrasné.") [DS1]

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

Datové struktury pro pokročilé ("Haldy a jiné kupky.") [DS2]

Dů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.

Datové struktury pro šílence [DS3]
Martin Mareš

Ještě důmyslnější datové struktury dle přání posluchačů. Možno servírovat například: dynamické reprezentace grafů (Sleator-Tarjanovy stromy, ET-stromy, Fredericksonovy topologické stromy), vícerozměrné datové struktury (zobecnění vyhledávacích stromů a intervalových stromů), obecné dynamizační schéma, triky pro malé integery, persistentní datové struktury et cetera.

Algoritmy (bez grafů) ("nevšední algoritmy všedního dne") [ALGZOO]
Martin Mareš

Na motivy knížky The Art of Computer Programming od pana Knutha si předvedeme několik nevšedních, zato však velmi elegantních algoritmů: hledání největších společných dělitelů bez dělení, násobení dlouhých čísel v čase O(n1.59) a možná i rychleji, residuovou aritmetiku, slévání setříděných posloupností v konstantním prostoru, pravděpodobnostní testování prvočíselnosti a jiné kejkle.

Vyhledávací a třídící algoritmy ("Dnes se zbavím bublifuku!") [SORT]

Základní třídící algoritmy, které se vyplatí znát: quicksort, mergesort, heapsort, radixsort a také něco na velké soubory – vnější třídění. Vyhledávání v polích: půlení intervalu, hledání mediánu resp. k-tého největšího prvku v lineárním čase.

Hledání v textu (">>Vyšíváme v seníku!<< – kde jsem to jen viděl?") [REGEX]
Martin Mareš, Martin Kruliš, Milan Straka

Vyhledávání čehokoliv ve velkém množství textu: Prostá vylepšení brute-force algoritmů: Karp-Rabin, Boyer-Moore. A algoritmy chytřejší: Morris-Pratt, Knuth-Morris-Pratt, Aho-McCorasicková. Konečné automaty prakticky, regulární a „regulární“ výrazy.

Stringové algoritmy ("Co se nedá spočítat v lineárním čase, nestojí za to.") [STRG]
Martin Mareš

Předvedeme všeliké algoritmy na zpracování řetězců, které mají (mimo jiné) společné to, že pracují v lineárním čase: třídění za pomoci kyblíčků, vyhledávání podřetězců v textu (Boyer-Moore, trie, Knuth-Morris-Pratt, Aho-McCorasicková), konstrukce suffixových stromů (aneb jak obrátit řetězec naruby) a jejich použití, nejdelší společné podřetězce a třeba i Burrows-Wheelerova transformace.

Komprese dat ("Jnm idln kpln j nstlčtln.") [PRESS]
Milan Straka, Martin Mareš

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), Burrows-Wheelerova transformace (BZIP). Pokud zbude čas, tak i něco o ztrátové kompresi obrázků a zvuku (prediktory, wavelets, JPEG, MPEG, fraktály).

Aproximační algoritmy ("Součet úhlů v trojúhelníku je vždycky tři ... tedy alespoň ± 5%") [APX]
Martin Mareš

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). A tak nám nezbývá než se je pokusit řešit alespoň přibližně. Horolezecké algoritmy, metoda Monte Carlo, simulované žíhání a hit loňské sezóny – genetické algoritmy. Ovšem raději bychom chtěli znát dopředu odhad chyby: aproximační algoritmy a aproximační schémata.

Pravděpodobnost a algoritmy ("Nejen že Bůh hraje v kostky, ale ještě při tom občas švindluje!") [PPALG]
Martin Mareš, Milan Straka

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.

Paralelní výpočty ("Největším nepřítelem lidstva je trojrozměrný prostor.") [PARAL]
Martin Mareš, Michal Vaner

Když nestihne problém vyřešit jeden procesor, proč jich nepoužít víc? Zkusme na chvíli zavřít oči a představit si, že máme stroj, který umí například pro sečtení N čísel zapnout N procesorů ... nebo rovnou N2, všechny se společnou pamětí a společným programem – teoretikové takovému počítači říkají PRAM. Ukážeme si rychlé paralelní algoritmy všeho druhu: aritmetiku, slévání a třídění, grafové algoritmy, vše v (poly)logaritmickém nebo dokonce konstantním čase. Po probuzení do reality všedního dne trocha praxe: SMP, NUMA, Connection Machine, clustery, koordinované screen savery, FPGA.

Kryptologie ("Gbgb arav zbp gnwan mcenin.") [CRYPT]
Martin Mareš, Milan Straka, Pavel Machek

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.

Kryptologie II ("6140 a184 c9a6 41f1 de99 e733 354a f451") [CRYPT2]
Martin Mareš, Milan Straka

Pokročilejší (dešifruj: zběsilejší) partie vědy kryptologické: utajené výpočty, zero-knowledge proofs, sdílení tajemství, podprahové informace a kvantová kryptografie. Aplikace v reálném životě: digitální peníze, volební systémy. Různé metody útoků na šifry a kryptografické protokoly. Problémy distribuce klíčů a proč se jí raději vyhnout (a jak: Diffie-Hellman key agreement, komutativní šifry). Stručný přehled souvisejících partií matematiky a teorie složitosti.

Předpoklady: Základní povědomí o šifrování (CRYPT) a víra v existenci náhodných čísel
RSA [RSA]
Milan Straka

O tom, jak šifrovací algoritmus RSA funguje, proč funguje a jestli bude ještě fungovat. A také jak se dá rozumně rychle naprogramovat.

Dune snadno a rychle [DUNE]
Honza Bulánek

Jak si napsat vlastní jednoduchou realtime strategii ve stylu starého Dune. Seznámíte se se základy diskrétní simulace a algoritmem A*, který slouží pro rychlé hledání cest.

Předpoklady: základy OOP a Dijkstrův algoritmus
Toky v sítích ("Když je v grafu povodeň, těsní?") [TOKY]
Martin Mareš

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)

Informatické přednášky – programovací jazyky a techniky

Programování v jazyce C [C]
Zbyněk Falt, Cyril Hrubiš

Datové typy jazyka C, programové konstrukce, základy práce s ukazateli. Seznámení se standardními knihovnami jazyka C.

C for wizards ("{ }1[x]+++++x[1]") [CWIZ]
Martin Mareš

Céčkové speciality aneb všechno, co jste chtěli o Céčku vědět, ale nebylo se koho zeptat. Pořadí vyhodnocování, side effecty, sequencing pointy, funkce s proměnným počtem parametrů, preprocesorové triky, celá pravda o vztahu pointerů a polí, o jménech typů a o příkazu switch; alignment, NULL, void, volatile. Všelijaké zrady (velikosti typů, (a+b)+c ≠ a+(b+c), znaménka ...). Dialekty Céčka od K&R až po (staro)nový standard C99 a různá nestandardní rozšíření jazyka. Proč jsou objekty potřebnější v mysli programátorově než v jazyce a proč je C lepší než C++ :–)

Předpoklady: Povšechná znalost jazyka C.
Objektově orientované programování nejen v C++ ("Object-oriented system. If we change it, users object.") [OBJ]
Martin Kruliš, Michal Vaner

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 Object Pascalu (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.
C++ pro pokročilé ("Kdo má dobrý vkus, píše v Cé plus plus. Ten, kdo má vkus slabší, tomu céčko stačí.") [CPP]
Martin Kruliš

Pokročilé techniky implementace algoritmů v C++. Šablony a jejich použítí, standardní knihovny STL a malý úvod do návrhových vzorů.

Předpoklady: C
Design Patterns (návrhové vzory) ("Jedináček nahazuje Fasádu nové Továrny.") [DP]
Jana Kravalová, Martin Kruliš

Pokročilé metody návrhu objektově orientovaných systémů. Seznámíte se s klasickými programátorskými postupy a osvědčenými modely, které usnadňují návrh složitějších projektů (resp. jejich dílčích částí) a také zjednodušují komunikaci mezi programátory.

Předpoklady: Základní znalosti objektově orientovaného programování.
.NET and C# [DNET]
Milan Straka

Spíš povídání o tom, co je to .NET, jak funguje, proč funguje zrovna tak, a k čemu to celé je a není vhodné a jak k tomu přispěla Java. Rozebereme používaný mezikód i důvody, proč ho (ne)používat, a vezmeme si na mušku i C# i jiné původně ne.NETové jazyky jako Boo či Phalanger.

Perl ("Jak Pejsek a Kočička vymýšleli programovací jazyk") [PERL]
Martin Mareš

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.

Python ("{ }print "Ffff".decode("rot13")") [PYTH]
Michal Vaner, Pavel Machek

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.

Logické programování ("Detektivem za 90 minut.") [LOGP]
Jana Kravalová

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.

LISP ("Lots of Irritating Superfluous Parentheses?") [LISP]
Martin Mareš

Lehký úvod do funkcionálního programování a jazyků z lispovské rodiny (Common Lisp, E-Lisp, Scheme, KSP Lisp atd.). Všechno je funkce, zbytek jsou seznamy (a konec konců funkce je také druh seznamu). Proměnné aneb příběh se nemění, jen příjmení a jména. Jak se programuje v Lispu a jak se programuje Lisp.

Předpoklady: Netrpět uncinofobií (((to jest chorobným strachem ze závorek)))
Haskell ("Pro ty, kdo uncinofobií trpí") [HASK]
Milan Straka, Martin Mareš

Základní kurz Haskellu – moderního funkcionálního jazyka. Na skladě máme skoro všechno, co měl Lisp, o zbytku ukážeme, že mít to by byla chyba; a samozřejmě spoustu věcí navíc. Základní konstrukce, typový systém, třídy a jak se obejít bez výjimek a speciálních případů, vstup a výstup.

Funkcionální programování [FUNC]
Milan Straka

Základní principy funkcionálního programování, výhody a nevýhody. Užitečné triky a techniky – monády, arrows, continuation passing, concurrence, .... Ladění a optimalizace. Ukázky budeme uvádět v Haskellu.

Dynamické programování ("Kampak jsem si to jenom schoval?") [DYNP]

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.

Jazyk XML a související technologie ("<xml style="vesele"/>") [XML]
Martin Kruliš

Povíme si, co je to jazyk XML, jak vznikl a k čemu je dobrý. Zároveň probereme nástroje pro práci s XML dokumenty, jejich načítání (parsování), generování, validaci atd. Z pokročilejších technik pak ukážeme vyhledávání v XML pomocí jazyka XPath a transformace XML dokumentů pomocí XSLT. Zbyde-li čas ukážeme si i několik konkrétních aplikací (XHTML, WML, SVG, ODF ...).

Databáze a DB systémy ("SELECT * FROM beaverknowledge WHERE code="DB" LIMIT na hoďku a půl") [DBS]
Martin Kruliš

Co je to databáze a databázový systém. ER diagramy a jejich převod na tabulky. Klíče, nadklíče, podklíče a paklíče. Normální formy, algoritmus dekompozice a algoritmus syntézy. Jazyk SQL a jeho použití na skutečných databázích. Zbude-li čas, přijde i ukázka relační algebry a doménového a n-ticového kalkulu.

Jak fungují DB systémy uvnitř ("HDD je lednička pro data – když je tam správně uložíte, vydrží déle.") [DBS2]
Martin Kruliš

Řekneme si, jak fungují současné vnější paměti (především pevné disky) a jak se s nimi pracuje. Protože jsou o hodně pomalejší než operační paměti, je potřeba navrhnout vhodnější datové struktury, které urychlí čtení z takovýchto zařízení. Povíme si o sekvenčních, index-sekvenčních a indexovaných souborech. Navrhneme vhodné způsoby ukládání indexů (B-stromy, hašování). A zbyde-li čas, povíme si i něco o vyhledání podle více klíčů.

Systémy pro správu versí [CVS]
Pavel Machek, Martin Mareš, Michal Vaner

Jak vyvíjet program delší dobu a nezbláznit se u toho. Něco o tom, jak verse 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.

Panoptikum Programátorských Projektů [PPP]

Přestože prazáklad programování poskytují převážně poznatky přírodovědců, přísluší patřičná pozornost programátorské praxi. Předvedeme proto publiku přednášejícími přímo provozované programátorské projekty.

Portabilní programování ("Šel si program na vandr...") [PORT]
Martin Mareš, Pavel Machek

Většina programátorů dřív nebo později zjistí, že počítačový svět nekončí hranicí jejich monitoru a že je mnohem rozmanitější než nekonečné zelené pláně windowsové pracovní plochy. Jenže jak se v takovém světě domluvit a jak psát programy, aby fungovaly všude? Na co se dá spolehnout a na co ne, jaké se hodí znát jazyky a jaké knihovny k nim. K čemu jsou dobré standardy a k čemu configure. Proč je někdy potřeba vynalézat kolo. Za rok se vrátím aneb jak (nechat) program udržovat.

Programování v UNIXu [PUNIX]
Zbyněk Falt, Pavel Machek, Cyril Hrubiš

Stručný přehled unixových utilit. Jak si napsat vlastní skript, přehled základních programových konstrukcí. V případě zájmu a času seznámení s programem awk.

Programování v assembleru [PASM]
Zbyněk Falt, Martin Kruliš

Seznámení s instrukčním souborem x86 procesorů. Rozdíly mezi Intel a AT&T syntaxí. Povídání o tom, jak lze spojit assembler s vyššími programovacími jazyky. Zbyde-li čas povíme si i něco o systémové architektuře IA32.

Programování v assembleru II [PASM2]
Zbyněk Falt, Martin Kruliš

Jak optimalizovat programy napsané v assembleru, a tak program ještě více urychlit. Stručné seznámení s architekturou procesorů. Ukázka konstrukcí, kterým je třeba se vyhnout a čím je nahradit. Seznámení s MMX a SSE instrukcemi.

Předpoklady: PASM
Java [JAVA]
Zbyněk Falt

Základy syntaxe, základní typy. Třídy, dědičnost, interface. Práce s objekty, s poli a s řetězci. Povídání o alokaci paměti a garbage collectoru. Zpracování výjimek. Jak na vlákna a jejich synchronizaci.

Java 2 Micro Edition [PJ2ME]
Zbyněk Falt

Rozdíly mezi klasickou Javou a Javou pro mobilní zařízení. Základní struktura programů (midletů). Jak naprogramovat vlastní user interface, kreslit a rozpohybovat obrázky, připojit se na internet a jak ukládat údaje do pevné paměti telefonu.

Předpoklady: Java
Windows API [WIN]
Zbyněk Falt, Martin Kruliš

Přednáška zaměřená převážně na programování GUI. Jak si vytvořit dialog nebo otevřít okno. Jak napsat proceduru pro zpracování zpráv. Přehled standardních ovládacích prvků.

Windows API II [WIN2]
Zbyněk Falt, Martin Kruliš

Správa procesů a vláken a synchronizace mezi nimi. Správa paměti, souborů. Vytváření knihoven DLL.

High-Performance Computing ("Jak krotit terabyty a jak trilobyty?") [HPC]
Martin Mareš

Jak vymáčknout z počítače co možná největší výkon. Kdy optimalizovat a kdy raději ne. Jak si program zparalelizovat: aritmetický paralelismus, vektorové instrukce, symetrický i nepříliš symetrický multiprocesing, počítání na clusterech počítačů. K čemu je grafická karta. Lži, zatracené lži a benchmarky a co si z nich vybrat. Jak hledat v terabytovém textu.

Informatické přednášky – hardware, operační systémy a spol.

Principy počítačů ("A opravdu uvnitř počítače běhají malý trpaslíci?") [HW]
Martin Kruliš, Pavel Machek, Cyril Hrubiš

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

Modely počítačů ("Nač Pentium? Máme Turingovy stroje!") [MODEL]
Martin Mareš

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ý, nedeterministický, univerzální a paralelní, orákula, Random Access Machine (RAM), Parallel RAM, Pointer Machine, Data Flow Machine, rekursivní funkce, Markovovy algoritmy, reverzibilní algoritmy, buněčné a grafové automaty, ale třeba i dlaždičky v koupelně.

Počítače s více procesory: jak se s nimi dohodnout ("Nač Turingovy stroje, když máme Athlona?") [SMP]
Pavel Machek, Martin Kruliš

Jak je vlastně možné, že se víc procesorů snese na jednom smetišti? Spinlocky, semafory, paměťové bariéry. K čemu je dobré dát víc vláken do jednoho procesoru a proč se dává víc procesorů na jednu destičku křemíku. Jak se nám z paměti RAM postupně stává „not-so-Random Access Memory“, co jsou cache a proč jsou dneska tak důležité.

Operační systémy ("Mám 3GHz procesor, tak co ty Windowsy už půl hodiny dělaj?!") [OS]
Martin Kruliš, Pavel Machek

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.

Filesystémy ("Opravdu je FAT tabulka tlustá?") [FS]
Pavel Machek, Martin Kruliš

Povídání o tom, jak kdo ukládá data na disk. Dozvíte se, jak funguje filesystém FAT či jeho modifikace VFAT, jak ukládá data Linux na filesystémy EXT2, EXT3 či dosti netradiční ReiserFS. Pokud zbude čas, povíme si i něco o NTFS a filesystémech pro netradiční nasazení (konkrétně žurnálovací a distribuované FS).

Předpoklady: Hrubé povědomí o tom, jak fungují pevné disky.
UNIX ("UNIX gives you enough rope to hang yourself.") [UNIX]
Martin Mareš, Pavel Machek

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.

Linuxové jádro a jak se v něm vyznat ("Jak pořádně otestovat fsck?") [KERN]
Pavel Machek

Co ten kernel vlastně je, čím se liší programování v kernelu od normálního kódu, jak sobě vlastní kernel postaviti a jak v něm něco opraviti. Kde najít nejnovější zdrojáky a kde najít pomoc, až se něco pokazí.

Sítě a Internet ("Sítě nejen na ryby.") [NET]
Martin Kruliš, Martin Mareš, Pavel Machek

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.

Sítě II – aneb aplikační protokoly TCP/IP ("Pokud jste se zamotali do sítí, tak se vás pokusíme vymotat.") [NET2]
Martin Kruliš, Martin Mareš

Tato přednáška navazuje na „Sítě a Internet“ a zaměří se na konkrétní aplikační protokoly nad TCP/IP. Zajímá vás, jak funguje web, pošta, DNS, FTP nebo třeba Telnet? Poodhalíme roušku tajemství těchto protokolů a když zbyde čas, přidáme ještě nějaké perličky jako RPC (vzdálené volání procedur) nebo SIP (protokol pro internetovou telefonii).

Předpoklady: NET
Mobilní zařízení ("Co je malé, to je hezké, a když ne, tak toho aspoň není moc.") [MOBI]
Pavel Machek

Čím se liší PDA a mobilní telefon, jak vlastně takový mobilní telefon funguje a jak vypadá struktura základnových stanic dovolující, aby fungovat mohl. Power management, vlastnosti různých baterií, metody šetření elektřinou, překlad všech možných 3-písmenných zkratek. Malý přehled toho, co se dá na takových malých věcech spustit, a velká ukázka telefonu, který nepodrazí.

Mobilní robotika ("3 years in artificial inteligence make you believe in God.") [ROBOT]
Pavel Machek

Jak naučit robota pohybovat se v prostoru. Problémy při konstrukci samočinných robotů, navigační algoritmy s omezeným množstvím paměti a veselé historky o tom, jak to vypadá, když se něco pokazí.

Informatické přednášky – lingvistika a zpracování jazyků

Jazyky, gramatiky a automaty [AUTO]
Martin Mareš

O jazycích přirozených, počítačových a matematických, jejich popisu a rozpoznávání. Začneme těmi nejjednoduššími: regulární jazyky a výrazy, konečné deterministické a nedeterministické automaty. Pak budeme stoupat po příčkách Chomského hierarchie, kam až to půjde.

Počítačová lingvistika ("Alkohol je silný, ale maso je zkažené...") [PLING]
Pavel Machek, Martin Mareš, Jana Kravalová

Přirozené jazyky a jak s nimi na počítači zápolit. Jak naučit program rozumět češtině nebo angličtině a nedejbože mezi nimi překládat (dokážeme vůbec říci, co to znamená?). Jak vypadá počítačová lingvistika a čím se liší od lingvistiky klasické. Lexikální, syntaktická a sémantická analýza vět a vztahů mezi nimi. O češtině, kterou vás učili ve škole, a jak je to doopravdy. Co nejde a co také nejde; příležitost k bezmocnému úpění? Ne tak docela, statistické metody by nás mohly aspoň zčásti zachránit: co je to korpus, entropie textu, jazykový model a k čemu je to všechno dobré. A co na to říká umělá inteligence. A co Jan Tleskač?

Rozpoznávání a syntéza řeči ("Babičko, a proč máš tak velké mikrofony?") [SYNT]
Pavel Machek

Co je potřeba udělat, aby počítač dovedl mluvit a poslouchat. Úvod do fonetiky – hlasové ústrojí, hlásky, fonémy, spektrální znázornění řeči. Formantová syntéza, difónová syntéza, transformace psaného textu na mluvený, modelování prosodie. Akustický a jazykový model, borcení časové osy.

Jazykové Zoo [JZOO]
Martin Mareš

Programovací jazyky jsou všelijaké – procedurální, funkcionální či logické, typované silně, slabě nebo třeba i vůbec, objekt... stop, vykládat si o všelijakých rodech, druzích a čeledích jazyků by byla nejspíš nuda, a tak si raději zajdeme do zoo a na ta zajímavější zviřátka se podíváme osobně: APL (či A+, případně J: průvan ve skladišti písmenek), Intercal (když existuje GO TO, proč by nemohlo existovat COME FROM?), Forth (pozpátku píšeme výrazy všechny úplně), Shakespeare (program coby divadelní hra), Oook!, Lingua::Romana::Perligata a další.

Kompilátory ("Jak se dělají kompilátory (a nebo komplikátory?)") [KOMP]
Martin Mareš

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

Informatické přednášky – grafika a typografie

Počítačová grafika ("Namaluj mi beránka...") [GFX]
Martin Mareš, Milan Straka, Martin Kruliš

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.

Geometrie a počítače ("Nerušte mé kruhy! (ani jiné kvadriky)") [GEOM]
Martin Mareš, Milan Straka

Základní algoritmy pro řešení geometrických úloh – konvexní obal, dva nejbližší body v rovině, výpočet obsahu nekonvexního mnohoúhelníka, lokalizace bodu, scanline algoritmus a jeho použití. Pokud bude čas a zájem, povíme si i něco o základech kombinatorické geometrie.

Barevné systémy [COLOR]
Martin Kruliš

Trocha o tom, jak je v počítačích, fotoaparátech, televizích a podobných zařízeních zapsáno, jakou mají jednotlivé pixelíky barvu. Systémy RGB, CMY(K), HSV, XYZ a jim podobné s jejich výhodami i neduhy. Půltónování, převody palet a základy stínování.

OpenGL ("Je libo krychličku nebo díru do ní?") [GL]
Milan Straka

Popovídáme si o tom, jak a kam se vyvíjí současná 3D grafika, dotkneme se shaderů a zjistíme, jak se to všechno programuje v OpenGL. Můžeme rozebrat i zatím navrhovaný standard OpenGL 3.0.

Předpoklady: GFX
PostScript ("Vy obrázky malujete? To my je programujeme...") [PS]
Martin Mareš

Jemný úvod do jazyka určeného k tisku grafiky a textu. Základní principy, řídící konstrukce a datové struktury, cesty a kreslení objektů, transformace souřadnic, DSC komentáře. Co je to PDF (Portable Document Format). Různé druhy fontů (např. Type1, TrueType) a jak fungují.

Formát JPEG [JPEG]
Milan Straka, Zbyněk Falt

Povíme si o tom, jak formát JPEG funguje, jak vypadá uvnitř a proč někdy dosahuje nebo nedosahuje dobrých výsledků. Také si povíme o tom, jak takové obrázky rychle načítat a ukládat.

Předpoklady: Povědomí o Fourierově transformaci (FFT)
Počítačová typografie ("What You See Is all What You've Got!?") [TYPO]
Martin Mareš

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? Jednou z možných odpovědí na všechny takové otázky je TeX – není sice WYSIWYG, ale nakonec zjistíme, že tak to je lepší. Ale u toho neskončíme: Metafont, Postscript, pdfTeX a sázení hudby pomocí Lilypondu.

Základní metody vykreslování fraktálů [FRAC]
Zbyněk Falt

Jak si nakreslit vlastní fraktál. Praktické ukázky IFS fraktálů a L-Systémů. Návod jak vykreslit a obarvit Mandelbrotovu a Juliovu množinu nebo Newtonovy fraktály.

Předpoklady: Znalost komplexních čísel (CPLX)

Matematické přednášky

Logika ("Tato věta sem nepatří.") [LOGI]
Martin Mareš, Milan Straka

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
Pravděpodobnost ("Většina lidí má nadprůměrný počet rukou.") [PP]
Martin Mareš, Milan Straka

Toto je přednáška o základech teorie pravděpodobnosti a statistiky. Dozvíte se, co to je podmíněná pravděpodobnost, rozdělení, střední hodnota nebo rozptyl, jak se to všechno počítá a k čemu je to dobré. Součástí přednášky bude i několik zajímavých příkladů z praxe a krátký kurs přežití ve světě plném chybných statistik.

Úvod do Ramseyovy teorie ("Dejte mi dostatečně velký objekt a já v něm najdu nějaký řád.") [RAMS]
Martin Mareš

Hříčka: ve společnosti šesti lidí vždy existují tři, kteří se navzájem znají, nebo neznají (ověřte ručně). Obecněji, pro libovolné „tři“ existuje „šest“ tak, že shora uvedené tvrzení platí. To je jedna z Ramseyových vět, které říkají, že v každém dostatečně velkém objektu vždy existuje nějaký stejnorodý podobjekt. Jednoduchá tvrzení Ramseyova typu, Ramseyova věta pro grafy dvou a více barev, pro systémy p-tic, nekonečná verze a aplikace. Populárně řečeno, chaos to má těžké.

Rovinné grafy ("Kdo nakreslí pět souvislých států tak, aby každý sousedil s každým, má u mě čokoládu.") [ROG]
Petr Kratochvíl

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ž zbyde čas, zkusíme grafy kreslit i na jiné plochy: kupříkladu Möbiovu pásku, pneumatiku nebo koule s ušima.

Základy algebry [ALGBR]
Milan Straka

Převážně neuspořádaný přehled základních matematických pojmů a konstrukcí. 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 – namátkou veřejná kryptografie, testování prvočísel, důkazy neřešitelnosti rovnic pátého a vyššího stupně...

Teorie množin a matematika nekonečen ("Je Vlk nedosažitelný kardinál?") [TEMNO]
Martin Mareš

Teorie množin tvoří páteř veškeré matematiky. Pomocí množin se totiž modelují veškeré objekty, které se v matematice vyskytují. Celou teorii prostupuje magický pojem nekonečno. Jakým způsobem se tohoto, pro spekulativní mysl ošidného, termínu zhostila moderní matematika? Množiny a jejich velikosti. Cantorův diagonální trik. Ordinály a houšť kardinálů. Potenciální kontra aktuální nekonečno. Myslíte si, že máte dobrou představu o tom, co jsou přirozená čísla? Možná vás z ní vyvedeme. A co teprve reálná čísla. Problematika volby axiomů determinovanosti versus výběru.

Grafy bez algoritmů [GRAFY]
Martin Mareš

Teorie grafů trochu teoretičtěji. Různé druhy grafů a jejich vlastnosti. Vrcholové a hranové barvení grafů, Eulerova věta, hamiltonicita grafů, rovinné grafy a grafy na plochách, Kuratowského věta, Eulerova formule, věta o skóre, grafové minory.

Lineární algebra [LA]
Martin Mareš, Milan Straka

Lineární algebra původně vznikla jako elegantní prostředek k popisování geometrie lineárních útvarů (bodů, přímek, rovin, ...) v libovolněrozměrném prostoru, ale ukázalo se, že její kouzlo dosahuje daleko dál. Vektorové prostory, lineární (ne)závislost, báze, lineární zobrazení a matice, determinanty, tenzory. Konečné projektivní roviny.

Teorie (vesměs samoopravných) kódů ("f y cn rd ths, y wll b gd cmptr prgrmmr!") [KODY]
Martin Mareš, Milan Straka

Jak komunikovat po lince, která průměrně každý k-tý bit přenese špatně? K tomu se hodí teorie samoopravných kódů, která nás naučí: distance slov a jejich souvislost s detekcí a opravou chyb, paritní a lineární kódy, perfektní kódy, Reed-Solomonovy a vůbec polynomiální kódy a několik dolních odhadů nádavkem. A jak s teorií kódů souvisí třeba čeština?

Komplexní a komplexnější čísla ("1=sqrt(1)=sqrt((-1)(-1))=sqrt(-1)sqrt(-1)=i· i=i2=-1. Huh?") [CPLX]
Martin Mareš, Milan Straka

Jak se nám matematika změní, když připustíme, že se záporná čísla také dají odmocňovat? Čísla imaginární a komplexní a jejich různé podoby. Součtové vzorce pro sin a cos dostaneme téměř zdarma. K čemu se hodí v matematice a k čemu ve fyzice. Proč se zastavit u dvou složek aneb quaterniony, octoniony a Cliffordovy algebry. Remember, life is complex.

Fourierova transformace [FFT]
Martin Mareš, Milan Staka

Chytrý trik pana Fouriera patří již dávno k matematické a fyzikální klasice a ukazuje se, že se hodí i při programování, počínaje digitálním zpracováním zvuku a obrazu (spektrální analýza či třeba komprese) a konče nečekaně rychlým násobením polynomů a předlouhých čísel.

Předpoklady: Základy komplexních čísel (CPLX)
Kombinatorika ("Nemám rád faktoriály. Faktoriály nemám rád. Rád nemám faktoriály...") [KOMB]
Martin Mareš, Milan Straka

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; taktéž metoda vytvořujících funkcí coby velký podvod v mezích zákona.

Teorie kombinatorických her ("Život je jen hra... Jakou má vyhrávající strategii?") [GAME]
Martin Mareš

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: všelijaké 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.

Fyzikální přednášky

Podzimní obloha [SKY]
Martin Mareš

Pozorování podzimní hvězdné oblohy spojené s astronomickým minikursem. Od antických a ještě starších bájí k modernímu příběhu o Velkém Třesku a naopak od celkem seriózní vědy k rozmarnému filosofování o světě a našem místě v něm. Hvězdáři a hvězdopravci, „Už staří Řekové...“, měření a vážení na dálku, vývoj hvězd a kosmologie, antropický princip, kdo schvaluje fyzikální zákony? Jak se podle hvězd orientovat a jak fungují sluneční a třeba i měsíční hodiny.

Předpoklady: Počasí dovolí. Měsíc nejlépe v novu.
Digitální elektronika [DIGI]
Martin Mareš, Martin Kruliš

Jak fungují digitální elektronické obvody, ze kterých jsou postavené (nejen) počítače. Nuly a jedničky jako napěťové úrovně; kombinační obvody (transistory, hradla, multiplexery), sekvenční obvody (klopné obvody, registry, čítače) a asynchronní obvody. Troška matematiky okolo aneb logické formulky a De Morganovy zákony; proč stačí jenom jeden typ hradel. Třístavová hradla a sběrnice ... zde plynule přecházíme v HW.

Ostatní přednášky

Ne-tak-úplně-obchodní angličtina [ENGL]
Pavel Machek

Jak napsat mail tak, abyste neurazili obchodníka, a jak napsat mail naopak tak, abyste ho urazili co největší kus. Umění chrlení ohně (a.k.a. flames) včetně praktických ukázek. A něco o tom, jak oheň nechrlit.

Lingvištika ("Přísudek je v této větě podmět.") [LING]
Martin Mareš

Převážně nevážné a mírně nepřed-vídatelné po-vídání o jazyku i jazyce. Kolik těch jazyků vlastně je, kde se vzaly a kam směřují? Slovní zásoba na cestách aneb nepožívejte odporné termity. Kde jsme přišli k pravidlům a proč pravidla nejsou všechno. Existují synonyma? A překlady? Proč je jazyk nejednoznačný a proč je to dobře. Co má společného čínština s angličtinou? Jak se na jazyk dívá matematik a jak se na matematiku dívají lingvisté. Jak vzniklo písmo? A jak otazník? &c.

Hudba v počítačích ("Na co gramofon? Pojďme poslouchat nuly a jedničky!") [HUPOC]
Milan Straka

Jak se vlastně hudba v počítači ukládá a jak se vyvíjely formáty pro ukládání hudby. Budeme si spíš povídat a pokud bude k dispozici technika, pustíme si i hojně ukázek.

MFF UK aneb co obnáší matfyzákem býti ("Maminko, ptá se tatínka, kdy už budu matfyzákem?") [MFF]

Nezávazné povídání o Matfyzu a základním matfyzáckém folkloru. 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.

Orientace [ORI]
Pavel Machek & Martin Mareš

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 zkreslení. Jak se neztratit v kartografii. Praktické cvičení v terénu.

Digitální fotografie [FOTO]
Pavel Machek

Jak za pomoci digitálního foťáku vytvořit fotku, na kterou se dá koukat, a o tom, co se dá zkazit tak, že už se na fotku koukat nedá. Vztahy mezi clonou, časem, citlivostí, rozmazáním fotky a šumem. Zoom a proč ho nepoužívat. Jak poznat špatný foťák a proč megapixely nejsou všechno. Jak kouzlit s foťákem, který nemá ani základní ovládání. K čemu se dá použít foťák v mobilu. Pokud počasí dovolí, vyrazíme ven: vlastní foťák vítán, vlastní krabička s CCD čipem taktéž.

Počítače a paragrafy ("In my country we have almost anarchy and I don't care.") [PRAVO]
Pavel Machek

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ě hromadneho ničení v rukou velkých firem, a co je patentový troll. Jak fungují trademarky a kdy se jim lze smát.

Předpoklady: Silný žaludek
Hry na hrdiny (a jiné) ("Trpaslík se otočil a vzhlédl do dálky. Hordy skřetů se blížily. Tohle bude dlouhý den...") [DRD]
Martin Kruliš, Aldar (mág 8. úrovně) a jeho družina

Hry na hrdiny a jiná RPG, tentokráte však bez počítače. O čem je slavné Dračí Doupě, z čeho vzniklo a jak vypadá jeho nová plusková varianta. Jaké jsou další hry na hrdiny v našich končinách (např. Gurps). Povídání lze zvrhnout i jiným směrem (Magic: The Gathering, jiné karetní hry, počítačová RPG, deskové hry...).

Předpoklady: Fantazie.