SUBJECT

Title

Discrete mathematics 2

Type of instruction

lecture + practical

Level

bachelor

Faculty

Faculty of Informatics

Part of degree program

Credits

3+3

Recommended in

Semester 2

Typically offered in

Spring semester

Course description

Graphs: examples, path, cycle. Isomorphic graphs, subgraphs, complement of a subgraph.
Eulerian path, Hamilton-cycle. Labeled graphs, Kruskal’s algorithm. Directed graphs, strongly connected graphs, directed trees and their applications. Planar graphs, the theorem of Kuratowski , Euler’s theorem.
Groups, subgroup, normal subgroup, factorgroup the homomorphism theorem. Cyclic groups, permutation groups. Ring, subring, ideal, factorring, the homomorphism theorem.
Polynomials, the ring of polynomials, Euclidean rings, Euclidian algorithm. Finite fields, factorization of polynomials, rational functions. the theorem of Gauss. Polynomials with several indeterminants.
Information, bit, entropy. Compression, optimal character coding, other coding types and their applications. Error correcting codes, code distance, linear codes, MDS codes, Reed-Solomon code and it decoding.
Algorithms in general, simulation. Turing machines, the equivalence of their versions. RAM computer, Neumann-type computers, heir equivalence with Turing machines. Other models.
Languages, decidability, computable and partially computable functions. Some undecidable problems. Nondeterministic Turing machines, the NP problem class.

Readings

Recommended literature: