Podzimní soustředění KSP 2004

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 týden 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í...") [V023]
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í): kód předmětu (pro snadnější odkazování na konkrétní předměty; první písmenko značí obor), jméno přednášky, hvězdičky značící obtížnost (žádné pro velmi jednoduchou přednášku až dvě pro dosti náročnou), v uvozovkách motto přednášky; dále pak jméno přednášejícího, stručný obsah přednášky (na detaily se můžete ptát e-mailem nebo na místě) a speciální předpoklady nutné k účasti na přednášce (nutnost o něčem něco vědět, ale lze i jinak).

Informatické přednášky

Algoritmy a jejich složitost [I000]

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 [I001]

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: I000
Třídy složitosti [I002]
Martin Mareš, Tomáš Valla

Složitost opravdu důkladně: nejrůznější složitostní třídy 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é, aneb dolní odhady a věty o hierarchii. Alternace a třída PSPACE. Polynomiální hierarchie. Pravděpodobnostní třídy složitosti. Orákula a neuniformní složitost.

Předpoklady: I001
Grafy & algoritmy I ("Pojďme si hrát s obrázky") [I003]

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 [I004]

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

Předpoklady: I003
Datové struktury pro začátečníky [I005]

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, červeno-černé), haldy (binární a obecně regulární) a v neposlední řadě hashování.

Datové struktury pro pokročilé [I006]

Důmyslnější datové struktury: splay stromy, suffixové stromy, intervalové stromy; persistentní stromy a lokalizace bodů v rovině. Binomiální a Fibonacciho haldy, leftist haldy a 2-3 haldy. Též pár méně známých, ale velice přátelských struktur – radix trie a skip list.

Datové struktury pro šílence [I007]
Zdeněk Dvořák, Martin Mareš, Tomáš Valla

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ů), dynamizace et cetera.

Jazyky, gramatiky a automaty [I008]
Martin Mareš, Tomáš Valla

O jazycích přirozených, počítačových a matematických, jejich popisu a rozpoznávání. Regulární jazyky a výrazy, konečné deterministické a nedeterministické automaty. Bezkontextové a kontextové gramatiky a odpovídající výpočetní modely. Chomského hierarchie.

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

Na motivy knížky The Art of Computer Programming od prof. 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(n<sup>1.59</sup>) a možná i rychleji, introspektivní třídění, residuová aritmetika, skip-listy (k čemu se v datových strukturách hodí náhodná čísla), algebraické algoritmy, pravděpodobnostní testování prvočíselnosti, aproximační algoritmy a aproximační schémata.

Vyhľadávacie a triediace algoritmy ("Dnes sa zbavím bublifuku!") [I010]
Miroslav Rudišin, Tomáš Gavenčiak, Petr Škoda

Základné triediace algoritmy, ktoré sa oplatí vedieť: quicksort, mergesort, heapsort, radixsort a tiež niečo na veľké súbory – vonkajšie triedenie. Vyhľadávanie v poliach: polenie intervalu, hľadanie mediánu, resp. k-tého najväčšieho prvku v lineárnom čase.

Hledání v textu ("`Vyšívajme v senníku!' – kde jsem to jen viděl?") [I011]
Zdeněk Dvořák, Martin Mareš, Miroslav Rudišin

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

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

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?") [I013]
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.

Mobilní robotika ("3 years in artificial inteligence make you believe in God.") [I015]
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í.

Paralelismus ("Největším nepřítelem lidstva je trojrozměrný prostor.") [I016]
Martin Mareš

Když nestihne problém vyřešit jeden procesor, proč jich nepoužít víc? Paralelismus „v malém“ (počítačové clustery) i „ve velkém“ (datově paralelní výpočty) a jak nám v tom brání fyzikální zákony. Základní paralelní algoritmy, třídění toliko v logaritmickém čase a jiné neuvěřitelné věci.

PostScript ("Vy obrázky malujete? To my je programujeme...") [I017]
Tomáš Valla

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.

Vyčíslitelnost ("S Halting problemem na věčné časy a ani o minutu déle!") [I020]
Martin Mareš, Tomáš Valla

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. Výpočetní modely a univerzální stroje, rekurzivně spočetné a rekurzivní množiny a funkce. Halting problem a diagonální důkazy. O krok výš aneb orákula a relativní vyčíslitelnost, o krok níž aneb primitivně rekurzivní funkce. Věta o rekurzi a Riceova věta. Skoky a 1-generické množiny.

