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.

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.

We will cover some classical topics of extremal theory of finite set systems: theorems of Sperner, Erdos-Ko-Rado, Frankl-Wilson. Applications will include the Littlewood-Offord theorem, Strong and weak saturation of hypergraphs and synchronization of DFA's. If time permits, we will proceed with the Alon's Combinatorial Nullstellensatz and applications thereof.

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.

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

• structural graph theory (monotone, hereditary and minor-closed classes, treewidth and structural properties of low-treewidth decompositions),
• extremal graph theory (Szemerédi's regularity lemma, Erdős-Stone-Simonovits theorem, Kővári-Sós-Turán theorem, pseudorandom graphs and Chung-Graham-Wilson theorem, graph limits),
• extremal and Ramsey-type combinatorics (Hales-Jewett theorem and its density version, Gallai-Witt theorem, Roth's theorem).

• Naučíme se používat LEAN k psaní ověřitelných důkazů matematických tvrzení.
• Příklady z lineární algebry, diskrétní matematiky, teorie čísel a analýzy.
• Bude se konat v angličtině, pokud o něj budou mít zájem zahraniční studenti.

Přemýšleli jste někdy, co vlastně znamenají titulky jako „Hackeři se nabourali do XY“? Přemýšleli jste někdy, jak by útočník mohl proměnit nevinný segfault ve vašem programu v plnou kontrolu nad vaším počítačem? Nebo získat citlivá data z databáze vaší aplikace pouze pomocí jediného vyhledávacího pole? V tomto kurzu se budeme zabývat některými z mnoha bezpečnostních nástrah, se kterými se člověk nakonec vždy setká při tvorbě čehokoli počítačového. Naučíte se základy moderní počítačové bezpečnosti, jak útočníci myslí a jak využívat tohoto smýšlení k psaní lepších a bezpečnějších programů a aplikací.

Přednáška se zabýva pokročilými častmi překladače vřetně generování kódi, alokace registrů, schedulingu a optimalizace smyček.

Tento semestr budu několik týdnů (3-4 přednášky) mimo Prahu. Proto provedeme progrm částečně referativní formou, kde prodiskutujeme zajímavé projekty související s překladem.

We will try to 1) Use off-the-shelf AI chatbots to build tools useful for math research, 2) Use those tools to solve open problems in mathematics, 3) Profit!

Relativně pravidelné setkávání o vedení cvičení pro cvičící studenty (sejdeme se asi 5-6x za semestr). Budeme si povídat mimo jiné o výukových metodách, komunikaci, tvorbě bezpečného prostředí a dalších pedagogických tématech (s praktickými ukázkami).

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.

Vyučující vyberou přístupné otevřené problémy z algoritmických oblastí jako jsou návrh algoritmů a jejich analýza, datové struktury, teorie složitosti a další. Studenti se pod vedením vyučujících snaží tyto problémy během semestru řešit. Klade se důraz na týmovou spolupráci a rozvoj dovedností v řešení problémů. Vhodné pro studenty bakalářského i magisterského studia.

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é skeče — často pouze logaritmické ve velikosti dat — které lze však stále použít jako aproximaci původních dat.

🔍Probereme základní problémy (např. hledání nejčastějších prvků, aproximace distribucí) a pak se zaměříme na pokročilejší skeče pro geometrické nebo grafové problémy. Dokážeme si i dolní odhady na jejich přestnost a někdy též probereme praktičnost jejich použití. Nakonec prodiskutujeme odolnost skečů vůči útokům adaptivních protivníků⚔️.

Přednáška bude z části navazovat na Pravděpodobností algoritmy (NDMI025), ale splnění NDMI025 není prerekvizitou, potřebnou látku zopakujeme.

🔭 This seminar explores topics in probability and algorithms.

📐 The topics are selected on the fly. Here's a general plan for this semester: We want to dig into the relations of probability with high-dimensional spaces and with some topics related to neural nets (stochastic gradient descent, adversarial attacks, ...).

📚 A basic understanding of probability is assumed (e.g. Probability 1). Fondness of probability is highly recommended. Check out notes from the past seminar (different topics, similar aesthetics). https://bayesbitsbrains.github.io/

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.

Looking up a new 'thing' in a table of 'known things' is a common task in science. If a molecule is synthesised, we want to know which substance it is or if we actually created something new. But as molecules usually do not answer to the question "Hi, have we met before?" a more systematic approach is required. One option is to structurally represent the molecule by a graph and run a graph isomorphism test against all molecule graphs in a database. But how do those test algorithms actually work? In this course we study three types of algorithms: Specialised efficient algorithms for restricted graph classes, algorithms that are fast in most cases but take exponential time in the worst case, and Babai's famous quasi-polynomial algorithm, which has the lowest known worst-case runtime, but is quite slow in practical application. For a nice introduction to the topic, see: Martin Grohe and Pascal Schweitzer. 2020. The graph isomorphism problem. Commun. ACM 63, 11 (November 2020), 128–134. https://doi.org/10.1145/3372123

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.

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován editační vzdálenosti. Editační vzdálenost je míra podobnosti řetězců. Má různé využití v bioinformatice, zpracování textu apod. V této přednášce se zaměříme na různé aspekty editační vzdálenosti: od algoritmů a dolních mezí po sketching a samoopravné kódy pro editační vzdálenost. Představíme její různé algoritmické a složitostní otázky.

Seminář věnující se využití současných AI modelů (primárně chatbotů) v pracovním procesu. Seminář se bude věnovat hlavně následujícím dvěma problematikám: Využití AI v programování a při práci s informacemi.

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.