Seznam přednášek

Zde je orientační seznam toho, co můžeme přednášet. Je toho však tolik, že to ani zdaleka nestihneme odpřednášet všechno. Byli bychom tedy rádi, kdybyste si vybrali, co byste slyšeli nejraději. Seznam zdaleka není úplný, takže se nelekněte, že bude občas zařazena přednáška, kterou jste zde nepotkali.

Seznam preferovaných přednášek můžete zasílat do 26. července 23:45 CEST (SELČ) na mail mq@ucw.cz. Doporučený formát je seznam kódů přednášek, které uvádíme v hranatých závorkách, setříděný podle síly preference sestupně.

Informatické přednášky – teoretické

Algoritmy a jejich složitost [SLOZ]

Čím menší je časová složitost algoritmu, tím větší je složitost kódu.

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ě. Ukázky jednoduchých (obvykle třídících) algoritmů a výpočet jejich složitosti.

Složitější složitost [SLOZ2]

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

Třídy složitosti [SLOZ3]

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.

Základní algoritmy [ZALG]

Základní výbavou každého informatika jsou různé standardní algoritmy, zde si ukážeme ty nejdůležitější z nich: Třídící algoritmy včetně vnějšího třídění. Trocha rekurze: hledání mediánu nebo obecněji k-tého nejmenšího prvku v lineárním čase. Aritmetika s dlouhými čísly. Železničářský algoritmus na vyhodnocování výrazů.

Ne až tak základní algoritmy [NZALG]

Pokročilá technologie není rozlišitelná od magie.

O algoritmech značně magických a nečekaných. Jak násobit n-ciferná čísla rychleji než v kvadratickém čase. Kouzlo na slévání setříděných posloupností v konstantním prostoru. Isomorfismus stromů pomocí přihrádkového třídění. Bitové kejklířství.

Vyčíslitelnost [VYCIS]

S Halting problémem na věčné časy!

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. Jak se ale dokazuje, že něco nejde? Matematický pohled na výpočetní modely a univerzální stroje, rekurzivně spočetné a rekurzivní množiny a funkce. Halting problem a diagonální důkazy.

Grafy & algoritmy [GA]

Pojďme si hrát s obrázky

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.

Prohledávání do hloubky [DFS]

Nášup grafových algoritmů, zejména různé chytré aplikace prohledávání do hloubky: topologické třídění, hledání mostů a artikulací, komponenty silné souvislosti, kreslení grafů jedním tahem.

Nejkratší a jiné cesty [CESTY]

Všechny cesty vedou do Horní Dolní, jen některé přes Řím.

O problému hledání cest v grafech trochu podrobněji. Obecné relaxační schéma, Bellmanův-Fordův a Dijkstrův algoritmus a jejich zrychlení pomocí různých datových struktur. Potenciálová redukce a heuristiky (třeba A^*). Souvislosti s násobením matic: transitivní uzávěr, Seidelův algoritmus, Kleeneho algoritmus a regulární výrazy.

Toky v sítích [TOKY]

Když je v grafu povodeň, těsní?

K čemu je dobré, když grafem teče voda. Předvedeme si klasický problém toků v sítích a jeho všelijaké, mnohdy dosti překvapivé aplikace. Jak rozestavět n věží na šachovnici a jak ji místo toho pokrýt dominovými kostkami? Další souvislosti, jako třeba násobná souvislost grafů.

Datové struktury pro začátečníky [DS1]

Pole oraná a neoraná, stromy ovocné a okrasné.

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, splay), haldy (binární a obecně regulární) a v neposlední řadě hashování.

Datové struktury pro pokročilé [DS2]

Haldy a jiné kupky.

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.

Datové struktury pro šílence [DS3]

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ů), obecné dynamizační schéma, triky pro malé integery, persistentní datové struktury et cetera.

Intervalové stromy [ITREE]

Já bych ty intervaly nejradši… dal do stromu!

Intervalový strom je datová struktura pracující s intervaly, se kterou se můžeme setkat v mnoha úlohách (zejména soutěžních). Řekneme si, co to intervalový strom je, jaké všechny druhy intervalových stromů existují a jejich použití si ukážeme na úlohách. Na závěr si představíme jednu „magickou“ datovou strukturu jménem Fenwickův strom.

