Course detail
Mathematical Structures in Computer Science (in English)
FIT-MATeAcad. year: 2022/2023
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.
Language of instruction
Number of ECTS credits
Mode of study
Guarantor
Learning outcomes of the course unit
Prerequisites
Co-requisites
Planned learning activities and teaching methods
Assesment methods and criteria linked to learning outcomes
- Mid-term written test - 20 points.
- Final exam - 80 points.
Course curriculum
Work placements
Aims
Specification of controlled education, way of implementation and compensation for absences
Recommended optional programme components
Prerequisites and corequisites
Basic literature
Mendelson, E.: Introduction to Mathematical Logic, Chapman and Hall/CRC, 2015, ISBN 9781482237726 (EN)
Robinson, J.C.: An Introduction to Functional Analysis, Cambridge University Press, 2020, ISBN 9781139030267 (EN)
Recommended reading
Lang, S.: Undergraduate Algebra, Springer-Verlag, New York , 2005, ISBN 978-0-387-22025-3 (EN)
Nerode, A., Shore, R.A.: Logic for Applications, 2nd. ed., Springer-Verlag, 1997, ISBN 978-0-387-94893-5 (EN)
Shoham, Y.: Reasoning about Change, MIT Press, Cambridge, 1988, ISBN 0262192691 (EN)
Van der Waerden, B.L.: Algebra I, II, Springer-Verlag, Berlin - Heidelberg - New York, 1971, Algebra I. ISBN 0387406247, Algebra II. ISBN 0387406255 (EN)
Classification of course in study plans
Type of course unit
Lecture
Teacher / Lecturer
Syllabus
- 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.
Fundamentals seminar
Teacher / Lecturer
Syllabus
- 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.