The goal of the course freely follows the course Graphs and Networks (NDMI110). We will discuss more extended topics in complex networks in the areas of centralities, random networks, community structure, and more.

We cover selected techniques of design and analysis of approximation and online algorithms. We assume knowledge on the level of the Bc. course NDMI084 Introduction to approximation and randomized algorithms. Recommended for Mgr. students.

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 algorithms for important IP and IP-related problems, 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.

Přednáška navazuje na přednášku NTIN066 Datové struktury I. Bude věnována pokročilejším technikám návrhu a analýzy datových struktur: deterministická reprezentace statických množin, datové struktury pro celočíselné universum, základní grafové datové struktury, dynamické cache-oblivious vyhledávací stromy, dynamizace a persistence, úsporné datové struktury, výpočty v proudovém modelu.

V klidném tempu probereme podmnožinu (vybranou studentkami a studenty) následujících témat: Důkaz Bertrandova postulátu. Spernerova věta a Erdős-Ko-Rado věta. Turánova čísla. Vlastnost B a chromatické číslo hypergrafů. Extrémální teorie grafů. Hamiltonovy cykly. Věta o přátelství, silně pravidelné grafy a Mooreovy grafy o průměru dva. Chromatické číslo grafů a pravděpodobnostní metoda. Van der Waerdenova věta a van der Waerdenova čísla. Erdős-Szekeres a Sylvester-Gallaiovy věty. Delta-systémy a Dezův důkaz Erdős-Lovászovy domněnky. De Bruijn-Erdősova věta. Rényiho náhodné grafy a jejich vývoj. Ramseyova věta a Ramseyova čísla.

Přednáška navazuje na GRG 1 ze zimního semestru, ale je vhodná i pro studenty, kteří GRG 1 nenavštěvovali. Témata pokrývají rozmanité algoritmické a strukturální výsledky týkající se grafových nakreslení a geometrických průnikových reprezentací.

Algoritmy pro kreslení grafu do roviny v lineárním čase, další výsledky o minimálních kostrách (algoritmus s průměrně lineární složitostí, Pettieho optimální algoritmus), techniky založené na dekompozici a pár datových struktur.

Kurs ze strukturální terorie grafů. V první části je zaměřen na grafové minory, ve druhé na různé rozklady grafů Je pokryt kapitolami 1-4 ze skript k přednášce.

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

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 the period of 3 years). This year we intend to cover topology. Coincidentally, this year, we also run a lecture Topological Methods in Combinatorics (NDMI014) with a partially overlapping contents (and the period of 2 years). Thus we have decided to merge the lectures. If possible, vote for and enroll to NDMI014. (It is not a big difference but it will be easier to handle.)

Přednáška rozšiřuje základní přednášku o výpočetní složitosti (NTIN063). Seznamuje s různými druhy booleovských obvodů, branching programů, a aritmetických obvodů. Ukážeme vztahy mezi těmito obvody a základními složitostními třídami a klasické dolní odhady na velikost obvodů.

Přednáška je určena především studentům magisterského studia a doktorandům.

Přednáška se věnuje pokročilým metodám optimalizace kódu tak jak jsou implementovány v produkčních překladačích. Témata mohou být přizpůsobena zájmu posluchačů. Typicky diskutujeme mezijazyky, SSA formu, skalární optimalizaci a optimalizaci smyček.

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.

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.

Proudové (streaming) algoritmy jsou navrženy pro analýzu dat pouhým jedním průchodem s malou pamětí. V přednášce pokryjeme techniky vzorkování (sampling) a skečování, které slouží k sumarizaci velkých objemů dat do malé datové struktury, typicky logaritmické ve velikosti dat, kterou lze však stále použít jako aproximaci původních dat. Ačkoliv se primárně zaměříme na návrh a analýzu proudových algoritmů, dokážeme si i dolní odhady na jejich přestnost a někdy též probereme praktičnost jejich použití.

Do you want to use a computer to deal with math problems? Do you find Wolfram alpha limited to only basic problems? Do you prefer open source software? Do you prefer Python over "Mathematica language"? Come and learn to use Sage!

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

Cílem semináře je dát dohromady studenty a vyučující, kteří mají zájem o kooperativní teorii her. Slouží především jako platforma pro vznik nových témat a formulaci zajímavých problémů, které následně diskutujeme a řešíme. Seminář je směřovaný tím, co jeho účastníky baví a zajímá. Chceme vybudovat kolektiv a propojit mezi sebou lidi, kteří mohou spolupracovat i nad rámec samotného semináře. Studenti si mohou také prostřednictvím semináře vyzkoušet, co obnáší výzkum v matematice, otestovat své schopnosti a na základě této zkušenosti na seminář i navázat prostřednictvím bakalářské/magisterské práce.

Further in-depth treatment of the topics introduced in NDMI059 Graph minors and tree decompositions, focusing on giving an outline of the proof Minor Structure Theorem and showcasing some of its applications. We will also cover recent developments towards the Hadwiger's conjecture.

Introduction to matroid theory. It covers basic notions, representability, graphic matroids, and some algorithmic aspects of matroids.

Částečná uspořádání, speciální částečná uspořádání informatiky. DCPO, domény. Spojitá a algebraická uspořádání. Základy topologie pro informatiky.

Cílem přednášky je poskytnout krátký úvod do topologie a následně se zaměřit na aplikace topologických metod především v kombinatorice. Příkladem takové aplikace je určení chromatického čísla tzv. Kneserových grafů. Ústředním nástrojem bude Borsuk-Ulamova věta, která bude podrobně vysvětlena. Letos bude přednáška spojena s přednáškou Matematika++. V důsledku toho bude úvod do topologie o něco hlubší.

Probereme symetrie grafů a struktur v kontextu extémálních problémů a jejich rozšiřujících vlastností. Budeme se věnovat problému rozšiřování částečných automorfismů (EPPA).

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

In this semester, we will focus on Evolutionary graph theory -- the field which studies random processes that model how entities (such as opinions, viruses, or genetic mutations) propagate through network-structured populations. Along the way we introduce notions such as Markov chains or martingales and we answer questions such as "How long does it take until a randomly typing monkey types a word 'abracadabra'?" We assume basic knowledge of discrete mathematics and probability.

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

Základní kurs kryptografie od teoretických základů až po běžně používané protokoly (jako například TLS a DNSSEC) a praktickou počítačovou bezpečnost.