Dynamické programování [DYNP]

Kampak jsem si to jenom schoval?

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.

Hledání v textu [TEXT]

>>Vyšíváme v seníku!<< – kde jsem to jen viděl?

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

Regulární výrazy a regexy [REGEX]

Jednoduché předpisy pro vyhledávání v textu. Jak vyhledat a nahradit různě šílené části, přejmenovat hlavního hrdinu, nahradit konstrukci v kódu za jinou konstrukci a jak napsat jednodušší parser. Jako bonus brutality jako detekce správně uzávorkovaného řetězce (do libovolné hloubky).

Stringové algoritmy [STRG]

Co se nedá spočítat v lineárním čase, nestojí za to.

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

Komprese dat [PRESS]

Jnm idln kpln j nstlčtln.

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), Burrowsova-Wheelerova transformace (BZIP). Pokud zbude čas, tak i něco o ztrátové kompresi obrázků a zvuku (prediktory, wavelets, JPEG, MPEG, fraktály).

Pravděpodobnost a algoritmy [PPALG]

Nejen že Bůh hraje v kostky, ale ještě při tom občas švindluje!

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.

Numerické paralelní výpočty [PARAL]

Největším nepřítelem lidstva je trojrozměrný prostor.

Když nestihne problém vyřešit jeden procesor, proč jich nepoužít víc? Zkusme na chvíli zavřít oči a představit si, že máme stroj, který umí například pro sečtení N čísel zapnout N procesorů … nebo rovnou N², všechny se společnou pamětí a společným programem – teoretikové takovému počítači říkají PRAM. Ukážeme si rychlé paralelní algoritmy všeho druhu: aritmetiku, slévání a třídění, grafové algoritmy, vše v (poly)logaritmickém nebo dokonce konstantním čase.

Kryptologie [CRYPT]

Gbgb arav zbp gnwan mcenin.

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.

Kryptologie II [CRYPT2]

6140 a184 c9a6 41f1 de99 e733 354a f451

Pokročilejší (dešifruj: zběsilejší) partie vědy kryptologické: utajené výpočty, zero-knowledge proofs, sdílení tajemství, podprahové informace a kvantová kryptografie. Aplikace v reálném životě: digitální peníze, volební systémy. Různé metody útoků na šifry a kryptografické protokoly. Problémy distribuce klíčů a proč se jí raději vyhnout (a jak: Diffie-Hellman key agreement, komutativní šifry). Stručný přehled souvisejících partií matematiky a teorie složitosti.

Modely počítačů [MODEL]

Nač Pentium? Máme Turingovy stroje!

Všechny počítače jsou si rovny, jen některé jsou si rovnější. Teoretický model počítače, 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é a grafové automaty, ale třeba i dlaždičky v koupelně.

Informatické přednášky – programovací jazyky a techniky

Programování v jazyce C [C]

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

C for wizards [CWIZ]

1[x]+++++x[1]

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++ ☺

Generika a objekty v C [TEMPL]

Má C typovou kontrolu? Ano, ale jen občas.

Co je to generická 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++ a v C, aneb neexistuje věc, která by nešla napsat, jen existuje spousta, které se nevyplatí. Jak to řeší jiné jazyky (Java, Haskell, Perl) a jakou za to platíte cenu.

Bash [BASH]

Psaní skriptů a pokročilých skriptů pro UNIX. Základní dovednost linuxového roota – umět skript napsat, pochopit a odladit (v tomto pořadí obtížnosti).

Bash jako programovací jazyk [BASH2]

Při zahloubání se do dokumentace bashe lze narazit na mnohá temná zákoutí a divokou syntaxi. Ukážeme, jak se v tomto bahně rochnit a jak ho použít pro zrychlení skriptů a napsání věcí nevídaných.

Perl [PERL]

Jak Pejsek a Kočička vymýšleli programovací jazyk

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.

Python [PYTH]

Základy programování v Pythonu, syntaxe, datové typy, slovníky, objektový model (aneb všechno je objekt). Standardní knihovny a interaktivní interpretr.

Django [DJANGO]

Weby v Pythonu na počkání, brutality do tří dnů.

