456-0533/01 – Discrete Mathematics (DIM)

Gurantor departmentDepartment of Computer ScienceCredits6
Subject guarantorRNDr. Michael Kubesa, Ph.D.Subject version guarantorRNDr. Michael Kubesa, Ph.D.
Study levelundergraduate or graduateRequirementCompulsory
Year2Semesterwinter
Study languageCzech
Year of introduction2003/2004Year of cancellation2006/2007
Intended for the facultiesFEIIntended for study typesBachelor
Instruction secured by
LoginNameTuitorTeacher giving lectures
KOH053 Ing. Ondřej Kohut
KON422 Mgr. Lukáš Konečný
KOT06 Ing. Martin Kot, Ph.D.
KOV16 doc. Mgr. Petr Kovář, Ph.D.
KUB59 RNDr. Michael Kubesa, Ph.D.
SOM025 Mgr. Miroslav Sommer
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined Credit and Examination 2+2

Subject aims expressed by acquired skills and competences

The goals of this subject are to introduce basic terms and methods of discrete mathematics, and to teach students to use those for an exact formulation and for solving related applications and practical problems. The students should learn - 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 In class students should practice - state a real life problem in the terms of Discrete mathematics - apply theoretical approach for solving the problem, choose proper methods - choose between various approaches and pick the most suitable - reuse the approach for similar problems

Teaching methods

Lectures
Individual consultations
Tutorials
Project work

Summary

In this course the students learn the basic concepts of Set theory and basic constructions used in Discrete mathematics, especially in Combinatorics and Graphs 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. P. Hliněný. Online textbook for the course, 2005.

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

E-learning

Další požadavky na studenta

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: Part I -- Introduction to discrete math. The scope and goals of discrete math. Sets, elements, combinations, permutations, formulas for their numbers. Integers and math induction, math proof. Proving the numbers of subsets, combinations, permutations. Discrete probability: tossing coins, random choice, shuffling cards. Probability space and event. Formal foundations of dicscrete math: relations, mapping, equivalence, ordering. Algorithmic aspects: practical implementation of sets and relations. Generating subsets and permutations. Part II -- Introduction to graph theory Graphs and relations. Subgraphs, isomorphism, degrees, implementation. Directed graphs. Graph connectivity, algorithms for searching. Multiple connectivity, edge-connectivity. Eulerian graphs. Distance in graphs, Dijkstra's algorithm, graph metric and its computation. Trees and their characterizations, tree isomorphism, rooted trees. Spanning trees, MST problem. Matroid of independent sets. Vector matroid, the greedy algorithm. Aplications to the MST problem, algorithms of Jarnik and Boruvka. Planar embeddings of graphs, Euler's formula. Graph colouring, bipartite graphs. Implementation of graphs in computers, weighted graphs, implementation of rooted trees and of planar graphs. Exercises: Following the course content. Projects: Preparing 1 or 2 written essays on selected topics from a list given during the course.

Conditions for subject completion

Combined form (validity from: 1960/1961 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (145) 51
        Examination Examination 100  0
        Exercises evaluation Credit 45  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2005/2006 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2004/2005 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Compulsory study plan
2003/2004 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2003/2004 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner