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ší třídy složitosti 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, 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.

Probereme vše, co by měl správný programátor vědět. Co jsou a k čemu slouží intervalové stromy. Jaké se pomocí nich dají řešit úlohy. Probereme množství stromů v 1D, 2D a více-D, statické i dynamické. Ukážeme implementaci podle Fenwicka, binárně indexované stromy i rekurzivní konstrukci. Jak se dají elegantně napsat za 5 minut. Jako bonus hromada příkladů.

Základní třídící algoritmy, které se vyplatí znát: quicksort, mergesort, heapsort, radixsort a také něco na velké soubory – vnější třídění. Vyhledávání v polích: půlení intervalu, hledání mediánu resp. k-tého největšího prvku v lineárním čase.

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 jejich použití, nebo třeba hledání nejdelšího společného podřetězce dvou řetězců.

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.

Kryptologie čili tajuplná nauka o šifrách, jejich konstrukci a hlavně o jejich luštění. Přísně tajné. Š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. Předvedeme nerozluštitelnou šifru a dokonce to o ní i dokážeme.

RSA je asi nejpoužívanější asymetrický šifrovací algoritmus dnešní doby. Povíme si o tom, jak funguje, proč funguje a jestli bude ještě fungovat. A také jak se dá rozumně rychle naprogramovat.

Datové typy jazyka C, programové konstrukce, základy práce s ukazateli. Seznámení se standardními knihovnami jazyka C.

Objektově orientované programování přináší jiný náhled na návrh řešení problémů. Vysvětlíme, jak se liší objektové a procedurální programování. Co je to objekt a co třída. Základní vlastnosti objektů (dědičnost, zabalení, polymorfismus). Co je to metoda, překrývání metod, virtuální metody (pozdní vazba) a čistě virtuální (abstraktní) metody. Syntaxe a odlišnosti v jazycích C++, C#, Java, Object Pascal, PHP, ...

Co je to genetirká struktura, jak v C napsat spojový seznam, spojovou mřížku, kde se do toho hodí void *, dědičnost (ano, v C) a preprocesor. Šablony v C++, aneb neexistuje věc, která by nešla napsat, jen existuje spoustu, které se nevyplatí. Jak to řeší jiné jazyky (Java, Haskell, Perl) a jakou za to mají cenu.

Rozdíly mezi klasickou Javou a Javou pro mobilní zařízení. Základní struktura programů (midletů). Jak naprogramovat vlastní user interface, kreslit a rozpohybovat obrázky, připojit se na internet a jak ukládat údaje do pevné paměti telefonu.

Jednoho dne se Larry Wall rozhodl, že nasype do jednoho velkého kotle spousty programovacích jazyků a unixový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. Malé ochutnání Perlu6, jazyka (snad už nepříliš vzdálené) budoucnosti.

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.

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.

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.

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

Jak vyvíjet program delší dobu a nezbláznit se u toho. Něco o tom, jak verze 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.

Kdo píše programy, které vždy hned fungují, ať se přihlásí. A kdo ne, ať se přihlásí na tuto přednášku. Ukážeme si několik nástrojů, jak si pomoci z nejhoršího. Mezi nimi třeba gdb, řádkový debuger (odvšivovač), nebo valgrind. Kdy je použít a kdy se více hodí printf. Proč assert je tak užitečná věc.

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.

Jak optimalizovat programy napsané v assembleru, a tak program ještě více urychlit. Stručné seznámení s architekturou procesorů. Ukázka konstrukcí, kterým je třeba se vyhnout; čím je nahradit. Seznámení s MMX a SSE instrukcemi.

Úvod do problematiky vytváření dynamicky generovaných webových stránek. Syntaxe jazyka PHP, netypovost, (ne)pole. Základní postupy pro boj s uživatelem (a proti němu). Zamícháno s XHTML, JavaScriptem, CSS a možná i (My)SQL.

Historie a vývoj počítačových technologií a současných architektur. Co je to procesor, jak se programuje (instrukční sady) a jak se chová. Přehled tříd procesorů (skalární a vektorové, RISC). Jak procesor komunikuje s okolím (čipová sada). Nezbytné periferie: vnitřní a vnější paměti, vstupní a výstupní zařízení.

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 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 a filesystémech pro netradiční nasazení (konkrétně žurnálovací a distribuované FS).

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