LISP ("Lots of Irritating Superfluous Parentheses?") [I021]
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í") [I022]
Zdeněk Dvořák

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í [I024]
Zdeněk Dvořák

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

Implementace neprocedurálních jazyků [I025]
Zdeněk Dvořák

Jak se kompilují a optimalizují funkcionální a logické programovací jazyky. Statická analýza programů, částečné vyhodnocování.

Předpoklady: Vědět, co jsou funkcionální a logické programovací jazyky (např. I024)
Voroného diagramy [I026]
Zdeněk Dvořák

Datová struktura z výpočetní geometrie s mnoha zajímavými souvislostmi. Jak je rychle zkonstruovat a jak s jejich pomocí vyřešit (skoro) cokoliv, od průchodu robota lesem po doručování pošty.

Panoptikum Programátorských Projektů [I027]

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.

Komprese dat ("Jenom ideální kapalina je nestlačitelná.") [I028]
Zdeněk Dvořák, Pavel Čížek, Miroslav Rudišin

Obsahem této přednášky je přehled základních kompresních algoritmů: statistické metody (Huffmanovo a aritmetické kódování), slovníková komprese (LZ77, LZ78) a pokud zbude čas, tak i něco o ztrátové kompresi obrázků a zvuku (prediktory, wavelets, JPEG, MPEG, fraktály).

PCP věta a její důsledky [I029]
Zdeněk Dvořák, Martin Mareš

Co všechno lze někomu dokázat, když mu z důkazu smíme ukázat jen 3 bity? Ukážeme, že mnohem víc, než bychom čekali. Jako důsledek pak dostaneme, že některé problémy jsou tak těžké, že je nejde řešit ani přibližně (například nalezení největší kliky v grafu).

Předpoklady: základy algebry (M010), složitosti (I001) a víra, že P≠ NP
Dynamické programování ("Kampak jsem si to jenom schoval?") [I030]
Tomáš Valla, Petr Škoda, Miroslav Rudišin

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.

Filesystémy ("Data sem, data tam, co já s nimi udělám?") [I031]
Miroslav Rudišin

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.

Hardware ("Babičko, a proč máš tak velké zuby?") [I032]
Martin Mareš, Pavel Machek

Jak vypadá počítač uvnitř, a to nejen obyčejné PC, ale třeba také superpočítač od Craye. Transistory, hradla a vůbec elektronickou drobotinu necháme na F001 a budeme se raději věnovat velkým věcem – pamětem, procesorům, sběrnicím, řadičům a také tomu, jak se takové věci programují. Trocha historie neboli komedie plná omylů.

Modely počítačů ("Nač Pentium? Máme Turingovy stroje!") [I033]
Martin Mareš, Zdeněk Dvořák

I032 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, 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?") [I034]
Pavel Machek

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

Kryptologie [I035]
Martin Mareš

Vše, co jste chtěli vědět o šifrování a báli se vám na to odpovědět. Š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. Jak šifru zkonstruovat a jak ji rozluštit. Předvedeme nerozluštitelnou šifru a dokonce to o ní i dokážeme.

Předpoklady: Víra v existenci náhodných čísel
Kompilátory ("Jak se dělají kompilátory (a nebo komplikátory?)") [I036]
Martin Mareš

Povídání o tom, jak překladače fungují uvnitř – jak se program parsuje, jak se optimalizuje kód atd. Co to jsou basic blocky, front end, back end, mezikódy, CSE, peephole optimizer, instruction scheduling, loop unrolling, loop strength reduction a jiná arkána umění kompilátorového. Některé věci převdedeme ctěnému publiku přímo na GCC.

Předpoklady: Základní povědomí o tom, co to je procesor a co dělá.
Kompilátory II ("Jak by se dnes kompilátory měly dělat") [I037]
Zdeněk Dvořák

Co nového se kolem překladačů objevilo v posledních letech. Postupné snižování úrovně mezikódu. Optimalizace přístupů k paměti a high-level loop optimalizace – přeskládávání, sekání a spojování smyček. Optimalizace řízené profilem – tj. tím, jak se program skutečně chová. Jak profil měřit a jak ho hádat. SSA forma a optimalizace na ní. Eliminace částečných redundancí.

Předpoklady: I036
Perl ("Jak Pejsek a Kočička vymýšleli programovací jazyk") [I038]
Martin Mareš, Tomáš Valla, Miroslav Rudišin

