This course is a continuation of NMAI062 Algebra 1, with a focus on foundational results in group and ring theory. We first discuss the isomorphism theorems and their application. The second chapter concerns results on field extensions, algebraic/transcendental numbers, and the classification of finite fields. We then apply the developed theory to discuss algorithmic problems over polynomial rings (fast multiplication/division/factorization). If any time is left, we talk about other algebraic structures of importance in computer science (such as lattices and Boolean algebras).

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

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.

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

Zajímá vás, jak férově rozdělovat zisky, moc nebo náklady v koalicích, trzích či AI systémech? Přijďte na intenzivní kurz Cooperative Game Theory vedený prof. Michelem Grabischem (ERA Chair, AGATE). Kurz propojuje pevné teoretické základy s praktickými aplikacemi v oblasti hlasovacích her, Shapleyho hodnoty, vyjednávání a metod SHAP v umělé inteligenci. Výuka bude probíhat dvakrát týdně v termínu od 17. února do 31. března. Ideální pro studenty a výzkumníky se zájmem o teorii her, ekonomii, operace research a strojové učení.

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 period of 3 years). This year we intend to cover: Discrete Fourier transform, Representation theory, and Polynomials in many variables

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

Navazujici kurz pro NOPT021 - algoritmy moderní teorie her

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.

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.

In-depth development of the theory of graph minors, building upon the foundation established in NDMI059 Graph minors and tree decompositions. The focus of the lecture will be on the celebrated Minor Structure Theorem, one of the most fundamental results in the structural graph theory. We will explore the most important ideas that go into the proof of this theorem and showcase some of its applications. We will also cover recent developments towards Hadwiger's conjecture.

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

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.

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