Jak napsat v Pythonu web snadno a rychle, tedy pokud na to mám server. Hrátky s databází bez bolení hlavy, přihlašování a komentáře bez jediného řádku kódu, administrační rozhraní vytvořené jediným řádkem. Šablony a oddělení kódu od vzhledu (aneb principy MVC a DRY).

Logické programování [LOGP]

Detektivem za 90 minut.

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.

LISP [LISP]

Lots of Irritating Superfluous Parentheses?

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.

Haskell [HASK]

Pro ty, kdo uncinofobií trpí

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. Pokud zbude čas, tak také trochu bezpečného vícevláknového a paralelního programování.

Jazyk SQL [SQL]

SELECT something FROM knowledge LIMIT 45min

Jazyk SQL a jeho aplikace. Jak ušetřit skriptu práci a sobě čas, aneb jak se zeptat rovnou na to, co chci vědět. K čemu se hodí složený dotaz a klíčové slovo JOIN. Kam až si můžu dovolit zajít, když nevím, na kterém systému to poběží.

Jazyk XML a související technologie [XML]

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

Git a jiné systémy pro správu verzí [GIT]

U svatýho tučňáka, kdo sem napsal tohle? Ono to tvrdí, že JÁ?!

Jak vyvíjet program delší dobu a nezbláznit se u toho. Různé systémy pro správu verzí od diff/patch přes CVS a SVN až ke Gitu. Jak Git funguje: stromy, commity, větve, tagy. Merge mezi větvemi nebo mezi různými počítači. Kouzelnické triky: hledáme bugy půlením historie, přepisujeme dějiny. Jak se liší správa zdrojáků v projektech o jednom, deseti a tisíci programátorech.

Jak se nestat vepřem [STYLE]

/* You are not expected to understand this */

Tvrdí se, že číst kód je mnohdy těžší, než ho psát – dokonce i po sobě, stačí krátká doba. Je několik obecně uznávaných pravidel, jak kód psát a jak ne, aby byl hezký a dobře čitelný. Od základních (rozumná pojmenovací konvence, systematické odsazování), až po to, kdy opravdu použít goto a jak napsat užitečný komentář nebo dokumentaci. K čemu je a není dokumentace v kódu. A kdy se vyplatí se na všechna tato pravidla vybodnout. Určeno především začátečníkům a zapřísáhlým teoretikům.

Správa paměti [MEM]

Když má program sklerózu…

Po chvíli zjistíme, že nám lokální a globální proměnné nestačí a je potřeba paměť alokovat dynamicky. Co všechno si musíme udělat sami a co se děje programátorovi „za zády“. Mapování adresního prostoru, ruční alokování a vracení paměti a problémy s tím spojené (chyby programátora), počítání odkazů a daň s nimi spojená (a hele, cyklus), odklízeče odpadu.

Make [MAKE]

make love ... don't know how to make love

Hodil by se otrok, který by překládal jednotlivé soubory. Základní syntaxe takového otroka, jak napsat jednoduchý Makefile, který řeší překlad Céčkového programu, automatické řešení závislostí. Jak to udělat, aby výsledek neměl několik tisíc řádek. Proč by se hodilo, aby tu bylo něco lepšího.

Gdb a jiné ladící nástroje [GDB]

Jak se ladí kytara, jak křišťálová koule a jak program (řazeno dle obtížnosti)

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ý debugger (odvšivovač), strace, nebo valgrind. Kdy je použít a kdy se více hodí printf. Proč assert je tak užitečná věc.

Textový editor Vim [VIM]

Víš, jaký je nejlepší textový editor? Vim.

Odložme na chvíli své myše a pojďme si vyzkoušet textový editor, který umí poslouchat na slovo. Pravda, budeme se ta slova muset chvíli učit, ale výsledek bude proklatě efektivní. Základní příkazy, práce s regulárními výrazy, makra, kouzla. Vimovité ovládání jiných programů, třeba webového prohlížeče.

Portabilní programování [PORT]

Šel si program na vandr …

