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é: dolní odhady a věty o hierarchii. Stroje s kvantifikátory, třída PSPACE a polynomiální hierarchie. Pravděpodobnostní třídy složitosti. Orákula a neuniformní složitost.

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.

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?

Důmyslnější datové struktury: trie, intervalové stromy, splay stromy, BB-α stromy; geometrické struktury pro lokalizaci bodů v rovině; binomiální a Fibonacciho haldy, leftist haldy a 2-3 haldy. Též několik přátelských randomizovaných datových struktur: skip listy a treapy.

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, slévání setříděných posloupností v konstantním prostoru, pravděpodobnostní testování prvočíselnosti a jiné kejkle.

Vyhledávání čehokoliv ve velkém množství textu: Prostá vylepšení brute-force algoritmů: Karp-Rabin, Boyer-Moore. A algoritmy chytřejší: Morris-Pratt, Knuth-Morris-Pratt, Aho-McCorasicková. Konečné automaty prakticky, regulární a „regulární“ výrazy.

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

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ě. Míchání karet.

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.

O tom, jak šifrovací algoritmus RSA funguje, proč funguje a jestli bude ještě fungovat. A také jak se dá rozumně rychle naprogramovat.

Jak si napsat vlastní jednoduchou realtime strategii ve stylu starého Dune. Seznámíte se se základy diskrétní simulace a algoritmem A^*, který slouží pro rychlé hledání cest.

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í, o jménech typů a o příkazu switch; alignment, NULL, void, volatile. Všelijaké zrady (velikosti typů, (a+b)+c ≠ a+(b+c), znaménka ...). Dialekty Céčka od K&R až po (staro)nový standard C99 a různá nestandardní rozšíření jazyka. Proč jsou objekty potřebnější v mysli programátorově než v jazyce a proč je C lepší než C++ :–)

Pokročilé techniky implementace algoritmů v C++. Šablony a jejich použítí, standardní knihovny STL a malý úvod do návrhových vzorů.

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, ovšem jak se ukázalo, též šikovný na spoustu dalších věcí. 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. Zkrátka jazyk, který lze jedině milovat nebo nenávidět, nic mezi tím.

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.

Povíme si, co je to jazyk XML, jak vznikl a k čemu je dobrý. Zároveň probereme nástroje pro práci s XML dokumenty, jejich načítání (parsování), generování, validaci atd. Z pokročilejších technik pak ukážeme vyhledávání v XML pomocí jazyka XPath a transformace XML dokumentů pomocí XSLT. Zbyde-li čas ukážeme si i několik konkrétních aplikací (XHTML, WML, SVG, ODF ...).

Řekneme si, jak fungují současné vnější paměti (především pevné disky) a jak se s nimi pracuje. Protože jsou o hodně pomalejší než operační paměti, je potřeba navrhnout vhodnější datové struktury, které urychlí čtení z takovýchto zařízení. Povíme si o sekvenčních, index-sekvenčních a indexovaných souborech. Navrhneme vhodné způsoby ukládání indexů (B-stromy, hašování). A zbyde-li čas, povíme si i něco o vyhledání podle více klíčů.

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.

Stručný přehled unixových utilit. Jak si napsat vlastní skript, přehled základních programových konstrukcí. V případě zájmu a času seznámení s programem awk.

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

Jak vypadá architektura dnešních operačních systémů aneb co musí programátor věďět, aby mu nepadala Wokýnka/Tučňáci. Správa procesů a vláken, plánování, synchronizace. Paměť, adresace a její přidělování. Správa souborů, filesystémy. Čemu se říká jádro a proč se spojuje s pudlem.

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

Jak funguje Internet a počítačové sítě vůbec: od elektronů v drátech (fotonů v optických kabelech, nebo elektro-magnetických vln) přes packety a jejich routing až k jednotlivým síťovým službám. Protokoly rodiny TCP/IP, síťové topologie (a proč Internet vlastně nemá žádnou), internetworking. Pár taktů hudby budoucnosti: IPv6, multicasting, přenos v reálném čase atd.

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

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.

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

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), Oook!, Lingua::Romana::Perligata 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.

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

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. Co je to PDF (Portable Document Format). Různé druhy fontů (např. Type1, TrueType) a jak fungují.

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, pdfTeX a sázení hudby pomocí Lilypondu.

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

Převážně neuspořádaný přehled základních matematických pojmů a konstrukcí. Pár magických slov pro představu: monoidy, grupy, okruhy, obory integrity, tělesa, vektorové prostory, polynomy, částečná uspořádání, booleovy algebry, filtry, ideály. Také si povíme, na co se takové věci dají použít.

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.

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. A jak s teorií kódů souvisí třeba čeština?

Chytrý trik pana Fouriera patří již dávno k matematické a fyzikální klasice a ukazuje se, že se hodí i při programování, počínaje digitálním zpracováním zvuku a obrazu (spektrální analýza či třeba komprese) a konče nečekaně rychlým násobením polynomů a předlouhých čísel.

Rozličné kombinatorické hry se zápalkami, kamínky, barvičkami či grafy. U některých si ukážeme výherní či obranné strategie, u některých dokážeme, že sice příslušná strategie existuje, ale nikdo ji ve skutečnosti nezná. Jak kombinatorické hry souvisí s M002. Zmíníme například: piškvorky, kruhové a zobecněné piškvorky, hex, různé varianty Nimu, vojáčci v poušti, speciality à la Herkules a Hydra, a další. Můžeme se zapovídat i o tom, jak podobné hry programovat na počítači.

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.

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.

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.

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 digitálního 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: vlastní foťák vítán, vlastní krabička s CCD čipem taktéž.