Jednoho dne se Larry Wall rozhodl, že nasype do jednoho velkého kotle spousty programovacích jazyků a unixovský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, ukázalo se, že velmi šikovný i na spoustu dalších věcí, jazyk obdivovaný i zatracovaný. 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.

C for wizards [I039]
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í a rovněž o jménech typů, alignment, NULL, void, volatile, extern a různá rozšíření jazyka. Také povídání o portabilním programování aneb jak napsat program tak, aby fungoval opravdu všude, a o (staro)novém standardu C99. A proč je C lepší než C<code>++</code> :–)

Předpoklady: Povšechná znalost jazyka C.
Aproximační algoritmy ("Součet úhlů v trojúhelníku je vždycky tři ... tedy alespoň ± 5%") [I040]
Martin Mareš, Tomáš Valla

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. Ne vše se aproximovat dá, ale to už přenecháme na I029.

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

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

Předpoklady: Vědět, co je to pravděpodobnost (M001), a být ochoten trochu počítat.
Počítačová aritmetika ("Je-li 0 dostatečně velká, může být skoro tak velká jako kousek jedničky.") [I042]
Martin Mareš

Čísla přirozená, celá, racionální a komplexní a jak s nimi počítače zacházejí či nedokáží zacházet. Floating point a floating slash reprezentace. Zaokrouhlovací chyby a proč a+(b+c) nemusí být rovno (a+b)+c. Intervalová a saturační aritmetika. Čísla obrovitánská a rychlé algoritmy pro počítání s nimi. Residuová aritmetika.

The Internet [I043]
Martin Mareš, Miroslav Rudišin

Jak funguje Internet a počítačové sítě vůbec: od elektronů v drátech (respektive fotonů v optických kabelech) přes packety a jejich routing až k jednotlivým síťovým službám. Vrstevnaté protokoly a kouzlo abstrakce (ale pozor, jsou i špatní kouzelníci), různé síťové topologie (a proč Internet vlastně nemá žádnou), jak se sčítají jablka s hruškami (a propojují naprosto nekompatibilní protokoly) a jak si naprogramovat vlastní protokol. Pár taktů hudby budoucnosti: IPv6, multicasting, přenos v reálném čase atd.

Počítačová typografie ("What You See Is all What You've Got!?") [I044]
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, následníci TeXu, jako je třeba pdfTeX nebo Omega.

Stringové algoritmy ("Co se nedá spočítat v lineárním čase, nestojí za to.") [I045]
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 k čemu všemu mohou být dobré: „inverzní“ vyhledávání, nejdelší společný substring, nejdelší palindrom, n-gramové statistiky a třeba i Burrows-Wheelerova transformace.

Jazykové Zoo [I046]
Martin Mareš

Programovací jazyky jsou všelijaké – procedurální, funkcionální či logické, typované silně, slabě nebo třeba i vůbec, objek... 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<sup>+</sup>, případně J: průvan ve skladišti písmenek), Intercal (když existuje <code>GO TO</code>, proč by nemohlo existovat <code>COME FROM</code>?), Forth (pozpátku píšeme výrazy všechny úplně), Shakespeare (program coby divadelní hra) a další.

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

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?

Počítačová grafika ("Čáry nejsou žádná chytrost") [I049]
Martin Mareš & Milan Straka

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

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

Jedna z nejmódnějších věcí dneška – akcelerovaná 3D grafika – textury, odlesky, dynamické stíny... Co je to OpenGL, k čemu se hodí a k čemu se nehodí. A má vůbec budoucnost?

Předpoklady: I049
Hudba v počítačích ("Na co gramofon? Pojďme poslouchat nuly a jedničky!") [I051]
Milan Straka, Pavel Machek

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.

Programování s omezujícími podmínkami [I052]
Zdeněk Dvořák

Trochu jiný přístup k obtížným úlohám. Některé úlohy sice vypadají, jako by se za dobu existence vesmíru nedaly vyřešit, nicméně pro rozumně velké vstupy to přesto potřebujeme. Jak backtrackovat rychleji a radostněji – backjumping, backmarking, limited discrepancy search, a jak neprobírat úplné nesmysly – hranová konzistence, konzistence po cestě, bodová konzistence.

Operační systémy [I053]
Martin Mareš