Tato přednáška navazuje na „Sítě a Internet“ a zaměří se na konkrétní aplikační protokoly nad TCP/IP. Zajímá vás, jak funguje web, pošta, DNS, FTP nebo třeba Telnet? Poodhalíme roušku tajemství těchto protokolů a když zbyde čas, přidáme ještě nějaké perličky jako RPC (vzdálené volání procedur) nebo SIP (protokol pro internetovou telefonii).

Co ovládá vaše náramkové hodinky, MP3 přehrávač nebo třeba cyclocomputer. Ukážeme si, jak se programuje procesor bez OS. PIC kontra AVR. I2C, RS232, LCD displej, 7-segmentovka. Alarm a autoalarm, elektronika v autě a proč se nová auta opravují víc s notebookem než manuálně. Řízení světelné křižovatky dříve a nyní a proč není kruhový objezd lepší. Home-made řízení modelové železnice a srovnání s reálným provozem. Možná ukázky existujících zařízení.

Základy počítačové bezpečnosti a ochrany informace. Co je to trusted base a můžeme ji věřit. Bezpečnostní modely (Bell-LaPadula, Biba, ...) a různé implementace. Co je to bezpečnostní politika a proč by jeden měl nějakou mít. Na závěr si ukážeme běžné typy útoků na informační systémy.

Praktické pokračování distribuovaných systému. Podíváme se na zoubek standardu CORBA. A že těch zoubků je! Jak funguje RPC a messaging. Jak se definují interfaces v IDL a proč se takový koncept vůbec používá.

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.

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, objekt... 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 a jejich rasterizace. 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í.

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řirozená, celá, racionální, reálná, hyperreálná. K tomu ordinální. Komplexní? Nadreálná! Znásobíte s nimi pí s nekonečnem na druhou a vyhrajete rozhodnou bitvu proti globálnímu kapitalismu. Nadto pěkně souvisí s kombinatorickou teorií her.

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 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čí: vzdálenost 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?

Co a k čemu je teorie čísel. Počítání v kongruenci, Euklidův algoritmus a jeho použití. Malá Fermatova věta, Čínská zbytková věta a k čemu v praxi jsou. Jak si odvodit kritéria dělitelnosti a nějaké další úchylnosti (třeba výpočet poslední cifry čísla 42^42{42}).

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.

Klasická i šílená planimetrie podle přání publika. Konstrukce trojúhelníků ze všeho možného, Apolloniovy a Pappovy úlohy. Zobrazení od souměrností po afinitu a kruhovou inverzi. Geometrické důkazy a věty, různé středy trojúhelníka, Feuerbachova kružnice devíti bodů a další čtyři její významné body, Cevova a Menelaova věta. Kouzlo tětivových čtyřúhelníků a nepřeberné množství dalších témat.

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.

Nezávazné povídání o Matfyzu a základním matfyzáckém folkloru. 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éž.

Hry na hrdiny a jiná RPG, tentokráte však bez počítače. O čem je slavné Dračí Doupě, z čeho vzniklo a jak vypadá jeho nová plusková varianta. Jaké jsou další hry na hrdiny v našich končinách (např. Gurps). Povídání lze zvrhnout i jiným směrem (Magic: The Gathering, jiné karetní hry, počítačová RPG, deskové hry, ...).

České předmětové olympiády z pohledu soutěžícího i nezávislého pozorovatele. Jak se dostat do celostátního kola, jak (možná) dojít až do mezinárodní olympiády a která cesta vede zaručeně do pekel. Příspěvek ze strany korespondenčních seminářů, aneb zapomeňte školní znalosti, ty vám nepomůžou.

České koleje a co po nich jezdí, trocha historie. Život okolo železnice, řízení dopravy. Proč (asi) se srazily vlaky v Moravanech – metody zjišťování volnosti koleje a další speciality. Co je to šotouš a kde ho můžete spatřit.