470-2301/01 – Discrete Mathematics (DIM)

The goals of this subject are to introduce basic terms and methods of discrete mathematics and graph theory and to teach students to use them to formulate real life problems using mathematical terminology and to solve these related practical problems. The students should learn to - comprehend and generalize given definitions, - distinguish which theoretical approach is suitable for a particular practical problem, - classify given objects based on given properties and summarize the results, - summarize each chapter. In class students should practice to - state a real life problem in the terms of Discrete mathematics or Graph theory - apply theoretical approaches in solving real life problem, choose proper methods, - choose and compare various methods of solution and pick the most suitable, - verify the validity of each partical method, - reuse the same theoretical approach in similar problems.

In this course the students learn the basic terms and concepts and basic constructions used in Discrete mathematics, especially in Combinatorics and Graph theory. The word "discrete" refers to the opposite of "continuous". In this course we deal almost exclusively with finite sets and finite objects.

K.H.Rosen, Discrete Mathematics and Its Applications - 6th ed., McGraw-Hill, New York NY, (2007), ISBN-10 0-07-288008-2. P. Kovář: Lecture slides online http://homel.vsb.cz/~kov16/files/dim_kapitoly_all_en.pdf P. Kovář, T. Kovářová: Solved exercises http://homel.vsb.cz/~kov16/files/dim_solved_exercises.pdf

Quizes during the semester. Each week (starting with the third week) there will be short quizes at the beginning of each class (10 quizes, 2 or 3 points each). No books or notes are alowed to be used to write the quiz. At the end of the semester eight best quizes will be counted, four of each type. Maximum is 20 points. Topics of the quizes can be foud on the course webpage (webpage of the lecturer). The exercises on the quiz will be similar but not identical. Project. Topis will be available in the second half of the semester. A regular project consists of several problem, half in Discrete mathematics, half in Graph theory. The problems will be graded 0-2 or 0-3 point depending on difficulty, the total is 10 points. There can be bonus projects available, each with two more difficult problems (Discrete mathematics +Graph theory), every student can work on the bonus project instead of the regular project. The problems will be graded 0/3/5 points, in the case of exceptionaly good solution 10 points. Exam. A student can come for the exam oly if he passed "zápočet". Main part of the exam is a written test for approximately 75 minutes. During the written part students can use one page A4 of hand-written notes. This legalized "ceat-sheet" may contain definitions, formulas, thorems, but NO SOLVED EXAMPLES! Necessary conditions to pass "zápočet": Get at least 10 point on quizes and project. The project has to be "accepted". A project can be accepted if it fulfils all formal requirement, i.e. title page, ID, etc. A project can be accepted even if it gains no points.