# 457-0519/01 – Discrete Mathematics (DIM)

 Gurantor department Department of Applied Mathematics Credits 6 Subject guarantor RNDr. Michael Kubesa, Ph.D. Subject version guarantor RNDr. Michael Kubesa, Ph.D. Study level undergraduate or graduate Study language Czech Year of introduction 2003/2004 Year of cancellation 2009/2010 Intended for the faculties FEI Intended for study types Bachelor
Instruction secured by
CER365 doc. Ing. Martin Čermák, Ph.D.
HOR33 doc. Ing. David Horák, Ph.D.
KAB002 Ing. Pavla Hrušková, Ph.D.
KOV16 doc. Mgr. Petr Kovář, Ph.D.
KUB59 RNDr. Michael Kubesa, Ph.D.
KUP055 Ing. Tomáš Kupka
VLA04 Ing. Oldřich Vlach, Ph.D.
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 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

Průběžná kontrola studia: Semestrální písemky. Každý týden v semestru (s výjimkou prvního týdne) se na cvičení bude psát krátká zápočtová písemka (10-11 písemek). K vyřešení bude třeba čas zhruba od 2 do 10 minut. Během písemek není možné používat literaturu, ani zápisky. Za každou písemku můžete získat 0/1/2 body - rozuměj NE/TÉMĚŘ SPRÁVNĚ/ZCELA SPRÁVNĚ. Na konci vezme cvičící každému body z "nejlepších" osmi písemek a jejich součet vynásobí koeficientem 1,25. To je celkový počet bodů za semestrální písemky (maximum je 20 bodů). Témata písemek budou vždy vyvěšena na stránkách diskrétní matematiky, minimálně týden před písemkou. Zkouška. Ke zkoušce můžete jít, pokud máte nárok na zápočet. Hlavní součástí zkoušky je písemná práce zhruba na 75 minut. Na písemné zkoušce můžete získat až 60 bodů. Během zkoušky můžete používat také jedinou stranu A4 rukou psaných poznámek. Na tomto "zlegalizovaném taháku" mohou být definice, věty, vztahy. ALE NE ŘEŠENÉ PŘÍKLADY!!! Podmínky udělení zápočtu: Získat během semestru alespoň 10 bodů a samostatný referát musí být PŘIJAT.

### 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. Combinations with repetition. Discrete probability: tossing coins, random choice, shuffling cards. Probability space and event. Integers and math induction, math proof. Proving the numbers of subsets, combinations, permutations. 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. Algorithms of Jarnik and Boruvka. Planar embeddings of graphs, Euler's formula and its applications. Graph colouring, bipartite graphs, recognition. Network flows: formulation and applications to practical problems. Ford-Fulkerson's algorithm for maximal flow. Applications to matching and representatives. Implementation of graphs in computers, weighted graphs, implementation of rooted trees and of planar graphs. Exercises: Following the course content.

### Conditions for subject completion

Combined form (validity from: 1960/1961 Summer semester)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (100) 51
Examination Examination 70  0
Exercises evaluation Credit 30 (30) 10
Zápočtová písemka Written test 20  0
Projekt Project 10  0
Mandatory attendence parzicipation:

Show history

### Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2009/2010 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2009/2010 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2008/2009 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2007/2008 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2646) Information Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (1103R031) Computational Mathematics P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (1103R031) Computational Mathematics K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology K Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R059) Mobile Technology P Czech Ostrava 2 Compulsory study plan
2006/2007 (B2647) Information and Communication Technology (2612R059) Mobile Technology K Czech Ostrava 2 Compulsory study plan
2005/2006 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2005/2006 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 1 Compulsory study plan
2005/2006 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2005/2006 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2004/2005 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 1 Compulsory study plan
2004/2005 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2004/2005 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 1 Compulsory study plan
2003/2004 (B2646) Information Technology (1103R021) Computation Mathematics P Czech Ostrava 2 Compulsory study plan
2003/2004 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 1 Compulsory study plan
2003/2004 (B2646) Information Technology (1103R021) Computation Mathematics K Czech Ostrava 2 Compulsory study plan
2003/2004 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 1 Compulsory study plan

### Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner