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 | 1 | 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 |
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:
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
Other requirements
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
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.