Title:  Mathematical Structures in Computer Science 

Code:  MAT 

Ac.Year:  2009/2010 

Term:  Winter 

Curriculums:  

Language:  Czech 

Credits:  5 

Completion:  examination (written) 

Type of instruction:  Hour/sem  Lectures  Sem. Exercises  Lab. exercises  Comp. exercises  Other 

Hours:  39  13  0  0  0 

 Examination  Tests  Exercises  Laboratories  Other 

Points:  80  20  0  0  0 



Guarantee:  Šlapal Josef, prof. RNDr., CSc., DADM 

Faculty:  Faculty of Mechanical Engineering BUT 

Department:  Department of Algebra and Discrete Mathematics FME BUT 

 Learning objectives: 

The aim of the subject is to improve the students' knowledge of the basic mathematical structures that are often utilized in different branches of informatics. In addition to the classical algebraic structures also foundations will be discussed of the mathematical logic, the theory of Banach and Hilbert spaces, and the graph theory.  Description: 

Formal theories, predicate logic, intuitionistic, modal and temporal logics, algebraic structures with one and with two binary operations, universal algebras, topological and metric spaces, Banach and Hilbert spaces, undirected graphs, directed graphs and networks.  Learning outcomes and competences: 

The students will improve their knowledge of the basic algebraic structures employed in informatics. This will enable them to better understand the theoretical foundations of informatics and conduct research work in the field.  Syllabus of lectures: 

 Propositional logic, formulas and their truth, formal system of propositional logic, provability, completeness theorem.
 Language of predicate logic (predicates, kvantifiers, terms, formulas) and its realization, truth and validity of formulas.
 Formal system of 1st order predicate logic, correctness, completeness and compactness theorems, prenex form of formulas.
 Universal algebras and their types, subalgebras and homomorphisms, congruences and factoralgebras, products, terms and free algebras.
 Groupoids, semigroups, subgroupoids, homomorphisms, factorgroupoids and free semigroups.
 Groups, subgroups and homomorphisms, factorgroups and cyclic groups, free and permutation groups.
 Rings, homomorphisms, ideals, factorrings, fields.
 Polynomial rings, integral domains and divisibility, finite fields.
 Metric spaces, completeness, normed and Banach spaces.
 Unitar and Hilbert spaces, orthogonality, closed orthonormal systems and Fourier series.
 Trees and spanning trees, minimal spanning trees (the Kruskal's and Prim's algorithms), vertex and edge colouring.
 Directed graphs, directed Eulerian graphs, networks, the critical path problem (Dijkstra's and FloydWarshall's algorithms).
 Networks, flows and cuts in networks, maximal flow and minimal cut problems, circulation in networks.
 Fundamental literature: 

 Mendelson, M.: Introduction to Mathematical Logic, Chapman Hall, 1997, ISBN 0412808307
 Cameron, P.J.: Sets, Logic and Categories, SpringerVerlag, 2000, ISBN 1852330562
 Biggs, N.L.: Discrete Mathematics, Oxford Science Publications, 1999, ISBN 0198534272
 Study literature: 

 Birkhoff, G., MacLane, S.: Aplikovaná algebra, Alfa, Bratislava, 1981
 Procházka, L.: Algebra, Academia, Praha, 1990
 Lang, S.: Undergraduate Algebra, SpringerVerlag, New York  Berlin  Heidelberg, 1990, ISBN 038797279
 Polimeni, A.D., Straight, H.J.: Foundations of Discrete Mathematics, Brooks/Cole Publ. Comp., Pacific Grove, 1990, ISBN 053412402X
 Shoham, Y.: Reasoning about Change, MIT Press, Cambridge, 1988, ISBN 0262192691
 Van der Waerden, B.L.: Algebra I,II, SpringerVerlag, Berlin  Heidelberg  New York, 1971, Algebra I. ISBN 0387406247, Algebra II. ISBN 0387406255
 Nerode, A., Shore, R.A.: Logic for Applications, SpringerVerlag, 1993, ISBN 0387941290
 Progress assessment: 

Middlesemester written test.  