Většina programátorů dřív nebo později zjistí, že počítačový svět nekončí hranicí jejich monitoru a že je mnohem rozmanitější než nekonečné zelené pláně windowsové pracovní plochy. Jenže jak se v takovém světě domluvit a jak psát programy, aby fungovaly všude? Na co se dá spolehnout a na co ne, jaké se hodí znát jazyky a jaké knihovny k nim. K čemu jsou dobré standardy a k čemu configure. Proč je někdy potřeba vynalézat kolo. Za rok se vrátím aneb jak (nechat) program udržovat.

Programování v Linuxu [PLX]

Jak si program pod Linuxem povídá s operačním systémem, když chce otevřít soubor, přečíst soubor, půjčit trochu paměti a jiná šprťouchlata. Předvedeme si, jaká existují v Linuxu systémová volání. Naučíme se namapovat si soubor rovnou do paměti, posílat a odchytávat signály, uspávat a probouzet proces, plodit děti a další. Pokud zbyde čas, můžeme si napsat démona a klienta a povídat si po síti.

Multithreading [THREAD]

K čemu je programu více vláken a jak zařídit, aby si vlákna vzájemně nešlapala po nohách. Úlohy vhodné k paralelizaci a kde to nemá smysl. Problémy s paralelním přístupem ke zdrojům a jak je řešit. Co jsou synchronizační primitiva, kritické sekce a bariéry a k čemu jsou volatile proměnné. Co je to deadlock a proč je noční můrou mnoha vývojářů. Proč nám knihovny házejí klacky pod nohy.

Optimalizace [OPTIM]

Mám skvělý algoritmus, tak proč to sakra běží tak pomalu?

Role překladače při optimalizaci a jak mu usnadnit práci. Jak fungují cache a jak této znalosti využít. Proč zdvojnásobení počtu procesorů nezvedne výkon dvakrát. Přístup do paměti z více vláken, contention points, profiling. Lži, zatracené lži a benchmarky a co si z nich vybrat.

Dynamický web a PHP [PHP]

Pepíčku, napíšeš mi é-šopík?

Základy praktické tvorby dynamického webu. Úvod do jazyka PHP a Javascriptu, čtení dat z odeslaných formulářů, přesměrování, databáze, generování obrázků a další.

Co je na PHP špatně [PHPBAD]

Stokrát opakovaná lež je stále lež.

PHP má velkou výhodu, je všude. Pak má prý ještě další výhody, ale nikdo si nemůže vzpomenout, jaké. Zato není těžké vyjmenovat, co je na PHP špatně. Není to nic velkého, samé malé věci, ale zato jich je hodně. Přehled problémů, se kterými se v PHP dříve či později potkáte, přičemž se budete mlátit do hlavy, proč jste radši nezačali s něčím hezčím.

Programování v assembleru [PASM]

Jak programovat procesor přímo, aniž by vám do toho mluvily překladače, linkery a podobná verbež. Začneme obecně, ale soustředíme se hlavně na procesory rodiny x86. 32-bitová a 64-bitová instrukční sada, FPU a panoptikum vektorových instrukcí. Rozdíly mezi intelovskou a AT&T syntaxí. Jak spojit assembler s vyššími programovacími jazyky. Optimalizace kódu. Stručný úvod do systémových architektur IA32 a AMD64.

Informatické přednášky – hardware, operační systémy a spol.

Architektury [ARCH]

Ne gotika a baroko, ale systémové architektury. Jaké jsou hlavní typy procesorů a čím se liší a co z toho se opravdu používá v praxi. Von Neumann a Harvard, RISC a CISC, Intel a ARM, jednočipy, vektorové procesory. Komunikace s pamětí a periferiemi, north a southbridge. Instrukční sady, assembler.

Jak vyrobit multiprocesor [MULPR]

Vyrábět nic nebudeme, ale povíme si o tom, jak je možné poskládat více CPU do jednoho systému. SMP, NUMA a další. Cache a jejich koherence, hierarchie cachí. FSB, HyperTransport a QuickPath. Exekuční jednotky a Hyper-Threading, architektura Bulldozer.

Digitální elektronika a hradla [DIGI]

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 …

UNIX [UNIX]

UNIX gives you enough rope to hang yourself.

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 skriptů. Kouzlo speciálních souborů. Kouzlo propojování programů. Kouzlo nechtěného. UNIX byl napsán v C a C vzniklo pod UNIXem.

