Discrete Mathematics

• 39 hrs lectures
• 13 hrs exercises
• 13 hrs pc labs
• 10 hrs projects

The student will obtain the basic orientation in discrete mathematics and linear algebra, and an abitity of an orientation in related mathematical structures.

The modern conception of the subject yields a fundamental mathematical knowledge which is necessary for a number of related courses. The student will be acquainted with basic facts and knowledge from the set theory, topology and especially the discrete mathematics with focus on the mathematical structures applicable in computer science.

Secondary school mathematics.

• Demlová M., Nagy J., Algebra, SNTL, Praha 1982.
• Havel, V., Holenda, J., Lineární algebra, STNL, Praha 1984.
• Jablonskij, S.V., Úvod do diskrétnej matematiky, Alfa, Bratislava, 1984.
• Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha 1989.
• Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000.
• Peregrin J., Logika a logiky, Academia, Praha 2004.
• Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982.

• Anderson I., A First Course in Discrete Mathematics, Springer-Verlag, London 2001.
• Acharjya D. P., Sreekumar, Fundamental Approach to Discrete Mathematics, New Age International Publishers, New Delhi, 2005.
• Faure R., Heurgon E., Uspořádání a Booloeovy algebry, Academia, Praha 1984.
• Gantmacher, F. R., The Theory of Matrices, Chelsea Publ. Comp., New York, 1960.
• Garnier R.,  Taylor J., Discrete Mathematics for New Technology, Institute of Physics Publishing, Bristol and Philadelphia 2002.
• Gratzer G., General Lattice Theory, Birkhauser Verlag, Berlin 2003.
• Grimaldi R. P., Discrete and Combinatorial Mathematics, Pearson Addison Valley, Boston 2004.
• Grossman P., Discrete mathematics for computing, Palgrave Macmillan, New York 2002.
• Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984.
• Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha 1989.
• Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992.
• Kolman B., Elementary Linear Algebra, Macmillan Publ. Comp., New York 1986.
• Kolman B., Introductory Linear Algebra, Macmillan Publ. Comp., New York 1993.
• Kolman B., Busby R. C., Ross S. C., Discrete Mathematical Structures, Pearson Education, Hong-Kong 2001.
• Klazar M., Kratochvíl J, Loebl M., Matoušek J. Thomas R., Valtr P., Topics in Discrete Mathematics, Springer-Verlag, Berlin 2006.
• Kučera, L., Kombinatorické algoritmy, SNTL, Praha 1983.
• Lipschutz, S., Lipson, M.L., Theory and Problems of Discrete Mathematics, McGraw-Hill, New York, 1997.
• Lovász L., Pelikán J., Vesztergombi, Discrete Mathematics, Springer-Verlag, New York 2003.
• Mannucci M. A., Yanofsky N. S., Quantum Computing For Computer Scientists, Cambridge University Press, Cambridge 2008.
• Mathews, K., Elementary Linear Algebra, University of Queensland, AU, 1991.
• Matoušek J., Nešetřil J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2000.
• Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, Oxford 2008.
• Nahara M., Ohmi T., Qauntum Computing: From Linear Algebra to Physical Realizations, CRC Press, Boca Raton 2008.
• O'Donnell, J., Hall C., Page R., Discrete Mathematics Using a Computer, Springer-Verlag, London 2006.
• Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982.
• Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
• Rosen, K. H. et al., Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton 2000.
• Ross, S. M. Topics in Finite and Discrete Mathematics, Cambridge University Press, Cambridge 2000.
• Sochor, A., Klasická matematická logika, Karolinum, Praha 2001.
• Švejdar, V., Logika, neúplnost, složitost a nutnost, Academia, Praha 2002.
• Vickers S., Topology via Logic, Cambridge University Press, Cambridge 1990.

1. A set intuitively. Basic set operations. The power set. The set of numbers. Binary relations. A mapping as a binary relation. Domain and co-domain. Functions and sequences. The composition of relations.
2. Injective, surjective and bijective mappings. The inverse mapping. The image and the inverse image. Important collections of sets with applications. Topological definition of continuity.
3. Operations on a set. Classification of the structures with one and two operations. The group of permutations of a finite set. Cominatorial properties of finite sets. The Principle of inclusion and exclusion.
4. Reflective, symetric, antisymetric and transitive binary relations. Reflective, symetric and transitive closure. Equivalences and partitions with examples.
5. The partially ordered sets. Lattices and their basic properties. Khalimsky's digital line and its order of specialization. The natural order of the real numbers. The Hasse diagrams. The lattice as a set with two binary operations. The Boolean algebra.
6. The basic properties of Boolean algebras. The duality and the set representation of a finite Boolean algebra.
7. Predicates, formulas, quantifiers and basic logical connectives. The proposional calculus and its syntaxis. The classification of formulas. Some subclasses of the proposional calculus.
8. The nterpretation of formulas. Tautologies,non-performable formulas and the logic equivalence of formulas. The structure of the algebra of non-equivalent formulas.
9. Prenex normal forms of formulas. The truthfulness and determinism.
10. Deduction systems. The system of the natural deduction and its rules. The proof in the system of natural deduction. The techniques of proofs.
11. The elementary notions of the graph theory. The Shortest path algorithm. The connectivity of graphs. The subgraphs.
12. The isomorphism and the homeomorphism of graphs. The Planarity problém.
13. The trees and the spanning trees and their properties. The searching of the binary tree. Selected searching algorithms.

• Practising and modelling of selected items of lectures.

Practising and modelling of selected items of lectures 8, 9 and 10.

Study evaluation is based on marks obtained for specified items. Minimimum number of marks to pass is 50.

Pass out the practices.