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

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

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.

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

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

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.

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.

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.

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.

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

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.

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.