Podle některých filosofických škol je celý svět pouhá iluze. Jestli je to pravda, nevíme, ale uvnitř počítačů to obvykle platí. Právě operační systémy nám dokáží nahradit „divoký“ svět hardwaru pro programátora přijatelnou iluzí. Jak operační systémy dneška vypadají a jak by třeba také mohly vypadat. Mnohé ctěnému publiku předvedeme na jádru Linuxu.

Geometrie a počítače ("Nerušte mé kruhy!") [I054]
Martin Mareš

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í pro výpočet obsahu sjednocení obdélníků. Pokud bude čas a zájem, povíme si i něco o základech kombinatorické geometrie.

Lineární programování [I055]
Zdeněk Dvořák

Řešení úlohy lineárního programování. Simplexová metoda, lineární programování v pevné dimenzi, elipsoidová metoda. Celočíselné programování a metody řešení – branch and bound, cutting plane.

Předpoklady: M009
Mobilní zařízení ("Co je malé, to je hezké, a když ne, tak toho aspoň není moc") [I056]
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.

Linuxové jádro a jak se v něm vyznat ("Jak pořádně otestovat fsck?") [I057]
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í.

Systémy pro správu versí [I058]
Pavel Machek

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 BitKeeperu a archu. 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.

RSA [I059]
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 (i pro HCS12, která se montuje třeba do klik od BMW).

.NET and C# ("Od čeho pochází název CéMříž – vězení? ") [I060]
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é. Rozebereme používaný mezikód i důvody, proč ho (ne)používat, a vezmeme si na mušku i C#.

UNIX ("UNIX gives you enough rope to hang yourself.") [I061]
Tomáš Valla, Martin Mareš

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.

Barevné systémy [I062]
Tomáš Gavenčiak

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

Multiagentní systémy ("Já jsem agent 007, kdo jsi ty?") [I063]
Petr Škoda

Máte autonomní subsystémy, které se potřebují dohodnout. Jak to udělat, když si mezi sebou potřebují vyměňovat informace. To vše se snaží řešit struktury vzletně nazvané multiagentní systémy. Rozdělování úloh, protokoly a další... třeba jak vypadá „burza práce“.

Cvičení brainstormingu [I064]
Miroslav Rudišin

Oddychové setkání, na kterém vás obeznámíme s metodou kolektivního řešení problémů a pak si zkusíme něco společně vyřešit.

Matematické přednášky

Logika ("Tato věta sem nepatří.") [M000]
Martin Mareš, Pavel Čížek, Tomáš Gavenčiak

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

Obsahem této přednášky by měly být základy pravděpodobnosti. Dozvíte se, co to je podmíněná pravděpodobnost, rozdělení, střední hodnota nebo rozptyl, jak se to počítá a k čemu je to dobré. Ukážeme si i jak spočítat pravděpodobnost, že dojde k odchylce určité velikosti. Součástí přednášky bude i několik zajímavých příkladů z praxe.

Úvod do Ramseyovy teorie ("Dejte mi dostatečně velký objekt a já v něm najdu nějaký řád.") [M002]
Tomáš Valla, 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é.

Barevnost grafů ("Bílá, modrá, červená, co to pro graf znamená?") [M003]
Tomáš Valla

V teorii grafů zaujímá významné místo problém barevnosti grafu, tedy přiřazení co nejmenší počtu barev vrcholům tak, aby se hranami dotýkaly pouze různobarevné vrcholy. Aplikace problému v informatice je nasnadě. Ukážeme si několik zajímavých teoretických výsledků. Barvení grafů na plochách vyššího rodu, channel assignment problem, hranová barevnost, listové barvení, vybíravost grafů a jejich tříd.

Neuronové sítě [M004]
Petr Škoda

Základy neuronových sítí. Biologický a formální neuron, perceptron. Back propagation, učení bez učitele. Asociační sítě a několikero příkladných modelů (Kohonenovy mapy, Hopfield). Simulované žíhání, genetické algoritmy.

Základy algebry [M005]
Zdeněk Dvořák

Převážně neuspořádaný přehled základních matematických pojmů a konstrukcí. Grupy, okruhy, tělesa, vektorové prostory. Polynomy a řešení (a neřešitelnost) rovnic. Částečná uspořádání, Booleovy algebry. Topologické prostory s body i bez nich. Kategorie.

Matematika nekonečen ("Je Vlk nedosažitelný kardinál?") [M006]
Martin Mareš, Tomáš Gavenčiak, Tomáš Valla

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. Problematika volby axiomů determinovanosti versus výběru.

