Hlavní stránka
| Seznam
oborů/specializací | Seznam
všech skupin předmětů | Seznam
všech předmětů | Seznam rolí
Návod
Předmět je základní jednotka výuky,
jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí
a dovedností, potřebnou pro zvládnutí studijního oboru/specializace.
Za věcný obsah předmětu zodpovídá garant předmětu.
Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu
rozsah kontaktní výuky. Například rozsah = 2+2 značí,
že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny
cvičení týdně.
Na závěr semestru musí vyučující provést vyhodnocení, nakolik si
ten který student osvojil poznatky a dovednosti, kterých měl během
výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou
určuje atribut způsob zakončení. U předmětu lze definovat, že
předmět je zakončen pouze zápočtem(Z),
klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo
zápočtem a zkouškou(Z,ZK).
Náročnost úspěšného absolvování předmětu je vyjádřena ECTS
kreditními body.
Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje
vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku.
Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L).
Za organizační zajištění výuky zodpovídá přiřazená katedra, která
zejména vytvoří časový rozvrh předmětu a zajistí pro předmět
vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují
zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu
je popsána pomocí různých popisných textů(anotace, týdenní osnova,
literatura, apod.)
$DODATEK_POPIS
BIE-VAK.21 |
Selected Combinatorics Applications |
Rozsah kontaktní výuky: |
2R |
Vyučující: |
Knop D., Schierreich Š., Suchý O., Valla T. |
Způsob zakončení: |
Z |
Zodpovědná katedra: |
18101 |
ECTS Kredity: |
3 |
Semestr: |
L |
Anotace:
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.
Osnovy přednášek:
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.
Osnovy cvičení:
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.
Literatura:
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.
Požadavky:
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).
Předmět je zahrnut do těchto studijních plánů:
Stránka vytvořena
29. 4. 2024, semestry: Z/2023-4, Z/2019-20, L/2021-2, L/2020-1, L/2022-3, Z/2021-2, L/2019-20, Z/2022-3, Z/2020-1, L/2023-4, Z/2024-5, připomínky
k informační náplni zasílejte správci
studijních plánů |
Návrh a
realizace:
J. Novák,
I. Halaška |