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:
Ú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
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ě.
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: I000Slož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: I001Co 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.
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: I003Jak 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í.
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.
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.
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.
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(n1.59) 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.
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.
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.
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č?
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.
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í.
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.
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.
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.
Jak funguje kvantové počítání. Náznak Shorova algoritmu pro faktorizaci čísel.
Předpoklady: Základy lineární algebry (M010)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.
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)))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.
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.
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)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.
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.
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).
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≠ NPDynamické 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.
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.
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ů.
V 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ě.
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.
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 číselPoví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á.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: I036Jednoho 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éč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++
:–)
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.
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.Čí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.
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.
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.
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+, případně J:
průvan ve skladišti písmenek), Intercal (když existuje GO TO
, proč by nemohlo
existovat COME FROM
?), Forth (pozpátku píšeme výrazy všechny úplně), Shakespeare
(program coby divadelní hra) a další.
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í čísloMá 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?
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.
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: I049Jak 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.
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.
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.
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.
Ř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Čí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
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: M000Obsahem 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.
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é.
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.
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.
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.
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.
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)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.
Vážené párování v bipartitních a obecných grafech, lineární programování a jeho dualita.
Předpoklady: I004Lineá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.
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.
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 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)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.
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
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.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.