Datasets containing sensitive personal information could serve as invaluable resources to policy-makers, public institutions, and companies. Yet, their analysis or release could jeopardize the privacy of individuals whose data is contained in such datasets. The focus of this course will be on the notion of differential privacy that, beyond strong academic success (2017 Goedel Prize), made it into the production of companies such as Google and Apple.

Přednáška na pomezí teorie a praxe o tom, jak implementovat algoritmy, aby byly rychlé na reálném hardwaru. Architektura počítačů, překladačů a operačních systémů z pohledu programátora. Přizpůsobení algoritmů vlastnostem stroje. Nebudeme se věnovat konkrétním frameworkům, nýbrž základním principům.

Tento kurz navazuje na předchozí předmět s názvem Základy nelineární optimalizace (NOPT018), který pojednává o teoretických formulacích problému nelineární optimalizace a jeho vlastnostech. V tomto kurzu jsou diskutovány různé třídy optimalizačních algoritmů s ohledem na jejich efektivitu, výpočetní složitost a několik dalších globálních vlastností. Předmět popisuje jak nepodmíněné, tak podmíněné optimalizační úlohy s nelineární doménou a/nebo funkcí. Mezi metody patří (kvazi)newtonovy metody, metody konjugovaných gradientů, metody vnitřních bodů, trust-region metody, atd.

Free continuation of the lecture NDMI059, now focused on algorithmic consequences (Courcelle's metatheorem, etc.).

This lecture will illustrate various surprising ways to combine the techniques from (mostly complex) analysis with the machinery of (ordinary and exponential) generating functions to solve (almost effortlessly!) some combinatorial counting problems that are too hard for conventional methods. We will assume no prior knowledge of complex analysis whatsoever. Some basic prior familiarity with generating functions is helpful but is not necessary.

Integer Programming is an optimization tool rich both in theory and applications. Computational Social Choice is a field of growing relevance which considers the computational aspects of elections, fair divison, opinion dynamics, etc. In this course, we will describe parameterized algorithms for important classes of IP, and show their applications to problems from computational social choice.

This is a very active area of research, and this course is at the bleeding edge of what is known, thus presenting fresh research opportunities.

Budou se přednášet vybraná témata z optimalizace tak, jak sou implementované v produkční překladači (zejména GCC a LLVM). Předmět nevyžaduje předchozí znalost oblasti.

Přehled tvorby Paula Erdőse, která položila základy moderní diskrétní matematiky. Pohodlným tempem probereme podmnožinu (určenou hlasováním studentů) následujících témat: Erdősův důkaz Bertrandova postulátu. Erdősův důkaz Turánovy věty. Hamiltonovské kružnice. Ramseyova věta a Ramseyova čísla. Delta-systémy a Dezův důkaz hypotézy Erdőse a Lovásze. Spernerova věta a Erdős-Ko-Rado věta. Van der Waerdenova věta a van der Waerdenova čísla. Extremální teorie grafů. Věta o přátelství, silně regulární grafy, a Mooreovy grafy průměru 2. The Erdős-Rényi náhodné grafy a jejich vývoj. (Přednášky budou založeny na knize https://www.megabooks.cz/p/17179094/discrete-mathematical-charms-of-paul-erdos .)

Předmět je úvodním kurzem v tématu komplexních sítí. Toto téma spojuje jednotlivé oblasti kombinatoriky a analýzy reálných komplexních systémů. Tématiky pokrývá jednak tradičnější oblasti teorie grafů, zasahuje do spektrální teorie, oblasti náhodných grafů a problematiky získávání dekompozic vrcholů. Přednášky jsou doplněny cvičením, která mají napůl formu teoretickou a výpočetní.

Přednáška navazje na Kombinatoriku NMAG403. Zde si ukážeme jinou konstrukci Steinerových systémů trojic a dokážeme, že dva ortogonální Latinské čtverce exitují pro každý řád n > 6. Podstatná část přednášky bude věnována teorii konečných projektivních prostorů, kde hlavním výsledkem bude důkaz, že pro dimenzi větší než 2 je řád konečného projektivního prostoru nutně mocnina prvočísla.

Kombinatorický seminář je seminář pro studenty se zájmem o kombinatoriku. Předpokládají se znalosti odpovídající základním přednáškám (Diskrétní mat., Komb. a grafy I), seminář je tedy vhodný pro studenty 2. ročníku bakalářského studia a starší (ale prváci se zájmem o věc jsou také vítáni).

Hlavní náplní semináře je četba a referování odborných článků účastníky semináře.

Přínos je tedy hned dvojí: dozvíte se něco nového pěkného a navíc si vyzkoušíte předávání znalostí ostatním (aneb jak zařídit, aby jim to bylo taky tak jasné, jako mě).

Tématicky seminář zasahuje do různorodých oblastí kombinatoriky: kombinatorické struktury a procesy, teorie grafů, kombinatorická geometrie, pravděpodobnost, teorie her, ...

Každoročně jsou účastníci semináře zváni na Jarní školu kombinatoriky.

This is a master-level course focusing on two topics in combinatorial optimization: i) structure of polytopes and the complexity of their description, ii) efficient methods for optimization over polytopes (and polyhedra).

