A systematic introduction to the graph coloring theory, including some of the recent developments.

• Critical graphs (their density and application in testing the chromatic number of graphs on surfaces, potential method)
• Discharging method (and an outline of the proof of the Four Color Theorem).
• Variants of graph coloring (fractional, circular, ...), connection to nowhere-zero flows.
• Applications of probabilistic and counting methods.

Special graph classes, in this course mainly defined as intersection graphs of geometrical objects in the plane, are intensively studied both for their applied motivation and interesting algorithmic properties. We will see interval graphs, chordal graphs, comparability graphs, and others, their structural characterizations, recognition algorithms as well as algorithms for basic optimization problems that run in polynomial time on graphs from these classes.

Přednáška se zabývá pokročilými algoritmy na nejkratší cesty, toky v sítích, minimální kostry a další grafové problémy. Také potkáme několik datových struktur pro dynamickou reprezentaci grafů. Předpokládá se znalost v rozsahu bakalářských Algoritmů a datových struktur 1+2.

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.

An advanced course in graph theory and combinatorics. Includes topics from:

• structural graph theory (properties of graph classes defined by forbidden minors, detailed introduction to treewidth from the structural perspective, Erdős-Pósa theorem, Nash-Williams theorem on spanning trees, VC dimension)
• extremal graph theory and additive combinatorics (regularity lemma and its applications)
• polynomial method (in list coloring and graph regularization)

Druhá část přednášky o překladačích. Zaměříme se na optimalizaci smyček, inter-procedurální optimalizaci, a generování kódu.

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.

Cílem semináře je otestovat možnosti a hranice práce s ChatGPT a do příštích let položit základy pro výuku "plnokrevné" přednášky na toto téma. Studenti mají příležitost se kromě osvojení tohoto nástroje aktivně podílet na obsahu semináře a směru, kterým se bude (především ve své druhé polovině) odvíjet.

Z důvodu povahy předmětu je kapacita omezena.

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.

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.

Imagine a true statement about finite objects, how can a formal proof of such a statement look? Can it be short? This semester's topic will be about basic propositional proof systems studied in proof complexity (namely Resolution, Frege system, and some algebraic and geometric systems). During the seminars, which will be as interactive as possible, we will work on various exercises which will guide us through the feel of proving something in those proof systems. We will also focus on studying classic lower bounds for those systems. In the later parts of the semester, the students will be free to pick a topic to present, but active participation will be enough to obtain the credit (zápočet). No prior knowledge is assumed, everything is to be explained on the seminar.

Algorithms for different types of flows and cuts, as well as their interrelations, have proven to be invaluable tools for addressing a wide range of graph-related problems (e.g., graph drawing, VLSI design, routing in networks, to name a few). In this course, we will

• describe the main results concerning (multicommodity) flows and cuts in graphs, and on the way we will also

• illustrate various techniques employed in the development of approximation algorithms, such as LP relaxation, probabilistic methods, geometric approaches, SDP relaxation and a greedy approach.

Cyklus přednášek o pokročilých datových strukturách, navazující na magisterské Datové struktury 1 a 2. Předmět je možné zapisovat opakovaně, každý rok děláme něco jiného.

Tento rok se zaměříme na Ramseyovu teorii. Přednáška nema prerekvizity.

Parametrizovaná výpočetní složitost analyzuje dobu běhu algoritmů podrobněji než klasická teorie složitosti: namísto vyjádření doby běhu pouze jako funkce velikosti vstupu se bere v úvahu závislost na vhodném dalším parametru vstupu. Cílem je, aby případný rychlý (exponenciální) růst doby běhu závisel jen na parametru, zatímco závislost na velikosti vstupu je nízká (polynomiální). Kromě hlubšího teoretického pochopení složitosti problému to může vést i k efektivním a praktickým algoritmům, je-li zvolený parametr pro obvyklé vstupy malý.

Prohlédněte si trailer.