Games have long served as benchmarks and marked milestones of progress in artificial intelligence (AI). This course teaches you fundamental formalisms, solution concepts and algorithms. We show how to solve both perfect and imperfect information games, and you will understand the deep connections and application of reinforcement learning to game theory. At the end of the course, you will implement algorithms to optimally solve (i.e. converge to Nash Equilibria) in small interesting games - notably small poker variants.

Ukážeme si několik (často docela překvapivých) aplikací lineárně algebraických metod v kombinatorice a teorii grafů. Jeden vzorek na ochutnání: Dokážete popsat všechny grafy, které mají tu vlastnost, že každé dva různé vrcholy mají <br /> právě jednoho společného souseda?

Přednáška volně navazuje na první část a probírá pokročilejší techniky optimalizace kódu (generování kódu, scheduling, optimalizaci smyček atd.). Témata jde upravit podle zájmu účastníků.

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.

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)

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.

The Complex Networks Applications seminar covers selected modern topics in complex networks. The principle of the seminar is to introduce several topics and let the students work on them. We first give a short introduction to the topic and present several topics from which students can choose. The topics include both theoretical and programming problems.

Cílem semináře je dát dohromady studenty a vyučující, které zajímá, nebo by mohla zajímat teorii kooperativní 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.

The history of Forcing in bounded arithmetic and proof complexity goes back to 1985 paper of Paris and Wilkie. Subsequently, Ajtai's 1988 lower bound for bounded depth Frege was originally obtained by a forcing argument and is still considered as one of the most important ones in the area. These results motivated further research into forcing in the context of bounded arithmetic. This semester, we will be covering Forcing with random variables in Proof Complexity (Krajíček 2011). In this setting, the constructed models are Boolean-valued and their behaviour is parametrized by random variables computed by some class of functions of fixed computational complexity.

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 semestr se plánujeme zaměřit na Steinerovy systémy a bloková schémata

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován tzv. zjemnělé složitosti (fine-grained complexity). Zjemnělá složitost je oblast, která vznikla a pozoruhodně se rozvinula během posledních patnácti let. Snaží se odpovědět na otázku, proč nejlepší známé algoritmy například pro hledání nejdelší společné podposloupnosti mají kvadratickou časovou složitost a pro jiné problémy mají všechny známé algoritmy zase složitost kubickou. Dává to do souvislosti s exponenciálními algoritmy pro řešení splnitelnosti (SAT).

The basic course in extremal graph theory, introducing the fundamental concepts (extremal function, stability), constructions (Turán's graph, algebraic constructions), and techniques used to show that sufficiently dense graphs must contain the specified configurations. We focus on giving an overview of the foundational results on the edge-density extremal function when various natural types of graphs (cliques, cycles, graphs of bounded degeneracy, ...) are forbidden, using this as an opportunity to introduce several more advanced methods that are generally useful (dependent random choice, regularity lemma, the method of flag algebras, ...) not just in the extremal combinatorics.

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.