This time, the Úmluva will happen virtually. On 2024-02-05, a list of courses will appear here, together with a voting form, where you can express your interest and time preferences. On 2024-02-16 09:00, we will tally the votes and schedule the classes. The time-space coordinates of classes will appear in the SIS.
SIS code | Name | Lecturer / instructor | Scheduled | Note |
---|---|---|---|---|
NDMI018 |
Approximation and Online Algorithms
Aproximační a online algoritmy |
J. Sgall / T. A. Vu | Will take place on Mon, Tue, or Fri. | |
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. |
||||
NSWI134 |
Code optimization in production compilers
Optimalizace kódu produkčních překladačů |
Jan Hubicka | ||
Course is focusing on advanced algorithms of code optimization used in production quality compilers. The topics can be adjusted according to interests of participants. Usually we focus on the intermediate languages, Single static assignment form, scalar optimization and loop optimization. |
||||
NDMI096 |
Complex network analysis
Analýza komplexních sítí |
David Hartman / David Hartman | Skills from course Graphs and networks (NDMI110) are reviewed, but not necessary for the course. | |
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. |
||||
NOPT057 |
Cooperative game theory
Kooperativní teorie her |
M. Černý, M. Loebl | Fr 13:00 | |
NOPT060 |
Cooperative game theory seminar
Seminář z kooperativní teorie her |
M. Černý, D. Ryzák | Tu 9:00 | |
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. |
||||
NTIN067 |
Data structures 2
Datové struktury 2 |
M. Mareš | ||
This course extends NTIN066 Data Structures I. It covers more advanced techniques of design and analysis of data structures: deterministic representation of static sets, data structures for integers, basic data structures for graphs, dynamic cache-oblivious search trees, dynamization, persistence, succinct data structures, computation in stream model. |
||||
NDMI107 |
Discrete Mathematics of Paul Erdős
Diskrétní matematika Pála Erdőse |
V. Chvátal | ||
At a leisurely pace, we shall cover a subset (chosen by the students) of the following topics: Proof of Bertrand's postulate. Sperner's theorem and the Erdős-Ko-Rado theorem. Turán numbers. Property B and hypergraph colouring. Extremal graph theory. Hamilton cycles. The Friendship Theorem, strongly regular graphs, and Moore graphs of diameter two. Chromatic number of graphs and the probabilistic method. Van der Waerden's theorem and van der Waerden numbers. The Erdős-Szekeres and the Sylvester-Gallai theorems. Delta-systems and Deza's proof of an Erdős-Lovász conjecture. The De Bruijn-Erdős theorem. The Erdős-Rényi random graphs and their evolution. Ramsey's theorem and Ramsey numbers. |
||||
NDMI035 |
Geometric Representations of Graphs II
Geometrické reprezentace grafů II |
V. Jelínek | ||
This is a follow-up course to GRG 1 from the winter semester, but is also accessible to students who didn't attend GRG 1. Topics cover various algorithmic and structural aspects of graph drawings and geometric intersection representations. |
||||
NDMI088 |
Graph algorithms 2
Grafové algoritmy 2 |
M. Mareš | ||
Algorithms for planar embedding in linear time, further results on minimum spanning trees (algorithm with expected linear complexity, Pettie's optimal algorithm), decomposition-based techniques and some data structures. |
||||
NDMI085 |
Graph minor theory
Teorie grafových minorů |
Z. Dvořák | ||
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. |
||||
NDMI059 |
Graph minors and tree decompositions
Grafové minory a stromové rozklady |
J. Fiala | ||
A course in structural graph theory. The first part focuses on graph minors, the second on various graph decompositions. Covers sections 1-4 of the lecture notes. |
||||
NDMI110 |
Graphs and networks
Grafy a sítě |
David Hartman / David Hartman | ||
The course is an introductory course in complex networks. This topic combines areas of graph theory and combinatorics with the analysis of real-world complex systems. The topics of the course cover some problems from the area of structural graph theory, selected areas of spectral theory, random graphs and the problem of obtaining decompositions of vertices. Lectures are supplemented by seminars having partly theoretical and partly computational forms. |
||||
NTIN113 |
Integer Programming and Computational Social Choice
Celočíselné programování a výpočetní aspekty voleb |
M. Koutecký | ||
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. |
||||
NDMI100 |
Introduction to cryptography
Úvod do kryptografie |
M. Mareš | ||
An introductory course ranging from theoretical foundations to commonly used cryptographical protocols (e.g., TLS and DNSSEC) and practical computer security. |
||||
NTIN100 |
Introduction to Information Transmission and Processing
Základy přenosu a zpracování informace |
P. Gregor / T. A. Vu | We start from the second week. | |
Essentials of information theory, error-correcting codes and communication complexity. |
||||
NMAI071 |
Math++
Matematika++ |
Martin Tancer / Tomáš Hons, Petr Chmel | The lecture will be merged into Topological methods in Combinatorics (NDMI014). Preferably, set up your time preferences for NDMI014 and also enroll for NDMI014. For any queries regarding the merging, contact the lecturer, please. | |
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.) |
||||
NOPT034 |
Mathematical Programming and Polyhedral Combinatorics
Matematické programování a polyedrální kombinatorika |
Petr Kolman, Hans Raj Tiwary | ||
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. |
||||
NDMI065 |
Matroid Theory
Teorie matroidů |
O. Pangrác / M. Černý | lecture preferably on Monday or Friday | |
Introduction to matroid theory. It covers basic notions, representability, graphic matroids, and some algorithmic aspects of matroids. |
||||
NOPT017 |
Multiobjective Optimization
Vícekriteriální optimalizace |
M. Hladík | ||
NTIN082 |
Nonuniform Computational Models
Neuniformní výpočetní modely |
P. Hrubeš | ||
The class expands on the basic course on computational complexity (NTIN063). It introduces various types of boolean circuits, branching programs and arithmetic circuits. We will show relationship between various circuit classes and traditional complexity classes. We will also show several classical lower bound results on circuit size. The class is intended for advanced master's students and doctoral students. |
||||
NMIN365 |
Sage
Sage |
R. Šámal, R. Hušek | ||
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! |
||||
NDMI056 |
Selected chapter in combinatorics 2
Vybrané kapitoly z kombinatoriky 2 |
Jan Hubička, Jarlosav Nešetřil | ||
We will cover symmetries of graphs and structures in the context of extremal problems and their structural extension properties. Particularly we will discuss the extension property for partial automorphisms (EPPA). Course will be self-contained and no previous knowledge of the area is necessary. |
||||
NTIN086 |
Selected topics in computational complexity II
Vybrané kapitoly z výpočetní složitosti II |
J. Tkadlec / J. Tkadlec | ||
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. |
||||
NPRG015
no voting |
Seminar for preparing students for contests in programming
Praktikum řešení programátorských úloh |
Z. Dvořák | Fr 14:00 SU2 | Every other week, starting on February 23. |
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. |
||||
NDMI093 |
Seminar on algorithms and data structures
Seminář z algoritmů a datových struktur |
M. Mareš | ||
Students present papers on new results in the field of algorithms and data structures. |
||||
NDMI052 |
Seminar on Combinatorial Problems
Problémový seminář z kombinatoriky |
P. Valtr, J. Kynčl | ||
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. |
||||
NDMI022 |
Seminar on Combinatorics
Kombinatorický seminář |
Martin Loebl, Irena Penev, Martin Tancer | ||
Seminar on Combinatorics is a seminar for students interested in combinatorics. The assumed knowledge corresponds to the first year lectures (Discrete Mathematics and Combinatorics and Graphs I). Therefore, the seminar is especially suitable for students of the 2nd year of Bachelor's studies and older but interested students of the first year are also very welcome. Main contents of the seminar is that the students present papers on Combinatorics. This means that you will learn something new as well as you will train how to explain some ideas to other students. Seminar covers several subtopics in Combinatrics including (but not limited to): Combinatorial structures, graph theory, combinatorial geometry, probability, game theory, etc. Participants of the seminar are invited to the Spring school of Combinatorics. |
||||
NTIN114 |
Streaming algorithms for Big Data
Proudové algoritmy pro velká data |
P. Veselý | ||
Streaming algorithms are designed for analyzing data in a single pass with a small memory footprint. We will cover sampling and sketching techniques to summarize large amounts of data into a concise summary, typically logarithmic in the data size, that can be used to approximately answer certain queries. While we will primarily focus on the design and formal analysis of streaming algorithms, we will also prove lower bounds on their accuracy and occasionally discuss practical considerations when applying these algorithms. |
||||
NMAI066
no voting |
Topological and Algebraic Methods
Topologické a algebraické metody |
A. Pultr | Please send e-mail to pultr@kam.mff.cuni.cz. | |
Partial order, special partial orders in computer science. DCPOs, domains. Continuous and algebraic posets. Introduction to topology. |
||||
NDMI014 |
Topological Methods in Combinatorics
Topologické metody v kombinatorice |
Martin Tancer / Tomáš Hons, Petr Chmel | The lecture Mathematics++ will be merged into this lecture | |
The aim of the lecture is to provide an introduction to topology and then focus on applications of topology to mostly combinatorial problems, e.g., providing a tight bound on chromatic number of so called Kneser graphs. The central tool for such applications is the Borsuk-Ulam theorem which will be thoroughly explained. This year the lecture will be merged with Mathematics++ which means that the introduction to topology will be slightly deeper. |