Main page | Study Branches/Specializations | Groups of Courses | All Courses | Roles                Instructions

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.

BI-VAK.21 Selected Applications of Combinatorics Extent of teaching: 2R
Instructor: 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 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

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 a Gu?nter M. ZIEGLER. Proofs from the book. 4. vyd. Berlin: Springer, 2010. ISBN 978-3-642-00855-9. BERLEKAMP, Elwyn R., John H. CONWAY a 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 a 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 a Clifford STEIN. Introduction to Algorithms. 3. vyd. Cambridge: The MIT Press, 2009. ISBN 978-0-262-03384-8. MAREŠ, Martin a Tomáš VALLA. Průvodce labyrintem algoritmů. V Praze: CZ.NIC, 2017. ISBN: 978-80-88168-22-5. MATOUŠEK, Jiří. Lineární programování: Úvod pro informatiky [online]. Praha: ITI, 2006. Dostupné z: https://iti.mff.cuni.cz/series/2006/311.pdf. MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. 4., upr. a dopl. vyd. V Praze: Karolinum, 2009. ISBN 978-80-246-1740-4. STEWART, Ian. Jak rozkrájet dort a další matematické záhady. Praha: 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).

Výukové materiály budou dostupné na https://courses.fit.cvut.cz/BI-VAK.21

The course is also part of the following Study plans:
Study Plan Study Branch/Specialization Role Recommended semester
BI-SPOL.2015 Unspecified Branch/Specialisation of Study V Není
BI-WSI-PG.2015 Web and Software Engineering V Není
BI-WSI-WI.2015 Web and Software Engineering V Není
BI-WSI-SI.2015 Web and Software Engineering V Není
BI-ISM.2015 Information Systems and Management V Není
BI-ZI.2018 Knowledge Engineering V Není
BI-PI.2015 Computer engineering V Není
BI-TI.2015 Computer Science V Není
BI-BIT.2015 Computer Security and Information technology V Není
BI-SPOL.21 Unspecified Branch/Specialisation of Study V Není
BI-PI.21 Computer Engineering 2021 (in Czech) V Není
BI-PG.21 Computer Graphics 2021 (in Czech) V Není
BI-MI.21 Business Informatics 2021 (In Czech) V Není
BI-IB.21 Information Security 2021 (in Czech) V Není
BI-PS.21 Computer Networks and Internet 2021 (in Czech) V Není
BI-PV.21 Computer Systems and Virtualization 2021 (in Czech) V Není
BI-SI.21 Software Engineering 2021 (in Czech) V Není
BI-TI.21 Computer Science 2021 (in Czech) V Není
BI-UI.21 Artificial Intelligence 2021 (in Czech) V Není
BI-WI.21 Web Engineering 2021 (in Czech) V Není


Page updated 28. 3. 2024, semester: Z/2023-4, L/2019-20, L/2022-3, Z/2019-20, Z/2022-3, L/2020-1, L/2023-4, Z/2020-1, Z,L/2021-2, Send comments to the content presented here to Administrator of study plans Design and implementation: J. Novák, I. Halaška