Podzimní soustředění KSP 2003

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]
Mistr Vševědění, Mistr Dveřník, Patron Chaotické, nefunkční a zvrhlé magie

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]
Knihovník, Mistr Dveřník, Dr. Faustroll, Patron Chaotické, nefunkční a zvrhlé magie

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]
Knihovník, Mistr Dveřník

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]
Mistr Vševědění, Tajemník Nejistých studií, Mistr Dveřník, Patron Chaotické, nefunkční a zvrhlé magie

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]
Mistr Vševědění, Mistr Dveřník

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]
Tajemník Nejistých studií

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]
Knihovník

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]
Externista z Démonických sfér, Mistr Dveřník

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]
Externista z Démonických sfér, Dr. Faustroll

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]
Externista z Démonických sfér

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]
Mistr Dveřník

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]
Patron Chaotické, nefunkční a zvrhlé magie

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.

Logické programování ("Detektivem za 90 minut.") [I018]
Profesor Katastrof

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.

Kvantové počítání [I019]
Mistr Vševědění, Dr. Faustroll

Jak funguje kvantové počítání. Náznak Shorova algoritmu pro faktorizaci čísel.

Předpoklady: Základy lineární algebry (M010)
Vyčíslitelnost ("S Halting problemem na věčné časy a ani o minutu déle!") [I020]
Mistr Dveřník, Mistr Vševědění

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]
Mistr Dveřník

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]
Knihovní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]
Knihovní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]
Knihovní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]
Knihovní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]
Knihovník, Tajemník Nejistých studií

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]
Knihovník, Mistr Dveřník, Mistr Vševědění

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]
Tajemník Nejistých studií

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]
Tajemník Nejistých studií

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]
Mistr Dveřník

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]
Mistr Dveřník, Knihovní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ě.

The Internet [I034]
Mistr Dveřník

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.

Kryptologie [I035]
Mistr Dveřník

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]
Mistr Dveřník

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]
Knihovní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]
Mistr Dveřník, Patron Chaotické, nefunkční a zvrhlé magie

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]
Mistr Dveřník

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 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]
Mistr Dveřník, Mistr Vševědění

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]
Mistr Dveřník

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]
Mistr Dveřník

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

Počítačová typografie ("What You See Is all What You've Got!?") [I044]
Mistr Dveřník

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]
Mistr Dveřník

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]
Mistr Dveřník

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

Fraktály a chaos ("Co je nahoře je i dole. Poznej to a budeš šťasten.") [I047]
Dr. Faustroll

Iterace funkcí, věta o pevném bodě. Rozdělení komplexní roviny na Juliovu a Fatouovu množinu. Jak definovat chaos. Mandelbrotova množina. Klasifikace komponent Fatouovy množiny. „Pohřbené“ komponenty. Hausdorffova dimenze.

Předpoklady: Vědět co je komplexní číslo
Matice a grafy ("Já pán, ty pán, ale kdo má graf v matici, je ještě větší pán.") [I048]
Strážce Toulavé nevědomosti

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]
Mistr Dveřník & Strážce Toulavé nevědomosti

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]
Strážce Toulavé nevědomosti

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]
Strážce Toulavé nevědomosti

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]
Knihovní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]
Mistr Dveřník

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í dvojnásob a právě operační systémy nám dokáží nahradit „divoký“ svět hardwaru pro programátora přijatelnou iluzí abstrakce. 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]
Tajemník Nejistých studií, Mistr Dveřník

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]
Knihovní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]
Externista z Démonických sfér

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

Matematické přednášky

Logika ("Tato věta sem nepatří.") [M000]
Mistr Dveřník, Dr. Faustroll, Profesor Katastrof

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 (Leibniz, Komenský etc.). Důkazy boží existence a neexistence.

Předpoklady: M000
Pravděpodobnost ("Většina lidí má nadprůměrný počet rukou.") [M001]
Tajemník Nejistých studií, Mistr Dveřník

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 variance, 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]
Patron Chaotické, nefunkční a zvrhlé magie, Mistr Dveřník

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 asi pro graf znamená?") [M003]
Patron Chaotické, nefunkční a zvrhlé magie

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]
Dr. Faustroll

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]
Knihovní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í, Boolovy algebry. Topologické prostory s body i bez nich. Kategorie.

Matematika nekonečen ("Je Vlk nedosažitelný kardinál?") [M006]
Mistr Dveřník, Dr. Faustroll

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.

Pravděpodobnostní metoda [M007]
Mistr Vševědění

Někomu se může zdát dokazování vět na základě pravděpodobnostního argumentu jako čirá magie. Pokud tento sen skončí, cíl přednášky byl splněn. Použití pravděpodobnostní metody v důkazech existence kombinatorických objektů; metoda střední hodnoty, metoda malých změn, metoda druhého momentu, použití Lovászova lokálního lemmatu.

Předpoklady: Základy pravděpodobnosti (M001)
Grafy bez algoritmů [M008]
Mistr Vševědění, Patron Chaotické, nefunkční a zvrhlé magie

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.

Matematické programování [M009]
Mistr Vševědění

Vážené párování v bipartitních a obecných grafech, lineární programování a jeho dualita.

Předpoklady: I004
Lineární algebra [M010]
Mistr Vševědění, Mistr Dveřník

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.

Matroidy [M011]
Mistr Vševědění

Teorie matroidů aneb jak to dopadne, když zkřížíme lineární algebru s teorií grafů. Co je to matroid, prostor cyklů, který matroid je reprezentovatelný, co to jsou matroidové minory a jak to všechno souvisí s hladovými algoritmy.

Předpoklady: M008, M010
Teorie kódů ("f y cn rd ths, y wll b gd cmptr prgrmmr!") [M012]
Mistr Dveřník

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.

Komplexní a komplexnější čísla ("1=sqrt(1)=sqrt((-1)(-1))=sqrt(-1)sqrt(-1)=i· i=i<sup>2</sup>=-1. Huh?") [M013]
Mistr Dveřník

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. Rovinná geometrie i goniometrie jako triviální operace s komplexními čísly. Proč jsou součtové vzorce pro sinus a cosinus na první pohled zřejmé. Komplexní konstrukce pětiúhelníků. Kořeny polynomů a proč má každé nenulové číslo n různých n-tých odmocnin. Komplexní fyzika – kruhové pohyby, komplexní tvar Newtonových zákonů, jak snadno odvodit odstředivou a Corriolisovu sílu a nezamotat se přitom ve vektorech. Proč se zastavit u dvou složek aneb quaterniony a octoniony. Remember, life is complex.

Fourierova transformace [M014]
Mistr Dveřník

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 do dějin i v informatice. 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]
Mistr Dveřník

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]
Mistr Dveřník & Patron Chaotické, nefunkční a zvrhlé magie

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

Fyzikální přednášky

Podzimní obloha [F000]
Mistr Dveřník, Tajemník Nejistých studií

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]
Mistr Dveřník

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.