Záznamy přednášek - Smršť 2018

↩ zpět na seznam všech přednášek

Akce: Krutá Smršť Přednášek 2018

Algoritmy a datové struktury

Fourierova transformace [FFT]

Jak rychle umíte násobit n-ciferná čísla? My to umíme lineárně. Hodí se k tomu chytrý trik pana Fouriera, který už dávno patří k matematické a fyzikální klasice. Ukážeme, co je Fourierova transformace zač, jak ji rychle spočítat a k čemu je dobrá: rychlé násobení polynomů i čísel, digitální zpracování zvuku a obrazu (spektrální analýza či třeba komprese).

Otevřít přednášku (webový přehrávač)

ICO-Dict ("Chtěli jste si pořídit strom, ale zjistili jste, že na něj nemáte místo? Máme řešení!") [ICODICT]

Někdy v šedesátých letech byl objeven in-place heapsort a s ním implicitní halda (taková ta permutace prvků v poli, kde potomci i-tého prvku jsou na pozicích 2i a 2i+1) a následně byla položena otázka, zda by náhodou nešlo vyrobit i implicitní strom. Vydáme se tedy na cestu za datovou strukturou, která pozůstává jen z nějaké prapodivné permutace n prvků v poli, a která umí Insert, Find, Delete, Min, Max, Pred i Succ v čase O(log n). Jo a jen tak mimochodem to bude celé cache-oblivious.

Otevřít přednášku (webový přehrávač)

Intervalové stromy ("Já bych ty intervaly nejradši... dal do stromu!") [ITREE]

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.

Otevřít přednášku (webový přehrávač)

Stromové algoritmy ("Půjdeme na to od lesa") [TREES]

Stromy jsou jednou z nejtypičtějších (a nejjednodušších) odrůd grafů. Ledacos pro ně umíme řešit mnohem rychleji než pro obecné grafy, tak se pojďme podívat, jak se to dělá. Předvedeme několik obecných technik pro práci se stromy: DFS očíslování, „vandalskou indukci“, intervalové reprezentace. Různé rozklady: heavy-light, Fredericksonův, separátorový a ST-stromy.

Otevřít přednášku (webový přehrávač)

Dovednosti

Orientace [ORI]

Jak ze neztratit v terénu a jak se neztratit na moři. Vývoj umění navigace. K čemu je důležité slunce a hvězdy, ale proč mořeplavcům nestačí, alespoň dokud neobjevíme hodinky. Použití mapy, busoly a GPSky. Orientace bez pomůcek a použití Ariadniny nitě. Bleskový úvod do sférické astronomie a časomíry čili jak (ne)postavit sluneční a třeba i měsíční hodiny. Jak reprezentovat mapu v počítači a jak raději ne. Jak zapisovat polohu místa na Zemi (přestože Země má tvar podivně nakousnuté hrušky) a kolika způsoby to jde. Různé druhy map a jejich (z)kreslení. Jak se neztratit v kartografii. Praktické cvičení v terénu.

Otevřít přednášku (webový přehrávač)

Matematické přednášky

Hausdorffův zvěřinec ("Jaký objem má π-rozměrná koule?") [HAUS]

Možná vás už také zarazilo, že některé fraktály nejsou ani dvourozměrné, ani třírozměrné, ale něco mezi tím. Pojďme se podívat, co to znamená. Cestou potkáme různé zajímavé partie matematiky (jako třeba metrické prostory a teorii míry) a různá podivuhodná zvířátka: Cantorovo diskontinuum, von Kochovu vločku a Hilbertovu křivku.

Otevřít přednášku (webový přehrávač)

Kvantové počitání ("return 0.5*dead + 0.5*alive; ") [QC]

Stručný úvod do kvantového počítání. Kvantová superpozice stavů výpočtu a její kolaps při měření. Základní kvantové operace: negace, řízená negace, permutace, Hadamardovo hradlo, Tofolliho hradlo. Groverův algoritmus na hledání v odmocninovém čase. Kvantová Fourierova transformace a Shorův algoritmus pro faktorizaci.

Otevřít přednášku (webový přehrávač)

Programovací jazyky

Filosofie programovacích jazyků ("Your programming language sucks!") [YPLS]

Společné filosofování nad programovacími jazyky a zejména nad tím, proč jsou všechny na draka, jen některé víc než jiné. Proč lze mít všechno na světě, jenže ne najednou. Proč je někdy lepší nechat programátora, aby si sedl na své vlastní vidle. Proč jsou některé vlastnosti jazyků na první pohled geniální, zatímco jiné (až) na ten druhý. Proč je důležitá hustota kódu a Huffmanův princip. Proč je někdy důležitější evoluce než revoluce.

Otevřít přednášku (webový přehrávač)

Programátorské nástroje

Databáze zevnitř [DBMS]

Narozdíl od "normálních" jazyků se v SQL (a podobných) moc nepopisuje jak se má výsledek spočítat, jen kde se má sehnat. Co s tím tedy databáze bude dělat? Proč nebude mít 7mi hlavý JOIN hroznou složitost a proč možná ano. Co bude dělat když po ní budeme chtít transakce? Jak se dají ukládat data, aby byla bezpečně na disku a po ruce v RAMce?

Otevřít přednášku (webový přehrávač)

Nematfyzácké přednášky

Biologická evoluce ("Ale vždyť je to jen teorie!") [EVOL]

Evoluční teorie je asi jedním z největších převratů v lidském náhledu na svět. Jak se na takovou věc vůbec přišlo, proč to tak dlouho trvalo a proč si myslíme, že je to pravda? Jak si to vše alespoň trochu představit? Mnoho nečekaných překvapení, informatické a fyzikální souvislosti. Proč jsou stromy vysoké, jak souvisí pohlavní rozmnožování s počítačovou bezpečností, co má evoluce společného s Windows a co s halting problémem?

Otevřít přednášku (webový přehrávač)

Hornictví [MINING]

Základní přehled toho, jak se vyhledávají, těží a upravují suroviny.

Otevřít přednášku (webový přehrávač)