A course is the basic teaching unit, it's design as a medium for a student to acquire comprehensive knowledge and skills indispensable in the given field. A course guarantor is responsible for the factual content of the course.
For each course, there is a department responsible for the course organisation. A person responsible for timetabling for a given department sets a time schedule of teaching and for each class, s/he assigns an instructor and/or an examiner.
Expected time consumption of the course is expressed by a course attribute extent of teaching. For example, extent = 2 +2 indicates two teaching hours of lectures and two teaching hours of seminar (lab) per week.
At the end of each semester, the course instructor has to evaluate the extent to which a student has acquired the expected knowledge and skills. The type of this evaluation is indicated by the attribute completion. So, a course can be completed by just an assessment ('pouze zápočet'), by a graded assessment ('klasifikovaný zápočet'), or by just an examination ('pouze zkouška') or by an assessment and examination ('zápočet a zkouška') .
The difficulty of a given course is evaluated by the amount of ECTS credits.
The course is in session (cf. teaching is going on) during a semester. Each course is offered either in the winter ('zimní') or summer ('letní') semester of an academic year. Exceptionally, a course might be offered in both semesters.
The subject matter of a course is described in various texts.
| BIE-VAK.21 |
Selected Combinatorics Applications |
Extent of teaching: |
2R |
| Instructor: |
Knop D., Schierreich Š., Suchý O., Valla T. |
Completion: |
Z |
| Department: |
18101 |
Credits: |
3 |
Semester: |
L |
Annotation:
The course aims to introduce students in an accessible form to various branches of theoretical
computer science and combinatorics. In contrast to the basic courses, we approach the issue from
applications to theory. Together, we will first refresh the basic knowledge needed to design and
analyze algorithms and introduce some basic data structures. Furthermore, with the active
participation of students, we will focus on solving popular and easily formulated problems from
various areas of (not only theoretical) informatics. Areas from which we will select problems to be
solved will include, for example, graph theory, combinatorial and algorithmic game theory,
approximation algorithms, optimization and more. Students will also try to implement solutions to
the studied problems with a special focus on the effective use of existing tools.
Lecture syllabus:
| 1. | | Problems of cloakrooms and watermen |
Despite the problem of the locker room and the problem of watermen, we will appropriately
establish and further expand some selected knowledge from the basic BI-DML course. We
will continue to use this knowledge in the rest of the course. Evidence will also be an
important concept for the rest of the course, so we will show examples of some evidence
that looks seemingly correct but doesn't really work.
We will deal with interesting problems in discrete mathematics, such as the breakfast
problem, CSP, Sperner's lemma and its applications, the Hercules and Hydra problem and
the like.
We will imagine problems that can be solved using graph theory, but creating a graph model
may seem unintuitive for these problems. Examples of such a problem are vessel metering,
tunnel passage reconstruction and much more.
The aim of the lesson is to acquaint students with the basic problems of computational
geometry, which bring with them many problems in the form of working with real numbers.
We will show how similar problems can be solved and we will get acquainted with why it is
interesting to be able to draw a graph nicely.
| 5. | | Solving marital problems |
The stable marriage problem is a fundamental problem in pairing theory. The task is to find
among equally large groups of (heterosexual) men and women an assignment to marriage
that is as close as possible to their preferences, so no couple will tend to leave the marriage.
The mentioned problem has many generalizations, either in the form of a stable roommate
problem or in games dedicated to the formation of coalitions. L. S. Shapley and A. E. Roth
were even awarded the Nobel Prize for their work in this field.
| 6. | | One to two player games |
Let's look at simple combinatorial games such as Nim, Toads and Frogs, Tic-Tac-Toe. We will
generalize these simple games and show some selected features of more complex games,
such as chess, Shannon's number, Go, Game of Life, Poker.
During the lesson, the basic problems of the theory of fair division will be introduced. It
deals with the fair division of a farm between players and finds many applications in real
world problems. The issue will be illustrated by the example of the cake-cutting problem
| 8. | | Inaccurate solutions to difficult tasks |
Using the example of the secretary selection problem, we will show how to solve problems
that are considered algorithmically unsolvable under the assumption of the P! = NP
hypothesis for large instances. We will show how to find a solution for similar tasks that is
not the best possible, but in the worst case it differs from the best result by a previously
known constant factor. Another solution to similar unsolvable problems is to create
algorithms such as Monte-Carlo, Las Vegas and others.
For most of the introduced algorithms, we know the entire input at the beginning of the
calculation. In many pra ctical tasks, however, we receive input information gradually and we
must respond flexibly to changes or additional input information. During the lesson, we will
use the example of the sorting and secretary problem to show how such algorithms work,
how to design and use them. Last but not least, we will discuss whether there is an online
counterpart for each off-line algorithm, and explain what a competitive online algorithm
means.
| 10. | | Problems suitable for general solvers ? SAT |
To acquaint students with the problem of satisfiability and its variants. SAT is a prominent
problem of all informatics, which is, among other things, the basis of the whole complexity
theory. On the one hand, from a theoretical point of view, this is an unsolvable problem for
larger instances, but on the other hand, there are many very good optimized commercial
and open-source solvers that can calculate many tasks very quickly. Therefore, students will
practice how to reduce some computational problems to the problem of satisfiability and
thus obtain a relatively efficient algorithm without the need to devise and implement a complex algorithm. The student will also learn how reducibility is related to the problem
belonging to the NP complexity class.
| 11. | | Problems suitable for general solvers - LP and ILP |
To acquaint students with the theory of linear programming and its integer variant.
Furthermore, students will practice how to express some computational problems as (integer) linear programs. We will then solve the problems expressed in this way in some
freely available LP solver. The student will also learn how reducibility is related to the
problem belonging to the NP complexity class.
| 12. | | Alternative computational models |
In addition to the standard RAM computational model, calculations can be performed on
other computational models. A nice example can be, for example, comparator networks or a tile model. The aim of the lesson is therefore to present these calculation models and show
their (limited) power.
| 13. | | (reserve) Parallel algorithms |
Modern processors often have not only a single core, but multiple cores. Machines
consisting of many interconnected processors can also be used to perform more complex
calculations. We will introduce a parallel computational model PRAM and its variants. We
will try to solve some known problems significantly faster than sequential calculation, ie
typically in polylogarithmic and constant time.
Seminar syllabus:
| 1. | | Problems of hatcheck ladies and watermen |
| 2. | | Number problems |
| 3. | | Graph problems |
| 4. | | Geometry and graph drawing |
| 5. | | Solving stable marriages |
| 6. | | Games for one or two players |
| 7. | | Cake cutting |
| 8. | | Imprecise solving of intractable problems |
| 9. | | On-line algorithms |
| 10. | | Problems for general solvers - SAT |
| 11. | | Problems for general solvers - LP and ILP |
| 12. | | Alternative computational models |
| 13. | | Parallel algorithms |
Literature:
AIGNER, Martin and Günter M. ZIEGLER. Proofs from the book. 4th ed. Berlin: Springer, 2010. ISBN
978-3-642-00855-9.
BERLEKAMP, Elwyn R., John H. CONWAY and Richard K. GUY. Winning ways, for your mathematical
plays. New York: Academic Press, 1982. ISBN 978-0-120-91150-9.
BRANDT, Felix, Vincent CONITZER, Ulle ENDRISS, Jérôme LANG and Ariel D. PROCACCIA. Handbook of
computational social choice. New York: Cambridge University Press, 2016. ISBN 978-1-107-06043-2.
CORMEN, Thomas H., Charles E. LEISERSON, Ronald L. RIVEST and Clifford STEIN. Introduction to
Algorithms. 3rd ed. Cambridge: The MIT Press, 2009. ISBN 978-0-262-03384-8.
MAREŠ, Martin and Tomáš VALLA. Algorithm maze guide. In Prague: CZ.NIC, 2017. ISBN: 978-80-
88168-22-5.
MATOUSEK, Jiri. Linear Programming: An Introduction to Computer Science [online]. Praha: ITI,
MATOUŠEK, Jiří and Jaroslav NEŠETŘIL. Chapters in discrete mathematics. 4., ed. published in
Prague: Karolinum, 2009. ISBN 978-80-246-1740-4.
STEWART, Ian. How to slice a cake and other math mysteries. Prague: Argo, Dokořán, 2009. ISBN
978-80-7363-187-1.
Requirements:
We assume that the student masters the knowledge acquired in the subjects Discrete Mathematics
and Logic (BI-DML) and Programming and Algorithmization 1 (BI-PA1).
The course is also part of the following Study plans:
| Page updated
26. 4. 2024, semester: Z/2020-1, L/2021-2, L/2019-20, L/2022-3, Z/2019-20, L/2020-1, L/2023-4, Z/2022-3, Z/2021-2, Z/2023-4, Z/2024-5, Send comments to the content presented here to Administrator of study plans |
Design and implementation:
J. Novák,
I. Halaška |