SubjectsSubjects(version: 837)
Course, academic year 2018/2019
   Login via CAS
Discrete Mathematics - NMIN105
Title in English: Diskrétní matematika
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech
Teaching methods: full-time
Guarantor: prof. RNDr. Jaroslav Nešetřil, DrSc.
Mgr. Martin Mareš, Ph.D.
Class: M Bc. FM
M Bc. FM > Povinné
M Bc. FM > 1. ročník
M Bc. MMIB > Povinné
M Bc. MMIB > 1. ročník
M Bc. OM
M Bc. OM > Povinné
M Bc. OM > 1. ročník
Classification: Informatics > Discrete Mathematics
Mathematics > Discrete Mathematics
Incompatibility : NDMA005
Interchangeability : NDMA005
Annotation -
Last update: G_M (16.05.2012)
Basic course in discrete mathematics for bachelor's program Mathematics. Elements of set theory (sets, relations), introduction to combinatorics and graph theory.
Course completion requirements - Czech
Last update: doc. RNDr. Jiří Fiala, Ph.D. (17.09.2018)

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.

Povaha kontroly studia předmětu vylučuje opakování této kontroly, tedy zápočtu.

Literature -
Last update: 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)

Requirements to the exam - Czech
Last update: doc. RNDr. Jiří Fiala, Ph.D. (17.09.2018)

Zkouška je ústní. Požadavky u ústní zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce.

Syllabus -
Last update: 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.

Charles University | Information system of Charles University |