470-2301/01 – Discrete Mathematics (DIM)

Gurantor departmentDepartment of Applied MathematicsCredits6
Subject guarantordoc. Mgr. Petr Kovář, Ph.D.Subject version guarantordoc. Mgr. Petr Kovář, Ph.D.
Study levelundergraduate or graduate
Study languageCzech
Year of introduction2010/2011Year of cancellation
Intended for the facultiesFEIIntended for study typesBachelor
Instruction secured by
LoginNameTuitorTeacher giving lectures
KOV16 doc. Mgr. Petr Kovář, Ph.D.
KOV74 Mgr. Tereza Kovářová, Ph.D.
KUB59 RNDr. Michael Kubesa, Ph.D.
RAI0011 Ing. Tom Raiman
ZAV0063 Ing. Jakub Závada
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined Credit and Examination 10+10

Subject aims expressed by acquired skills and competences

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.

Teaching methods

Lectures
Individual consultations
Tutorials
Project work

Summary

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.

Compulsory literature:

J.Matoušek, J.Nešetřil. Invitation to Discrete Mathematics, Oxford University Press, ISBN 0-19-850208-7.

Recommended literature:

K.H.Rosen, Discrete Mathematics and Its Applications - 6th ed., McGraw-Hill, New York NY, (2007), ISBN-10 0-07-288008-2.

Way of continuous check of knowledge in the course of semester

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.

E-learning

Další požadavky na studenta

No additional requirements are imposed on the student.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: Part I - Introduction to discrete mathematics. The scope and goals of Discrete mathematics. Sets, elements, k-combinations, k-permutations, related formulas. Discrete probability: tossing coins, random choice, shuffling cards. Probability space and random event. Integers and mathematical induction, the concept of proofs. Proving the formulas for numbers of subsets, k-combinations, k-permutations. Formal foundations of dicscrete math: relations, mappings, equivalence relations, partial orders. Algorithmic aspects: practical implementation of sets and relations. Generating all possible subsets k-combinations, and k-permutations. Part II - Introduction to graph theory Graphs and relations. Subgraphs, isomorphism, degrees, implementation. Directed graphs. Graph connectivity, algorithms for searching. Higher degrees of connectivity, edge-connectivity. Eulerian graphs and their applications. Distance in graphs, Dijkstra's algorithm, graph metric and its enumeration. Trees and their characterizations, rooted trees, tree isomorphism. Spanning trees, MST problem. Basic algorithms for MST. Planar embeddings of graphs, Euler's formula and its applications. Graph coloring, bipartite graphs, recognition. Network flows: formulation and application to real life problems. Ford-Fulkerson's algorithm for maximum flow. Further applications to matching and system of representatives. Exercises: Following the course content. Project: Each student will prepare one project which contains a part concerning Discrete mathematics and a part concernig Graph Theory.

Conditions for subject completion

Full-time form (validity from: 2013/2014 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (100) 51
        Exercises evaluation Credit 30 (30) 10
                Projekt DIM Project 10  0
                Zápočtová písemka Written test 20  0
        Examination Examination 70  21
Mandatory attendence parzicipation: participation at all exercises is obligatory, 2 apologies are accepted participation at all lectures is expected

Show history
Combined form (validity from: 2013/2014 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (100) 51
        Exercises evaluation Credit 30 (30) 10
                Projekt DIM Project 10  0
                Zápočtová písemka Written test 20  0
        Examination Examination 70  21
Mandatory attendence parzicipation: participation at all exercises is obligatory, absence of 20% can be excused participation at all lectures is expected

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2019/2020 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2019/2020 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2019/2020 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2019/2020 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2019/2020 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2019/2020 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2019/2020 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2019/2020 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2019/2020 (B0714A060010) Telecommunication technology P Czech Ostrava 2 Optional study plan
2019/2020 (B0714A060010) Telecommunication technology K Czech Ostrava 2 Optional study plan
2018/2019 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2018/2019 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2018/2019 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2018/2019 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2018/2019 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2018/2019 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2018/2019 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2018/2019 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2017/2018 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2016/2017 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2015/2016 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2014/2015 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2013/2014 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2012/2013 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2012/2013 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2012/2013 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2012/2013 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2012/2013 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2012/2013 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2012/2013 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2012/2013 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2011/2012 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2011/2012 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2011/2012 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2011/2012 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2011/2012 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2011/2012 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2011/2012 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2011/2012 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2010/2011 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2010/2011 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2010/2011 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2010/2011 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2010/2011 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2010/2011 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2010/2011 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2010/2011 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2010/2011 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2010/2011 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2010/2011 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2010/2011 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner
V - ECTS - bc. 2014/2015 Full-time Czech Optional 401 - Study Office stu. block
V - ECTS - bc. 2013/2014 Full-time Czech Optional 401 - Study Office stu. block
V - ECTS - bc. 2012/2013 Full-time Czech Optional 401 - Study Office stu. block