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

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.

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.

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.

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.

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

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

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.

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.

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

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.

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

Jak je vlastně možné, že se víc procesorů snese na jednom smetišti? Spinlocky, semafory, paměťové bariéry. K čemu je dobré dát víc vláken do jednoho procesoru a proč se dává víc procesorů na jednu destičku křemíku. Jak se nám z paměti RAM postupně stává „not-so-Random Access Memory“, co jsou cache a proč jsou dneska tak důležité.

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.

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.

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

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

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.

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.

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í. Právě operační systémy nám dokáží nahradit „divoký“ svět hardwaru pro programátora přijatelnou iluzí. 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.

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

Co ten kernel vlastně je, čím se liší programování v kernelu od normálního kódu, jak sobě vlastní kernel postaviti a jak v něm něco opraviti. Kde najít nejnovější zdrojáky a kde najít pomoc, až se něco pokazí.

O tom, jak šifrovací algoritmus RSA funguje, proč funguje a jestli bude ještě fungovat. A také jak se dá rozumně rychle naprogramovat (i pro HCS12, která se montuje třeba do klik od BMW).

Kamarád u černobílého textového okna září blahem. Chcete poznat, proč? Jak UNIX vznikl, k čemu je dobrý a k čemu třeba není. UNIXová filosofie. Kouzlo scriptů. Kouzlo speciálních souborů. Kouzlo propojování programů. Kouzlo nechtěného. UNIX byl napsán v C a C vzniklo pod UNIXem.

Máte autonomní subsystémy, které se potřebují dohodnout. Jak to udělat, když si mezi sebou potřebují vyměňovat informace. To vše se snaží řešit struktury vzletně nazvané multiagentní systémy. Rozdělování úloh, protokoly a další... třeba jak vypadá „burza práce“.

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.

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.

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.

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

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 zbyde-li čas, tak i některé obyčejné diferenciální rovnice.

Každé tvrzení je buďto pravdivé, nebo ne. Ale co když to není úplně jasné? Někdo tvrdí, že platí A, druhý B. Fuzzy logika se snaží najít cestu. Vypadá to jako pravděpodobnost? Ne tak úplně.

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.

Fyzika na střední škole se vyhýbá pojmu derivace jako čert kříži. Co všechno se dá spočítat, když už víme, co to je? Keplerovy zákony, harmonický oscilátor, vrh vzhůru s bržděním vzduchu, prověšení drátu (jen ideálního :–)) atd.

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