Logo ČVUT
Loading...
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2024/2025
Faculties | School elective courses | ECTS courses catalogue | Settings | Česká verze
Welcome page > Faculty of Information Technology > Department of Theoretical Computer Science > Selected Applications of Combinatorics

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
Course guarantor:
Michal Opler
Lecturer:
Tomáš Valla
Tutor:
Dušan Knop, Michal Opler, Jan Pokorný, Šimon Schierreich, Jiřina Scholtzová, Ondřej Suchý, Tomáš Valla
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 2024/2025:
Time-table is not available yet
Time-table for summer semester 2024/2025:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-12-05
Copyright © Jiří Kosek, 2010–2022 | Copyright © ČVUT, 2010–2022
Hosted by Výpočetní a informační centrum ČVUT
Send your questions and comments to HelpDesk ČVUT or to spravcekos@cvut.cz
For updated information see http://bilakniha.cvut.cz/en/predmet7025806.html