Přeložme si vlastní linuxový kernel [KERNC]

Kde kernel vzít, čím se liší jednotlivé stromy a jak do toho zapadají distribuční jádra. Co je k překladu kernelu potřeba, jak kernel nakonfigurovat, přeložit a nainstalovat a jak se v tom všem vyznat. Jak aplikovat do svého kernelu změnu, která ještě není oficiálně začleněna.

Napišme si vlastní linuxový ovladač [KERNM]

Vyrobíme si vlastní modul do linuxového kernelu, který sice nebude umět zázraky, ale bude náš. Dozvíte se základy programování v kernel space, interface kernelu k modulům, jak kernel komunikuje s hardware.

Spravujeme server [SLS]

Kolik uživatelů ti nadává, tolikrát jsi adminem.

Povídání o tom, co se všechno může stát, když spravujete server v nepřátelském prostředí internetu. Bezpečnost až na prvním místě. Od uživatele, který prozradil heslo ke svému webmailu spambotovi, přes špatně nakonfigurované služby, občasné čtení logů, zálohování apod. až do situace, kdy server spadnul nebo byl napaden a musíme vyrazit na místo. Užitečné pro začínající adminy.

Počítačové sítě [NET]

Základy fungování počítačových sítí. Trocha historie aneb od kabelových přenosů k moderním přenosovým technologiím a Internetu. Síťové vrstvy a nevrstvy aneb od drátů přes pakety k aplikačním protokolům. Síťové topologie a směrování aneb proč data nezabloudí. Na závěr si osaháte krimpovací kleště.

Internet [INTERNET]

Jak funguje Internet, a to pěkně do hloubky. Protokoly IPv4, IPv6, TCP, UDP, HTTP, FTP a další. IP a DNS adresy, jejich přidělování a překlad (a nedostatek). Velmi lehce naťukneme směrování a povíme si, proč je NAT špatný a jak funguje firewall.

IPv6 [IPV6]

Jak se liší IPv6 od IPv4 aneb není to jen o počtu bitů v adrese. Konfigurace IPv6 klienta, IPv6 routeru a IPv6 serveru. Kde vzít IPv6 adresu, když mi ji provider nechce dát. Proč neexistuje NAT nad IPv6. DNS, IPsec a mobilita.

Wifi zevnitř [WIFI]

Co je Wi-Fi(TM) a co je standard IEEE 802.11. Proč je to wifi tak složité, co znamenají ty divné zkratky jako AP, WEP, WPA, TKIP, EAP a RTS a jak se liší "personal" od "enterprise". Jak si poradit, když to jede pomalu. Čím se wifi liší od jiných bezdrátových technologií.

Web uvnitř [HTTP]

Error 402: Payment Required. Please insert a coin.

Většina webu je dnes založena na protokolu HTTP, pojďme se podívat, jak funguje uvnitř. Metody GET, POST, ale třeba i PUT. Dohadování o typu dat. Cacheování, revalidace a transformace dat. Křupavé sušenky. Jak se vypořádat s dynamicky generovaným obsahem aneb protokol CGI. Mezi klientem a serverem aneb DNS a virtuální servery. Nakonec do toho všeho přimícháme SSL/TLS a máme HTTPS.

E-mail [EMAIL]

Drahoušek zákazník.

Co se stane s e-mailem, když jej odešlete? Kudy chodí a kudy jej čerti nesou? Jaké máte záruky, že přijde; proč občas přijde pozdě nebo vůbec. Problém formátů a kódování, chyby webových i jiných klientů. Protokoly SMTP, POP, IMAP a co se stane, když do nich přimícháme SSL/TLS. E-mailová bezpečnost, spam, viry, phishing a BFU. Nakonec státní datové schránky a proč je to zlý ošklivý nepěkná věc.

DNS [DNS]

Neviditelný stín v pozadí Internetu

DNS je starý a přesto moderní protokol. Stojí na něm infrastruktura celého Internetu. Slouží k překladu adres, ale nejen k tomu. Jak zajišťuje spolehlivost, jak bezpečnost. A proč si na něj ani Anonymous netroufnou.

Exploity, DoS a záludné chyby [DOS]

