Course details

# Mathematical Structures in Computer Science (in English)

MATe Acad. year 2022/2023 Winter semester 5 credits

Formal theories, propositional logic, predicate logic, universal algebra, algebraic structures with one and with two binary operations, topological and metric spaces, Banach and Hilbert spaces, undirected graphs, directed graphs and networks.

Guarantor

Course coordinator

Language of instruction

Completion

Time span

- 39 hrs lectures
- 13 hrs exercises

Assessment points

- 80 pts final exam
- 20 pts mid-term test

Department

Lecturer

Instructor

Subject specific learning outcomes and competences

The students will improve their knowledge of the algebraic structures that are most often employed in informatics. These will be mathematical logic, algebra, functional alalysis and graph theory. This will enable them to better understand the theoretical foundations of informatics and also conduct research work in the field.

Learning objectives

The aim of the subject is to improve the students' knowlende of the basic mathematical structures that are often utilized in different branches of informatics. In addition to universal algebra and the classical algebraic structures, foundations will be discussed of the mathematical logic, the theory of Banach and Hilbert spaces, and the theory of both udirected and directed graphs.

Study literature

- 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
- Lang, S.: Undergraduate Algebra, Springer-Verlag, New York , 2005, ISBN 978-0-387-22025-3
- Farenick, D.: Fundamentals of Functional Analysis, Springer-Verlag, 2016, ISBN 978-3-319-45633-1
- Nerode, A., Shore, R.A.: Logic for Applications, 2nd. ed., Springer-Verlag, 1997, ISBN 978-0-387-94893-5

Fundamental literature

- Mendelson, E.: Introduction to Mathematical Logic, Chapman and Hall/CRC, 2015, ISBN 9781482237726
- Biggs, N.L.: Discrete Mathematics, 2nd ed., Oxford University Press, 2003, ISBN 978-0198507185
- Robinson, J.C.: An Introduction to Functional Analysis, Cambridge University Press, 2020, ISBN 9781139030267

Syllabus of lectures

- Propositional logic, formulas and their truth, formal system of propositional logic, provability, completeness theorem.
- Language of predicate logic (predicates, quantifiers, 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 Euclidean 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.

Syllabus of numerical exercises

- 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

- Mid-term written test - 20 points.
- Final exam - 80 points.

Course inclusion in study plans

- Programme IT-MGR-2 (in English), field MGMe, 1st year of study, Compulsory
- Programme MIT-EN (in English), 1st year of study, Compulsory