# 456-0533/01 – Discrete Mathematics (DIM)

 Gurantor department Department of Computer Science Credits 6 Subject guarantor RNDr. Michael Kubesa, Ph.D. Subject version guarantor RNDr. Michael Kubesa, Ph.D. Study level undergraduate or graduate Requirement Compulsory Year 2 Semester winter Study language Czech Year of introduction 2003/2004 Year of cancellation 2006/2007 Intended for the faculties FEI Intended for study types Bachelor
Instruction secured by
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
Part-time 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.

### 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

Part-time form (validity from: 1960/1961 Summer semester)
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.Zaměření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