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

Login | Name | Tuitor | Teacher 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 study | Way of compl. | Extent |

Full-time | Credit and Examination | 2+2 |

Combined | Credit and Examination | 2+2 |

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

Lectures

Individual consultations

Tutorials

Project work

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.

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.

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

Subject has no prerequisities.

Subject has no co-requisities.

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.

Task name | Type of task | Max. 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 |

Show history

Academic year | Programme | Field of study | Spec. | Form | Study language | Tut. centre | Year | W | S | Type 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 |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|