|
|
|
||
|
Last update: G_M (16.05.2012)
|
|
||
|
Last update: doc. RNDr. Vít Jelínek, Ph.D. (08.09.2022)
Zápočet je nutnou podmínkou účasti u zkoušky.
Zápočet bude udělen za zisk 100 bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, apod. Maximální možný počet bodů, které lze získat, je zhruba 150.
Povaha kontroly studia předmětu vylučuje opakování této kontroly, tedy zápočtu. |
|
||
|
Last update: doc. Mgr. Jan Kynčl, Ph.D. (04.02.2018)
Jiří Matoušek, Jaroslav Nešetřil: Invitation to Discrete Mathematics; Oxford University Press; second edition(December 15, 2008) |
|
||
|
Last update: doc. RNDr. Vít Jelínek, Ph.D. (08.09.2022)
Zkouška je písemná s možností ústního dozkoušení. Požadavky u zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce, včetně schopnosti uplatnit probranou teorii při řešení příkladů. |
|
||
|
Last update: doc. Mgr. Jan Kynčl, Ph.D. (02.02.2018)
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. |