Course details

# Mathematical Structures in Computer Science

MAT Acad. year 2017/2018 Winter semester 5 credits

Guarantor

Language of instruction

Completion

Time span

Assessment points

Department

Lecturer

Instructor

Hrdina Jaroslav, doc. Mgr., Ph.D. (DADM FME BUT)

Šlapal Josef, prof. RNDr., CSc. (DADM FME BUT)

Subject specific learning outcomes and competences

Learning objectives

Study literature

- Birkhoff, G., MacLane, S.: Aplikovaná algebra, Alfa, Bratislava, 1981
- Procházka, L.: Algebra, Academia, Praha, 1990
- Lang, S.: Undergraduate Algebra, Springer-Verlag, 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, Springer-Verlag, Berlin - Heidelberg - New York, 1971, Algebra I. ISBN 0387406247, Algebra II. ISBN 0387406255
- Nerode, A., Shore, R.A.: Logic for Applications, Springer-Verlag, 1993, ISBN 0387941290

Fundamental literature

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

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 basic types: groupoids, semigroups, monoids, groups, rings, integral domains, fields, lattices and Boolean lattices.
- Basic algebraic methods: subalgebras, homomorphisms and isomorphisms, congruences and direct products of algebras.
- Congruences on groups and rings, normal subgroups and ideals.
- Polynomial rings, divisibility in integral domains, Gauss and Eucledian rings.
- Field theory: minimal fields, extension of fields, 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 Floyd-Warshall's algorithms).
- Networks, flows and cuts in networks, maximal flow and minimal cut problems, circulation in networks.

Progress assessment

Course inclusion in study plans