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

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.

2.

Numerical problems

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.

3.

Graph problems

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.

4.

Geometry and graphing

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.

7.

Slicing a cake

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.

9.

Online algorithms

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.

2.

Numerical problems

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.

3.

Graph problems

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.

4.

Geometry and graphing

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.

7.

Slicing a cake

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.

9.

Online algorithms

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,

2006.

Available from: https://iti.mff.cuni.cz/series/2006/311.pdf.

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).

https://courses.fit.cvut.cz/BIE-VAK.21

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr BIE-TI.2015_ORIGINAL Computer Science (Bachelor, in English) V Není BIE-TI.2015 Computer Science (Bachelor, in English) V Není BIE-WSI-SI.2015 Software Engineering (Bachelor, in English) V Není BIE-BIT.2015 Computer Security and Information technology (Bachelor, in English) V Není BIE-PI.21 Computer Engineering 2021 V Není BIE-PV.21 Computer Systems and Virtualization 2021 V Není BIE-PS.21 Computer Networks and Internet 2021 V Není BIE-TI.21 Computer Science 2021 V Není BIE-SI.21 Software Engineering 2021 V Není BIE-IB.21 Information Security 2021 (Bachelor in English) V Není