Podzimní soustředění KSP 2002

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]
Daniel Kráľ, Martin Mareš

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]
Zdeněk Dvořák, Martin Mareš

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š

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]
Daniel Kráľ, Honza Kára, Martin Mareš

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]
Daniel Kráľ, 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

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]
Miroslav Rudišin, Zdeněk Dvořák

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

Počítačová lingvistika ("Klíč k rozeznávání lingvistů matfyzáckých a filozofických") [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.

Hammer ("Jak proměnit Itanium v Itanic?") [I014]
Pavel Machek

Jaké nástrahy s sebou přináší port operačního systému na nový procesor. Co je to ABI, proč je potřeba přenášet kompilátor a něco málo detailů o tom, jak „to dělá Kladivo“.

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

Strojový překlad ("Alkohol je silný, ale maso je zkažené.") [I016]
Pavel Machek

Jak to (ne)udělat, aby počítače překládaly. Historie strojového překladu, parsing, transfer, generování a něco málo o tom, jak se počítač může naučit překládat sám (statistické metody).

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.

Logické programování ("Detektivem za 90 minut.") [I018]
Tomáš Vyskočil

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]
Daniel Kráľ

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]
Martin Mareš, Daniel Kráľ

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š

Ještě jeden programovací jazyk, tentokráte ovšem nepříliš procedurální – naopak, všechno je funkce, zbytek jsou seznamy. Dozvíte se, že funkci vlastně nikdo nebrání, aby jako výsledek vracela jinou funkci (ne pointer na funkci, ale opravdovou funkci), a že alokaci a uvolňování paměti za vás udělá systém sám (co je to garbage collector?) a nakonec i to, že proměnná se vůbec nemusí nějak jmenovat.

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.

Advanced Haskell [I023]
Zdeněk Dvořák

Monády (Haskell – the world's finest imperative language? a mnohem víc), víceparametrické třídy a funkcionální závislosti, implicitní parametry, existenciální typy, generiky a spousta dalších hezkých triků.

Předpoklady: I022
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, Honza Kára

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]
Honza Kára

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]
Honza Kára

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š

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, ale třeba i dlaždičky v koupelně.

The Internet [I034]
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.

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 [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á.
Paralelismus ("Největším nepřítelem lidstva je trojrozměrný prostor.") [I037]
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.

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

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

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.

AirCastle Project ("Pojďte, zavřem' svoje krámky a jdem stavět vzdušné zámky!") [I043]
Martin Mareš

Jedna z možných budoucností počítačového světa: mikromodulární programování, autonomní putující objekty, large-scale distributed OS, generalizované interfejsy. Java a Corba naznačují cestu, ale jak udělat, abychom po ní někam došli? Object folding, on-line kompilace, dynamické optimalizátory a podobná udělátka. Distribuované ukládaní souborů od NFS a AFS až po Napster a Gnutellu. Sáhneme nejen po nejnovějších technologiích, ale také po těch prastarých a neprávem zapomenutých. Problémy s řízením distribuovaného světa aneb internetová ekologie.

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

Matematické přednášky

Logika ("Tato věta sem nepatří.") [M000]
Tomáš Vyskočil, Martin Mareš

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]
Honza Kára

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]
Tomáš Valla

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.

Barevnost grafů [M003]
Tomáš Valla

Co je to barevnost grafu a několik tvrzení o ní. Barvení grafů na plochách vyššího rodu, channel assignment problem, hranová barevnost, listové barvení, vybíravost grafů a jejich tříd.

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

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

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]
Daniel Kráľ

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

Předpoklady: Základy pravděpodobnosti (M001)
Grafy bez algoritmů [M008]
Daniel Kráľ

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]
Daniel Kráľ

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]
Daniel Kráľ, Martin Mareš

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]
Daniel Kráľ

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

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

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)

Fyzikální přednášky

Podzimní obloha [F000]
Martin Mareš, Honza Kára

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.