Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2022/2023

Selected Applications of Combinatorics

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
BI-VAK.21 Z 3 2R Czech
Lecturer:
Tomáš Valla (guarantor)
Tutor:
Tomáš Valla (guarantor), Václav Blažej, Dušan Knop, Michal Opler, Šimon Schierreich, Ondřej Suchý
Supervisor:
Department of Theoretical Computer Science
Synopsis:

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.

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

Syllabus of lectures:

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

Syllabus of tutorials:

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

Study Objective:

The aim of the course is to introduce students to a wide range of topics that theoretical computer science deals with, and to motivate him to study this field.

Study materials:

AIGNER, Martin a Gü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.

Note:
Further information:
https://ggoat.fit.cvut.cz/bi-vak/index.html
Time-table for winter semester 2022/2023:
Time-table is not available yet
Time-table for summer semester 2022/2023:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
roomT9:107
Knop D.
Opler M.

09:15–10:45
(parallel nr.101)
Dejvice
Posluchárna
Tue
Wed
Thu
Fri
The course is a part of the following study plans:
Data valid to 2023-01-28
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet7025806.html