In the first part of the lecture, we will cover basics of the theory of polytopes such as the Minkowski-Weyl theorem, face-lattice, 1-skeleton, etc.

In the second part we describe in detail the ellipsoid algorithm and the interior point methods (IPMs). It is worth mentioning that the framework of IPMs is a key ingredient of the recent algorithm for exact maximum flow in almost linear time.

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 contents of the lecture alters (with a period of 3 years). This year we intend to cover: Measure theory (including a little bit of continuous probability), higher-dimensional geometry, and functional analysis.

The language of the lecture will be Czech or English. (It will be English if there is at least one person in the audience who does not understand Czech.)

Training for programming competitions, especially International Collegiate Programming Contest (ICPC). Practice contests and tutorials on important techniques and problem types. Held once every two weeks for 3 hours.

Náhodnost umožňuje řešit některé úlohy, které jsou bez jejího použití neřešitelné nebo řešitelné méně efektivně. Probereme mírně pokročilé metody pro návrh a analýzu takových algoritmů a protokolů. Budeme se věnovat mj. náhodným procházkám v grafech, přibližnému počítání, algoritmům s proudy dat, PCP větě.

Předpokládá se znalost na úrovni předmětů NDMI084 Úvod do aproximačních a pravděpodobnostních algoritmů a NTIN022 Pravděpodobnostní techniky.

🔭 This (somewhat experimental) lecture explores how probability connects mathematical theory with our understanding of the world - from foundational ideas to practical modeling.

📐 We'll examine mathematical foundations like entropy and its various interpretations and applications, Dutch Book theorems, von Neumann-Morgenstern axioms, relationships with high-dimensional spaces, connections to machine learning, statistics, forecasting, Bayesian inference, and more.

🧭 Instead of focusing deeply on a particular topic, the lectures will explore various ideas that we find insightful, drawing inspiration from information theory, Bayesian statistics, and some LessWrong-inspired aesthetics of modeling and understanding the world through probability.

📚 A basic understanding of probability is assumed (e.g. Probability 1). Fondness of a probabilistic viewpoint is recommended. Some familiarity with related fields will help you get more from the lecture but it is not required.

Seminar v tomto semestru bude asi v cestine, poprve 21.2. The students will collaborate on solving open combinatorial problems, which are easily formulated and do not require deep background knowledge. We attempt to choose problems of medium difficulty.

Volné pokračování Semináře o TeXu ze zimního semestru. Budeme se věnovat různým rozšířením TeXu (pdfTeX, LuaTeX) a dalším nástrojům pro digitální sazbu dokumentů.

Referativní seminář o aktuálních výsledcích na poli algoritmů a datových struktur.

Známý též jako pizza seminář. Přijdtě si dát kus pizzy a poslechnout přednášku na aktuální téma z teoretické informatiky.

Přednáška nebude vyžadovat předchozí znalost oblasti.

💻 Hands-on Coding Seminar: This seminar focuses on creating educational videos about math, algorithms, and related topics using languages like Motion Canvas or the Python library Manim.

🎬 You will work on a video project, either individually or in a team. By the end of the semester, the goal is for you to have created something comparable to the Summer of Math Exposition videos.

Můžeme vyřesit více úloh, když dostaneme více času nebo prostoru? Dá se vyřešit splnitelnost SAT v prostoru n^{1/2} a čase n^2? Lze SAT vyřešit snáze, když víme, že každá formule má nejvýše jedno pravdivé ohodnocení? Jak může Alenka přesvědčit Boba, že kola a pepsi nechutnají stejně? Během této přednášky se podíváme na všechny tyto otázky a mnoho dalších. Přednáška seznámí posluchače s řadou základních konceptů výpočetní složitosti.

Základy teorie informace, samoopravných kódů a komunikační složitosti.