Podzimní soustředění KSP 2005

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é: 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: 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 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: 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 [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ů), obecné dynamizační schéma, triky pro malé integery, persistentní datové struktury 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, residuovou aritmetiku, introspektivní třídění, slévání v konstantním prostoru, 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]
Tomáš Gavenčiak, Petr Škoda, Martin Kruliš, Milan Straka

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š, Martin Kruliš, Milan Straka

Vyhledávání čehokoliv ve velkém množství textu: Prostá vylepšení brute-force algoritmů: Karp-Rabin, Boyer-Moore, Morris-Pratt, Knuth-Morris-Pratt, Aho-McCorasicková. 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í.

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

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 N<sup>2</sup>, 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.

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. Co je to PDF (Portable Document Format). Různé druhy fontů (např. Type1, TrueType) a jak fungují.

Logické programování ("Detektivem za 90 minut.") [I018]
Jana Kravalová, Pavel Čížek, Zdeněk Dvořák

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. Pokud zbude čas, i něco málo k modernějším jazykům – Goedel a Mercury.

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

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 ("Jnm idln kpln j nstlčtln.") [I028]
Zdeněk Dvořák, Pavel Čížek, 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).

PCP věta a její důsledky [I029]
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

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.

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, buněčné 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?") [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é.

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 je to front end, back end, „middle-end“, mezikód, CSE, peephole optimizer, instruction scheduling, loop unrolling, loop strength reduction 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á.
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

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 ("<code>{ }1[x]+++++x[1]</code>") [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í, 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. Také povídání o portabilním programování aneb jak napsat program tak, aby fungoval opravdu všude. 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ě. Míchání karet.

Předpoklady: Vědět, co je to pravděpodobnost (M001), a být ochoten trochu počítat.
The Internet [I043]
Martin Mareš

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

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, 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?

Počítačová grafika ("Čáry nejsou žádná chytrost") [I049]
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. 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

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! (ani jiné kvadriky)") [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. Malý přehled toho, co se dá na takových malých věcech spustit.

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

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.

.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, Martin Mareš

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

Databáze a DB systémy ("SELECT * FROM beaverknowledge WHERE code="DB" LIMIT na hoďku a půl") [I065]
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.

CD ("Cimrmanův Disk") [I066]
Tomáš Valla

Každý je zná, každý je používá. A skoro nikdo neví, jak ve skutečnosti fungují. Fyzikální vlastnosti CD, výroba lisovaných disků, konstrukce snímače (čočka, zaměřování). Fyzická struktura a mnohaúrovňové zabezpečení dat: EFM, rámce, sektory, subkanály a stopy, L1 a L2 Reed-Solomonovy samoopravné kódy na rámcích a sektorech, a další. Různé formáty disků: CD-DA, CD-ROM, jakož i exotické (S)VCD, CD-i, aj. Média CD-R a CD-RW. „Ochrany proti kopírování“ (čti: úmyslně poškozené disky) paranoidních nahrávacích společností, které jsou vlastně ve skutečnosti k ničemu. Pokud zbude čas, nakousneme i modernější disky DVD.

Formát JPEG [I067]
Milan Straka

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 (M014)
Kryptologie ("Gbgb arav zbp gnwan mcenin.") [I068]
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.

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

Pokročilejší (dešifruj: zběsilejší) partie vědy kryptologické: utajené výpočty, zero-knowledge proofs, digitální peníze, volební systémy, sdílení tajemství, podprahové informace a kvantová kryptografie. 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í (I068) a víra v existenci náhodných čísel

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š

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

Teorie množin a matematika nekonečen ("Je Vlk nedosažitelný kardinál?") [M006]
Martin Mareš, Tomáš Gavenčiak, Tomáš Valla, Pavel Čížek

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 <i>nekonečno.</i> 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ů [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, Pavel Čížek, Tomáš Gavenčiak

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 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š, Pavel Čížek

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 [M014]
Martin Mareš, Pavel Čížek

Fourierova transformace patří již dávno k matematické a fyzikální klasice a poté, co pánové Cooley 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.

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

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á. Jak kombinatorické hry souvisí s M002. 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.

Derivace a integrály [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 zbude-li čas, tak i některé obyčejné diferenciální rovnice.

Úvod do fuzzy logiky ("Pravda je někdy i trochu lež.") [M019]
Petr Škoda

Svět není černobílý. Někdy se hodí mít připravenu i jinou odpověď než <i>ano</i> a <i>ne.</i> Na otázku „Jsem bohatý?“ si lze vymyslet celou řadu odpovědí. Matematici se ale nenechali zahanbit a vytvořili kolem toho celou teorii.

Předpoklady: M000

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: Znát pojem derivace (M017).
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).

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é. Jak vzniklo písmo? A jak otazník? &c.

Seminář strunných hudebních nástrojů ("Hendrixem za 90 minut") [X003]
Tomáš Valla

Hudební nástroje více či méně příbuzné s dnešní kytarou patří v současnosti k těm nejrozšířenějším. Kytaře se budeme věnovat přednostně, dostaneme se však i k nástrojům, jako jsou banjo, mandolína, brač, loutna a další. Jak se liší různé druhy kytar, jak funguje kytara elektrická, elektroakustická, steel-kytara. Doplňky (kapodastry, slidery, typy strun), tabulatury, nákup a údržba nástrojů. Různé hráčské techniky a především jejich hojné praktické ukázky, při vhodném počtu zájemců možno rovnou propojit s jejich výukou.

MFF UK aneb Co obnáší matfyzákem býti ("Maminko, ptá se tatínka, kdy už budu matfyzákem?") [X004]
Milan Straka & Martin Mareš & kdokoliv další

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.

Orientace [X005]
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 [X006]
Pavel Machek

Jak za pomoci digitalniho 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: vlastni foťák vítán, vlastní krabička s CCD čipem taktéž.