Course detail

Basics of Discrete Mathematics

FSI-9MDMAcad. year: 2024/2025

The subject makes students acquainted with some basic methods of discrete mathematics employed in (not only technical) practice. The content can be divided into four areas. The first of them is logic, especially the propositional and predicate logic, and its applications in computer science. The second area is formed by the graph theory with an emphasis on the graph algorithms utilized for solving optimization problems of different kinds. The next area is algebra and its applications in the theory of formal languages and automata. The last area is represented by the fundamentals of coding theory, especially the linear codes are discussed.

Language of instruction

Czech

Mode of study

Not applicable.

Guarantor

prof. RNDr. Josef Šlapal, CSc.

Department

Institute of Mathematics (ÚM)

Entry knowledge

Basic knowledge of mathematics on bachelor level are required.

Rules for evaluation and completion of the course

Students are to pass an exam consisting of the written and oral parts. During the exam, their knowledge of the concepts introduced and of the basic propertief of these concepts will be assessed. Also their ability to use theoretic results for solving concrete problems will be evaluated.
Since the subject is taught in the form of a lecture, which is not compulsory for student, the attendance will not be checked.

Aims

The goal of the subject is to make students acquainted with principal methods of discrete mathematics employed in technical applications. The knowledge of these methods will help students to understand their specializations more deeply and to utilize computers and programming when solving given problems.
Students will learn basic facts about logic, graph theory, automata theory, formal languages and coding theory. This will be useful for research in their specializations and for affective use of computers because they will better understand the principles computers work on.

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Mike Piff: Discrete Mathematics. Cambridge University Press 1991 (EN)
Norman l. Biggs: Discrete Mathematics. Oxford Science Publications 1999 (EN)

Recommended reading

D.R Hankerson & al.: Coding Theory and Cryptography. Marcel Dekker, Inc. 2000. (EN)
F.P. Preparata, R.T. Yeh: Úvod do teórie diskrétnych matematických štruktúr. Alfa-Bratislava 1982 (CS)
J. Nešetřil: Teorie grafů. SNTL, Praha 1979 (CS)
Steven Roman: Lattices and ordered sets, Springer 2008. (EN)
S.V. Jablonskij_: Úvod do diskrétnej matematiky. Alfa-Bratislava 1984 (CS)

Classification of course in study plans

  • Programme D-IME-P Doctoral 1 year of study, winter semester, recommended course
  • Programme D-IME-K Doctoral 1 year of study, winter semester, recommended course

Type of course unit

 

Lecture

20 hod., optionally

Teacher / Lecturer

prof. RNDr. Josef Šlapal, CSc.

Syllabus

1. Propositional logic
2. Axiomatization of propositional logic
3. Predicate logic
4. Axiomatization of predicate logic
5. Directed and non-directed graphs
6. Graph algorithms
6. Nets and their applications
8. Groupoids and groups
9. Rings and fields
10.Formal languages
11.Automata
12.Introduction to coding theory
13.Linear codes