Course detail

Methods of Discrete Mathematics

FSI-SDMAcad. year: 2023/2024

The subject Methods of discrete mathematics gets students acquainted with basic areas of set theory, discrete mathematics, and applied algebra. The first area is formed by relations between sets and on sets with a stress on partially ordered sets. The next area covers Axiom of Choice and cardinal and ordinal numbers. After that, lattice theory is discussed with the main interest focused on the theory of Bolean algebras. Then the algebraic theory of automata and formal languages follows. The last area is an introduction to the coding theory. Thus, all the three areas represent theoretical fundamentals of informatics. With respect to the expansion of using computers in all branches of engineering, the acquired knowledge is necessary for graduates in mathematical engineering.

Language of instruction

Czech

Number of ECTS credits

6

Mode of study

Not applicable.

Entry knowledge

Only the basic knowledge of the set theory is supposed that students acquired in high schools.

Rules for evaluation and completion of the course

The course unit credit is awarded on condition of having attended the seminars actively and passed a written test. The exam has a written and an oral part. The written part tests student's ability to deal with various problems using the knowledge and skills acquired in the course. In the oral part, the student has ro prove that he or she has mastered the related theory.


The attendance at seminars is required and will be checked regularly by the teacher supervising a seminar. If a student misses a seminar due to excused absence, he or she will receive problems to work on at home and catch up with the lessons missed.

Aims

The course aims to acquaint the students with some usual methods of discrete mathematics used in various applications, especially in computer science for construction and process description of computers and for data transmission. The students will get a proof that, beside the continuous mathematics, also discrete mathematics is a basic discipline whose knowledge is a necessary condition for a successful creative work of an engineer.


The students will learn about the fundamentals of ordered sets, lattices and Boolean algebras. They will learn to minimize Boolean functions and realize them by logic circuits. They will also get acquainted with the most usual types of automata and their properties, with regular languages and with the problem of determinism. Finally, thay will also get an image of the basic problems connected with coding and decoding of messages..

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

N.L.Biggs, Discrete Mathematics, Oxford Univ. Press, 1999. (EN)
M.Piff, Discrete Mathematics, Cambridge Univ. Press, 1991. (EN)
A.D.Polimeni and H.J.Straight, Foundations of Discrete Mathematics, Brooks/Cole Publ. Comp., Pacific Grove, California, 1990. (EN)
D.R.Hankerson at al.: Coding Theory and Cryptography, Marcel Dekker, Inc., New York -Basel, 2000. (EN)
Steven Roman, Lattices and Ordered Sets, Springer, 2008. (EN)

Recommended reading

F. Preparata, R. Yeh: Úvod do teórie diskrétnych matematických štruktúr, Alfa, Bratislava, 1982.
M. Demlová, V. Koubek: Algebraická teorie automatů, SNTL, Praha, 1990.
J. Kopka: Svazy a Booleovy algebry, Univerzita J.E.Purkyně v Ústí nad Labem, 1991.
M.Novotný, S algebrou od jazyka ke gramatice a zpět, Academia, Praha, 1988.

Classification of course in study plans

  • Programme B-MAI-P Bachelor's, 2. year of study, winter semester, compulsory

Type of course unit

 

Lecture

26 hours, optionally

Teacher / Lecturer

Syllabus

1. Relations between sets and on sets
2. Tolerances, equivalences, preorders and orders
3. Ordered sets
4. Axiom of choice and equivalent statements
5. Ordinal and cardinal numbers
6. Lattices, irreducibility, ideals and filters
7. Boolean lattices and functions, applications
8. Complete lattices, closure operators
9. Galois connections, Dedekind-MacNeille completion
10.Formal languages
11.Finite automata
12.Grammars
13.Selfcorrecting codes

Exercise

26 hours, compulsory

Teacher / Lecturer

Syllabus

1. Relations between sets and on sets
2. Tolerances, equivalences, preorders and orders
3. Ordered sets
4. Axiom of choice and equivalent statements
5. Ordinal and cardinal numbers
6. Lattices, irreducibility, ideals and filters
7. Boolean lattices and functions, applications
8. Complete lattices, closure operators
9. Galois connections, Dedekind-MacNeille completion
10.Formal languages
11.Finite automata
12.Grammars
13.Selfcorrecting codes