Course detail
Mathematical Structures in Computer Science
FIT-MATAcad. year: 2020/2021
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.
Guarantor
Learning outcomes of the course unit
Prerequisites
Co-requisites
Recommended optional programme components
Literature
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
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
Planned learning activities and teaching methods
Assesment methods and criteria linked to learning outcomes
Language of instruction
Work placements
Aims
Classification of course in study plans
- Programme MITAI Master's
specialization NADE , any year of study, winter semester, 5 credits, elective
specialization NBIO , any year of study, winter semester, 5 credits, elective
specialization NGRI , any year of study, winter semester, 5 credits, elective
specialization NNET , any year of study, winter semester, 5 credits, elective
specialization NVIZ , any year of study, winter semester, 5 credits, elective
specialization NCPS , any year of study, winter semester, 5 credits, elective
specialization NSEC , any year of study, winter semester, 5 credits, elective
specialization NEMB , any year of study, winter semester, 5 credits, elective
specialization NHPC , any year of study, winter semester, 5 credits, elective
specialization NISD , any year of study, winter semester, 5 credits, elective
specialization NIDE , any year of study, winter semester, 5 credits, elective
specialization NISY , any year of study, winter semester, 5 credits, elective
specialization NMAL , any year of study, winter semester, 5 credits, elective
specialization NMAT , any year of study, winter semester, 5 credits, elective
specialization NSEN , any year of study, winter semester, 5 credits, elective
specialization NVER , any year of study, winter semester, 5 credits, elective
specialization NSPE , any year of study, winter semester, 5 credits, elective - Programme IT-MGR-2 Master's
branch MBI , 1. year of study, winter semester, 5 credits, compulsory
branch MPV , 1. year of study, winter semester, 5 credits, compulsory
branch MGM , 1. year of study, winter semester, 5 credits, compulsory
branch MSK , 1. year of study, winter semester, 5 credits, compulsory
branch MIS , 1. year of study, winter semester, 5 credits, compulsory
branch MBS , 1. year of study, winter semester, 5 credits, compulsory
branch MIN , 1. year of study, winter semester, 5 credits, compulsory
branch MMI , 1. year of study, winter semester, 5 credits, compulsory
branch MMM , 1. year of study, winter semester, 5 credits, compulsory
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, 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, a minimum spanning tree (the Kruskal's and Prim's algorithms), vertex and edge colouring.
- Eulerian and Hamiltonian graphs, vertex coloring, planarity.
- Directed graphs, directed Eulerian graphs, a minimum length path (Dijkstra's and Floyd-Warshall's algorithms).
Fundamentals seminar
Teacher / Lecturer