Zajímavosti ze světa počítačové bezpečnosti, příklady typických chyb a jak se dají zneužít. Absolutní bezpečnost neexistuje, záleží jenom na tom, za kolik vám zabezpečovaná věc stojí. Spíše sbírka příkladů a historek než ucelená přednáška.

Informatické přednášky – lingvistika a zpracování jazyků

Jazyky, gramatiky a automaty [AUTO]

O jazycích přirozených, počítačových a matematických, jejich popisu a rozpoznávání. Začneme těmi nejjednoduššími: regulární jazyky a výrazy, konečné deterministické a nedeterministické automaty. Pak budeme stoupat po příčkách Chomského hierarchie, kam až to půjde. Jak výpočetně silný je třeba takový automat na kafe?

Jazyková Zoo [JZOO]

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

Kompilátory [KOMP]

Jak se dělají kompilátory (a nebo komplikátory?)

Povídání o tom, jak překladače fungují uvnitř – jak se program parsuje, jak se optimalizuje kód atd. Co je to front end, back end, „middle end“, mezikód a jiná arkána umění kompilátorového. Jak psát programy tak, aby kompilátoru chutnaly, co optimalizovat ručně a co naopak udělá kompilátor lépe než my.

Informatické přednášky – grafika a typografie

Počítačová grafika [GFX]

Namaluj mi beránka …

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.

Geometrie a počítače [GEOM]

Nerušte mé kruhy! (ani jiné kvadriky)

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í, Voroného diagramy a souvislost s persistentními datovými strukturami.

Barevné systémy [COLOR]

Co je na konci duhy?

O podstatě světla a barevného vidění a různých pokusech o reprezentaci barev v počítačích, fotoaparátech, televizích a podobných zařízeních. Systémy RGB, CMY(K), HSV, XYZ, Lab s jejich výhodami i neduhy. „Systém“ Pantone. Reálné kontra imaginární barvy aneb proč nejde vyfotit duha.

Jak ukládá obrázky počítač [IMG]

V kriminálním seriálu: „Zaostřete mi tu SPZ!“

Rozdíl mezi bitmapovou a vektorovou grafikou. Souborové formáty BMP, GIF a PNG. Proč není JPEG formát vhodný na webovou grafiku, ale fotkám neublíží. SVG a další vektorové grafické formáty a metody konverze na bitmapu. Proč v reálném světě není možné „zaostřit“ SPZ nebo lidskou tvář jako v seriálech.

PostScript [PS]

Vy obrázky malujete? To my je programujeme …

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

MetaFont, MetaPost [MF]

Teď ten obrázek takhle zkroutím a pak ho přeložím.

Lehké nakousnutí jazyka, ve kterém můžete opravdu kreslit planimetrické obrázky, ale i třeba písma nebo piktogramy do zadání a řešení KSP. Jak vypadají CM fonty (ty, které používá TeX) a jak se autorovi povedlo, že se z jediného „obrázku“ dá vygenerovat tlusté, tenké, rovné, skloněné, šišaté písmenko.

Typografie [TYPO]

What You See Is all What You've Got!?

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. Přineste knihy i letáky, zkritizujeme sazeče, co se do nich vejde.

TeX [TEX]

No pages of output. Ask a TeXnician.

Z předchozí přednášky máme představu o tom, jak vypadá pěkná sazba. K její výrobě nám pomůže typografický systém TeX. Praktická přednáška s ukázkami použití TeXu od hladké sazby knihy až po zběsilosti hraničící s programováním. Jak do TeXu vkládat obrázky a jak to raději nedělat. Kde shánět další informace: TeXbook, TeXbook naruby a další zajímavá literatura. Praktické rozdíly mezi různými dialekty TeXu. Všelijaká rozšíření: pdfTeX, eTeX, LuaTeX.

Matematické přednášky

Logika [LOGI]

Tato věta sem nepatří.

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.

Teorie množin a matematika nekonečen [TEMNO]

Je Vlk nedosažitelný kardinál?

Teorie množin tvoří páteř veškeré matematiky. Pomocí množin se totiž modelují veškeré objekty, které se v matematice vyskytují. Celou teorii prostupuje magický pojem nekonečno. 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. A co teprve reálná čísla. Problematika volby axiomů determinovanosti versus výběru.