Grafy bez algoritmů [M008]
Martin Mareš, Tomáš Valla

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 [M010]
Martin Mareš, Tomáš Valla

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. Konečné projektivní roviny. Fisherova nerovnost jako ukázka použití lineárně algebraických metod.

Teorie kódů ("f y cn rd ths, y wll b gd cmptr prgrmmr!") [M012]
Martin Mareš

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=i<sup>2</sup>=-1. Huh?") [M013]
Martin Mareš

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 a octoniony. Remember, life is complex.

Fourierova transformace [M014]
Martin Mareš, Pavel Čížek

Fourierova transformace patří již dávno k matematické a fyzikální klasice a poté, co pánové Coole a Tukey objevili, jak ji efektivně počítat, vešla i do informatických dějin. Spektrální analýza a digitální zpracování zvuku i obrazu (a třeba i JPEG, ten sice není založen přímo na FT, ale na jiné podobné transformaci). Superrychlé násobení polynomů a předlouhých čísel. Zobecnění FT aneb waveletové transformace i vícerozměrné verze.

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

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.

Kombinatorická teorie her ("Život je hra... A jakou má vyhrávající strategii?") [M016]
Martin Mareš & Tomáš Valla

Rozličné kombinatorické hry se zápalkami, kamínky, barvičkami či grafy a jak na ně vymýšlet strategii. Stavové grafy, minimaxový algoritmus, hry coby Conwayova čísla. Také pár slov o tom, jak se strategie programují.

Derivace, integrály, ap. [M017]
Pavel Čížek

Ve fyzice se často setkáme s rovnicemi typu a=∂ v / ∂ t. Co dělat, když se a mění? Derivace, integrál, jak se počítají, a zbyde-li čas, tak i některé obyčejné diferenciální rovnice.

Trachtenbergův rychlý systém základní matematiky ("Jak fungují geniální děti?") [M018]
Tomáš Gavenčiak

Zde se dozvíte (a možná i naučíte), jak vynásobit čísla rychleji než na kalkulačce, jak velmi rychle (a přesně) sčítat, odčítat, dělit a odmocňovat. Součástí přednášky je kurs netradičního myšlení při triviálních matematických operacích (bez malé násobilky).

Předpoklady: Sčítání a odčítání do 40 zpaměti, násobení a dělení dvěmi.
Úvod do fuzzy logiky [M019]
Petr Škoda

Každé tvrzení je buďto pravdivé, nebo ne. Ale co když to není úplně jasné? Někdo tvrdí, že platí A, druhý B. Fuzzy logika se snaží najít cestu. Vypadá to jako pravděpodobnost? Ne tak úplně.

Fyzikální přednášky

Podzimní obloha [F000]
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 [F001]
Martin Mareš

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

Světlo [F002]
Pavel Čížek

To, že je světlo elektromagnetické vlnění, asi každý ví. To, že elektrická a magnetická složka ve světle svírají pravý úhel, je známo o něco méně. Ale jak se k tomu vlastně dospělo? Maxwellovy rovnice a jak z nich plyne světlo. Snellův zákon.

Předpoklady: Trochu povědomí o tom, co je derivace (M017) (a nebo věřit, že to, co píšu, je dobře).
Newtonova mechanika, jak se nebere na střední škole [F003]
Pavel Čížek

Fyzika na střední škole se vyhýbá pojmu derivace jako čert kříži. Co všechno se dá spočítat, když už víme, co to je? Keplerovy zákony, harmonický oscilátor, vrh vzhůru s bržděním vzduchu, prověšení drátu (jen ideálního :–)) atd.

Předpoklady: Vědět, co je derivace (M017) a komplexní čísla (M013).
Relativita [F004]
Pavel Čížek

Všechno je relativní. I čas. Nezáživná hodina ve škole je o hodně delší než ta zábavná. A nebo to tak Einstein nemyslel? Jak se dospělo ke speciální teorii relativity a jak se projevuje (a to nejen ve velkých rychlostech).

Ostatní přednášky

Ne-tak-úplně-obchodní angličtina [X000]
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.

Bojová umění [X001]
Zdeněk Dvořák

Výhradně teoretický (alespoň ze strany přednášejícího) úvod do problematiky bojových umění. Principy, historie, mýty (čti drby).

Lingvištika ("Přísudek je v této větě podmět") [X002]
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é. &c.