SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Discrete Mathematics - NMIN105
Title: Diskrétní matematika
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Additional information: https://kam.mff.cuni.cz/~tancer/DiskretkaM/prednaska.html
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
M Bc. MMIB > Povinné
M Bc. MMIB > 1. ročník
M Bc. MMIT
M Bc. MMIT > Povinné
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
Is interchangeable with: 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. Martin Tancer, Ph.D. (02.10.2023)

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.

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

Requirements to the exam - Czech
Last update: doc. RNDr. Martin Tancer, Ph.D. (02.10.2023)

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

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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html