Title:  Discrete Mathematics 

Code:  IDA 

Ac.Year:  2010/2011 

Term:  Winter 

Curriculums:  

Language of Instruction:  Czech 

Credits:  7 

Completion:  examination (written) 

Type of instruction:  Hour/sem  Lectures  Seminar Exercises  Laboratory Exercises  Computer Exercises  Other 

Hours:  39  12  0  4  10 

 Exams  Tests  Exercises  Laboratories  Other 

Points:  60  0  10  0  30 



Guarantor:  Kovár Martin, doc. RNDr., Ph.D. (DMAT) 

Lecturer:  Durnová Helena, Mgr., Ph.D. (DMAT) Fajmon Břetislav, RNDr., Ph.D. (DMAT) Kovár Martin, doc. RNDr., Ph.D. (DMAT) 
Instructor:  Durnová Helena, Mgr., Ph.D. (DMAT) Fajmon Břetislav, RNDr., Ph.D. (DMAT) Vítovec Jiří, Mgr., Ph.D. (DMAT) 

Faculty:  Faculty of Electrical Engineering and Communication BUT 

Department:  Department of Mathematics FEEC BUT 

Followups:  

 Learning objectives: 

  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.  Description: 

  The sets, relations and mappings. The topology and the continuous mapping. The structures with one and two operations. Equivalences and partitions. Posets. Lattices and Boolean algebras.The proposional calculus. The normal forms of formulas. Deduction. The proving techniques. The elementary notions of the graph theory. Connectedness. Subgraphs and morphisms of graphs. Planarity. Trees and their properties. Simple graph algorithms.  Knowledge and skills required for the course: 

  Secondary school mathematics.  Learning outcomes and competences: 

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


 A set intuitively. Basic set operations. The power set. The set of numbers. Binary relations. A mapping as a binary relation. Domain and codomain. Functions and sequences. The composition of relations.
 Injective, surjective and bijective mappings. The inverse mapping. The image and the inverse image. Important collections of sets with applications. Topological definition of continuity.
 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.
 Reflective, symetric, antisymetric and transitive binary relations. Reflective, symetric and transitive closure. Equivalences and partitions with examples.
 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.
 The basic properties of Boolean algebras. The duality and the set representation of a finite Boolean algebra.
 Predicates, formulas, quantifiers and basic logical connectives. The proposional calculus and its syntaxis. The classification of formulas. Some subclasses of the proposional calculus.
 The nterpretation of formulas. Tautologies,nonperformable formulas and the logic equivalence of formulas. The structure of the algebra of nonequivalent formulas.
 Prenex normal forms of formulas. The truthfulness and determinism.
 Deduction systems. The system of the natural deduction and its rules. The proof in the system of natural deduction. The techniques of proofs.
 The elementary notions of the graph theory. The Shortest path algorithm. The connectivity of graphs. The subgraphs.
 The isomorphism and the homeomorphism of graphs. The Planarity problém.
 The trees and the spanning trees and their properties. The searching of the binary tree. Selected searching algorithms.
 Syllabus of numerical exercises: 

  Practising and modelling of selected items of lectures.
 Syllabus of computer exercises: 

 Practising and modelling of selected items of lectures 8, 9 and 10.  Syllabus  others, projects and individual work of students: 

 Five individual hometasks/works  an instructor will inform.  Fundamental literature: 


 Johnsonbaugh, R., Discrete mathematics, Macmillan Publ. Comp., New York, 1984.
 Jablonskij, S.V., Úvod do diskrétnej matematiky, Alfa, Bratislava, 1984 (in Slovak).
 Kolář, J., Štěpánková, O., Chytil, M., Logika, algebry a grafy, STNL, Praha 1989 (in Czech).
 Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992 (in Slovak).
 Kučera, L., Kombinatorické algoritmy, SNTL, Praha 1983 (in Czech).
 Lipschutz, S., Lipson, M.L., 2000 Solved Problems in Discrete Mathematics, McGrawHill, New York, 1992.
 Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982 (in Slovak).
 Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
 Štěpán, J., Diskrétní matematika, UP, Olomouc, 1990 (skriptum) (in Czech).
 Mathews, K., Elementary Linear Algebra, University of Queensland, AU, 1991.
 Anton, H., Elementary Linear Algebra, John Wiley, New York, 1984.
 Demlová, M., Nagy, J., Algebra, STNL, Praha, 1982.
 Gantmacher, F. R., The Theory of Matrices, Chelsea Publ. Comp., New York, 1960.
 Study literature: 


 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 (in Czech).
 Kolibiar, M. a kol., Algebra a príbuzné disciplíny, Alfa, Bratislava, 1992 (in Slovak).
 Lipschutz, S., Lipson M.L., 2000 Solved Problems in Discrete Mathematics, McGrawHill, New York, 1992.
 Preparata, F.P., Yeh, R.T., Úvod do teórie diskrétnych štruktúr, Alfa, Bratislava, 1982 (in Slovak).
 Rosen, K.H., Discrete Mathematics and its Applications, AT & T Information systems, New York 1988.
 Štěpán, J., Diskrétní matematika, UP, Olomouc, 1990 (skriptum) (in Czech).
 Demlová, M., Nagy, J., Algebra, STNL, Praha 1982 (in Czech).
 Havel, V., Holenda, J., Lineární algebra, STNL, Praha 1984 (in Czech).
 Hrůza, B., Mrhačová, H., Cvičení z lineární algebry, PCDir, Brno 1984 (in Czech).
 Controlled instruction: 

  Pass out the practices.  Progress assessment: 

  Pass out the practices in the prescribed range.  
