|
||
|
Basic course in discrete mathematics for bachelor's program Mathematics. Elements of
set theory (sets, relations), introduction to combinatorics and graph
theory.
Last update: G_M (16.05.2012)
|
|
||
|
Pro zápočet je třeba získat 100 bodů z alespoň 150 možných udělovaných průběžně za písemné testy, řešení domácích úloh a další aktivity.
Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani zadání náhradních domácích úloh.
V důvodných případech (dlouhodobá nemoc, pobyt v zahraničí, apod.) může cvičící stanovit individuální podmínky na udělení zápočtu.
Zápočet je podmínkou pro konání zkoušky. Last update: Tancer Martin, doc. RNDr., Ph.D. (02.10.2023)
|
|
||
|
Jiří Matoušek, Jaroslav Nešetřil: Invitation to Discrete Mathematics; Oxford University Press; second edition(December 15, 2008) Last update: Kynčl Jan, doc. Mgr., Ph.D. (04.02.2018)
|
|
||
|
Zkouška je písemná s možností ústního dozkoušení. (V případně mimořádných okolností může přednášející rozhodnout o změně formátu zkoušky na zkoušku zcela písemnou, zcela ústní nebo distanční.) Požadavky u zkoušky odpovídají tomu co bude probráno na přednášce, včetně schopnosti uplatnit probranou teorii při řešení příkladů. Last update: Tancer Martin, doc. RNDr., Ph.D. (02.10.2023)
|
|
||
|
Notion of a set (Cantor), language of set theory, formula. Describe a set by enumeration or as a set of elements of a given property. Basic set operations (including power set and sums) and their properties.
Cartesian product, (binary) relations, composition of relations. Functions, functions one-to-one, onto, bijections. Properties of relations (reflexivity, symmetry, ...). The equivalence relation on a set, the decomposition of a set, the correspondene, examples.
Combinatorial counting. Number of mappings (injective mappings) from n-element to m-element set, number of subsets of an n-element set. Variations, permutations, combinations. Binomial coefficients, binomial theorem. The Inclusion and Exclusion Principle. Asymptotic estimates of factorials and binomial coefficients.
Graphs: definition, basic terminology, graph isomorphism. Vertex degree, the handshaking lemma, graph score. Paths in a graph, connectivity, components. Graph metric, derived notions.
Trees: their characterization and properties, the number of trees on a given set. Tree isomorphism, tree encoding. Spanning tree, minimum spanning tree algorithms.
Partial order, linear order, the greatest/smallest, maximal/minimal element, chain/antichain, supremum/infimum, examples. The existence of a minimal element and the linear extension theorem for finite sets. Isomorphism of sets with respect to relations. Representation of a partial order by inclusion. Good ordering, induction principle for natural numbers.
Euler trails. Euler subgraphs and their description using vector spaces (space of cycles and cuts).
Planar graphs. Plane drawing of a graph. Euler formula and its consequences. Coloring of a planar graph by five colors.
Bonus topics:
Ramsey theorem for graphs, Ramsey multicolored theorem. Lower bound on Ramsey numbers. Last update: Kynčl Jan, doc. Mgr., Ph.D. (02.02.2018)
|