Course detail

Mathematical Structures in Computer Science

FIT-MATAcad. year: 2023/2024

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

Czech

Number of ECTS credits

5

Mode of study

Not applicable.

Guarantor

prof. RNDr. Josef Šlapal, CSc.

Department

Dept. of Algebra and Discrete Mathematics (ÚM OAAG)

Entry knowledge

Not applicable.

Rules for evaluation and completion of the course

Middle-semester written test.

Aims

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.
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.

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Not applicable.

Recommended literature

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
Nerode, A., Shore, R.A.: Logic for Applications, Springer-Verlag, 1993, ISBN 0387941290
Cameron, P.J.: Sets, Logic and Categories, Springer-Verlag, 2000, ISBN 1852330562

Birkhoff, G., MacLane, S.: Aplikovaná algebra, Alfa, Bratislava, 1981
Mendelson, E.: Introduction to Mathematical Logic, Chapman Hall, 1997, ISBN 0412808307

Classification of course in study plans

  • Programme IT-MSC-2 Master's

    branch MBS , 1 year of study, winter semester, compulsory
    branch MPV , 1 year of study, winter semester, compulsory
    branch MIS , 1 year of study, winter semester, compulsory
    branch MIN , 1 year of study, winter semester, compulsory
    branch MGM , 1 year of study, winter semester, compulsory
    branch MBI , 1 year of study, winter semester, compulsory
    branch MSK , 1 year of study, winter semester, compulsory
    branch MMM , 1 year of study, winter semester, compulsory

  • Programme MITAI Master's

    specialization NSPE , 0 year of study, winter semester, elective
    specialization NBIO , 0 year of study, winter semester, elective
    specialization NSEN , 0 year of study, winter semester, elective
    specialization NVIZ , 0 year of study, winter semester, elective
    specialization NGRI , 0 year of study, winter semester, elective
    specialization NADE , 0 year of study, winter semester, elective
    specialization NISD , 0 year of study, winter semester, elective
    specialization NMAT , 0 year of study, winter semester, elective
    specialization NSEC , 0 year of study, winter semester, elective
    specialization NISY up to 2020/21 , 0 year of study, winter semester, elective
    specialization NCPS , 0 year of study, winter semester, elective
    specialization NHPC , 0 year of study, winter semester, elective
    specialization NNET , 0 year of study, winter semester, elective
    specialization NMAL , 0 year of study, winter semester, elective
    specialization NVER , 0 year of study, winter semester, elective
    specialization NIDE , 0 year of study, winter semester, elective
    specialization NEMB , 0 year of study, winter semester, elective
    specialization NISY , 0 year of study, winter semester, elective
    specialization NEMB up to 2021/22 , 0 year of study, winter semester, elective

Type of course unit

 

Lecture

39 hod., optionally

Teacher / Lecturer

prof. RNDr. Josef Šlapal, CSc.

Syllabus

  1. Propositional logic, formulas and their truth, formal system of propositional logic, provability, completeness theorem. 
  2. Language of predicate logic (predicates, kvantifiers, terms, formulas) and its realization, truth and validity of formulas.
  3. Formal system of 1st order predicate logic, correctness, completeness and compactness theorems, prenex  form of formulas.
  4. Universal algebras and their basic types: groupoids, semigroups, monoids, groups, rings, integral domains, fields, lattices and Boolean lattices.
  5. Basic algebraic methods: subalgebras, homomorphisms and isomorphisms, congruences and direct products of algebras.
  6. Congruences on groups and rings, normal subgroups and ideals.
  7. Polynomial rings, divisibility in integral domains, Gauss and Eucledian rings.
  8. Field theory: minimal fields, extension of fields, finite fields. 
  9. Metric spaces, completeness, normed and Banach spaces.
  10. Unitar and Hilbert spaces, orthogonality, closed orthonormal systems and Fourier series.
  11. Trees and spanning trees, minimal spanning trees (the Kruskal's and Prim's algorithms), vertex and edge colouring.
  12. Directed graphs, directed Eulerian graphs, networks, the critical path problem (Dijkstra's and Floyd-Warshall's algorithms).
  13. Networks, flows and cuts in networks, maximal flow and minimal cut problems, circulation in networks.

Fundamentals seminar

13 hod., compulsory

Teacher / Lecturer

prof. RNDr. Josef Šlapal, CSc.