Matematics++, spring semester 2021/2022

Ida Kantorová, Robert Šámal, Martin Tancer

Topic

Modern computer science often uses mathematical tools that reach beyond the scope of standard mathematical courses in the bachelor program. This course will present a (somewhat condensed) introduction to several fields of mathematics that proved especially useful in computer science and in discrete mathematics. Computer science applications will be shown as well. This course is suitable for master's or PhD students of computer science. The students are assumed to have prior knowledge in the extent of mandatory courses of the bachelor program in computer science. For illustration, see topics of past lectures.

This year we will focus on measure theory -- as a background for probability. Also on geometry in high dimensions and a bit of functional analysis.

Prerequisites

Interest in mathematics, knowledge roughly in the extend of cs bachalor degree at MFF UK. We will mostly build upon analysis, probability and linear algebra.

Extent

Two hours of lectures and two hours of tutorials weekly (2/2). Credit and exam.

Tutorials

A substantial part of the class will consist of independent solving of homework problems. Credit will be given for solving a sufficient number of problems. The exercises will be led by Denys Bulavka and Petr Chmel. Here is the exercise webpage.

Exam

Will be oral, containing both theory and problems. For the arrangement of time, email the lecturers. (Ideally all of them, the one with similar time preferences as you will reply.) Note: each of us will examine you from anything that was being taught, not just his/her third!

Literature

[KMS] I. Kantor, J. Matoušek, R. Šámal: Mathematics++ (should be available in the library)
[W] T.B. Ward: Functional analysis lecture notes

Covered material

(For illustration, see the web page of last edition of this class.)

Date	Topic	Literature
21.2.	[MT] Motivation for measure. Definition of the outer measure. The outer measure of an interval. Subadditivity. Additivity fails: Vitali set. Measurable sets, properties of measurable sets. Definition of a sigma algebra and a measure. Lebesgue measure. Lebesgue measure is a measure (= checking countable additivity).	[KMS], 1.1
28.2.	[MT] Poznámka o Lebesguově míře v $d$-rozměrném prostoru. Borelovské množiny, jejich měřitelnost. Příklad: Vitaliho množina je měřitelná v $\mathbb R$ ale ne v $\mathbb R^2$. Úplná míra, popis Lebesgueovy míry jako úplné míry co obsahuje všechny borelovské množiny. Měřitelná funkce. Pro funkci $X \to Y$ je potřeba podmínku ověřit jen pro množiny, které generují sigma-algebru v Y. Měřitelné funkce $\mathbb R \to \mathbb R$ a operace s nimi. Jednoduché funkce. Aproximace zdola měřitelných funkcí pomocí jednoduchých. Definice Lebesguova integrálu pro jednouché funkce a pak obecně.	[KMS], 1.1, 1.2
7. 3.	[MT] Základní vlastnosti Lebesguova integrálu (bez dk., ale často plynou přímo z definice). Fatouovo lemma (částečný důkaz). Léviho věta o monotonní konvergenci. Linearita integrálu. Lebesgueova věta o integrovatelné majorantě (Dominated convergence theorem). Součinová míra a Fubiniho věta. Základní pojmy z teorie pravděpodobnosti: Pravděpodobnostní prostor (jako měřitelný prostor), jev, náhodná veličina, střední hodnota.	[KMS], 1.2, 1.3
14.3.	[MT] Náhodná veličina s rozdělením s danou hustotou. Standardní normální rozdělení. Dva výpočty: $\int_{-\infty}^{\infty} e^{-x^2/2} = \sqrt{2\pi}$ (neformálně přes mezikruží, formálněji pomocí substituce). Vlastnosti standardního normálního rozdělení: neformální srovnání s binomickým rozdělením, centrální limitní věta (jedna z mnoha možných verzí). Gaussova míra, n-rozměrná Gaussova míra a její pravděpodobnostní interpretace. Generování náhodného bodu na sféře (náznak).	[KMS], 2.3
21.3.	[IK] Vícedimenzionální geometrie. Motivace: problémy z jiných oblastí, kde se uplatní. Zvláštní jevy v mnoha dimenzích: n-dimenzionální krychle má mnohokrát větší objem, než jí vepsaná koule, náhodné jednotkové vektory jsou pravděpodobně téměř kolmé. Brunnova nerovnost, Brunnova-Minkowského nerovnost, důkaz Brunnovy nerovnosti z Brunn-Minkowského nerovnosti.	[KMS], 2.1, 2.2
28.3.	[IK] Izoperimetrický problém, euklidovská izoperimetrie (důkaz z BM nerovnosti). 1-dimenzionální BM nerovnost, bezdimezionální BM nerovnost. Prékopova--Leindlerova nerovnost.	[KMS], 2.2
4.4.	[IK] Koncentrace míry na sféře (bez důkazu). Příklady prostorů s koncentrací míry (sféra s euklidovskou metrikou a uniformní mírou, n-dimenzionální reálný prostor s euklidovskou metrikou a gaussovskou mírou, hyperkrychle s Hammingovou metrikou, expandery). Lévyho lemma o koncentraci Lipschitzovských funkcí (na sféře). Odhad mediánu 1-Lipschitzovských funkcí na sféře pomocí střední hodnoty. Gromovova věta o pasu sféry. Koncentrace míry v n-dimenzionálním reálném prostoru s gaussovskou mírou (s důkazem).	[KMS], 2.4
11.4.	[IK] Johnson--Lindenstraussovo zploš?ovací lemma. Lemma o náhodné gaussovské projekci. Koncentrace délky gaussovského vektoru. Důkaz lemmatu o náhodné gaussovské projekci a J.--L. lemmatu. Odhady pravděpodobnosti, že f(x) je větší, než t, podle Bernsteina: Markovova nerovnost, Čebyševova nerovnost, odhad pomocí exponenciální funkce se dvěma příklady: Černovova nerovnost a koncentrace délky gaussovského vektoru.	[KMS], 2.4
25.4.	[RS] Funkcionální analýza -- definice Banachova prostoru. Úplnost. Příklady. Lineární operátory -- tři ekvivalentní definice.
2.5.	[RS] Banachova věta o kontrakci. Norma lineárního operátoru. Příklady Banachových prostorů a měření zobrazení mezi nimi. Hilbertův prostor -- Banachův prostor se skalárním součinem.
9.5.	[RS] Hilbertův prostor -- promítání na konvexní množiny, promítání na podprostory. Hahn-Banachova věta: důkaz základního lemmatu a několik důsledků (opěrný funkcionál pro kouli, rozlišování bod, ...).
16.5.	[RS] Dvě použití Frechet-Rieszovy reprezentace: Definice adjungovaného operátoru Důkaz Radon-Nikodymovy, resp. Lebesguovy věty o dekompozici. Spektrum lineárního operátoru, rozdíl oproti konečné dimenzi. Spektrum nekonečného regulárního stromu.