Ú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ů), dynamizace 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, 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.

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.

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

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.

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.

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.

Jak se kompilují a optimalizují funkcionální a logické programovací jazyky. Statická analýza programů, částečné vyhodnocování.

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.

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

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.

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

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.

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

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++ :–)

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

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.

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

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.

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.

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.

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.

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.

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

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.

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.

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.

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.