Úvod do moderní teorie vlkodlaků, čili též praktická dæmonologie a naiadologie.

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

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.

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

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.

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^1.59) 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.

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.

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.

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

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.

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.

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.

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

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.

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

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.

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.

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.

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.

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.

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?

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?

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.

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.

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

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.

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

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

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.

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.

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.

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

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.

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 nekonečno. 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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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