Grafy bez algoritmů [GRAFY]

Teorie grafů trochu teoretičtěji. Různé druhy grafů a jejich vlastnosti. 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 [LA]

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.

Teorie (vesměs samoopravných) kódů [KODY]

f y cn rd ths, y wll b gd cmptr prgrmmr!

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?

Komplexní a komplexnější čísla [CPLX]

1=√(1)=√((-1)(-1))=√(-1)√(-1)=i· i=i²=-1. Huh?

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, octoniony a Cliffordovy algebry. Remember, life is complex.

Úvod do teorie čísel a RSA [NUT]

Po malém fermetu mívám čínský zbytkáč.

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. Malý výlet do algebry a příslušné zobecnění pár srandovních pozorování. Jak z toho všeho odvodit RSA – asi nejpoužívanější asymetrický šifrovací algoritmus dnešní doby. Jak RSA funguje, proč funguje a jestli bude ještě fungovat. Generování klíčů, faktorizace kontra testování prvočíselnosti.

Fourierova transformace [FFT]

Chytrý trik pana Fouriera patří již dávno k matematické a fyzikální klasice. Převapivě se ale hodí i při programování: rychlé násobení polynomů a dlouhých čísel (dokonce v lineárním čase), digitální zpracování zvuku a obrazu (spektrální analýza či třeba komprese).

Kombinatorika [KOMB]

Nemám rád faktoriály. Faktoriály nemám rád. Rád nemám faktoriály …

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.

Teorie kombinatorických her [GAME]

Život je jen hra … Jakou má vyhrávající strategii?

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 příslušná strategie existuje, i když nevíme, jak vypadá. Zmíníme například: všelijaké 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.

Syntetická planimetrie [PLANI]

Desátý bod kružnice devítí bodů

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.

Deskriptivní geometrie [DG]

Jak splácnout tři rozměry do dvou

Jemný úvod do Mongeova promítání a axonometrie. Jak nakreslit krychli aby vypadala „jako živá“, jak narýsovat na list papíru dvě navzájem kolmé roviny a poznat, kde se protínají a spousta dalších zajímavých konstrukcí.

Teorie nemožného [NONEX]

Neexistence důkazu není důkazem neexistence. Dokažte.

Existenci slona v Africe snadno dokážete tím, že ho přivedete. Jak ale ukázat, že tam žádný slon není, případně že sice je, jenže ho nejde najít pomocí pravítka, kružítka a jeepu? Přímo se to dělá těžko, ale existuje spousta krásných triků, jak neřešitelnost problémů dokazovat. Nesložitelné hlavolamy, nerozvázatelné uzly, nepopsatelná čísla, neroztřetitelné úhly, nealgoritmické problémy a jiné slasti nekonstruktivní matematiky. Jak naopak ukázat, že něco existuje, aniž bychom věděli, jak to vypadá?

Ostatní přednášky

MFF UK aneb co obnáší matfyzákem býti [MFF]

Maminko, ptá se tatínka, kdy už budu matfyzákem?

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.

Autorský zákon [AUTH]

Podrobné osvětlení českého (potažmo evropského) autorského zákona. Na co máme právo, co nesmíme, co je to užití díla a jak fungují licence. Bittorent vs. uložto. Jak a proč novináři lžou a jak je to jinde ve světě.

Open source a free software [OSS]

Cože, ono se na tom dokonce dá vydělávat?

Jak open source software (OSS) funguje a jaktože funguje. Co je to ta "komunita", o kterou zavadíte okamžitě poté, co k OSS přičichnete. Proč free software nutně neznamená "zdarma". FSF, LF a další organizace. Licence a právní otázky.

Patenty a trademarky [PAR]

Patenty, copyrighty, trademarky a podobný obtížný hmyz. Jak patenty škodí, jak se jim vyhnout a kdy je lepší nevědět. Zbraně hromadného ničení v rukou velkých firem a co je patentový troll. Jak fungují trademarky a kdy se jim lze smát. Autorské svazy, poplatky, ACTA a co s tím má společného George Orwell. Přineste svoji oblíbenou EULA, zasmějeme se.