Faculty of Information Technology, BUT

Course details

Mathematical Structures in Computer Science

MAT Acad. year 2008/2009 Winter semester 5 credits

Formal theories, predicate logic, intuitionistic, modal and temporal logics, algebraic structures with one and with two binary operations, universal algebras, topological and metric spaces, Banach and Hilbert spaces, undirected graphs, directed graphs and networks.

Guarantor

Language of instruction

Czech

Completion

Examination (written)

Time span

39 hrs lectures, 13 hrs exercises

Assessment points

80 exam, 20 half-term test

Department

DADM FME BUT

Lecturer

Subject specific learning outcomes and competences

The students will improve their knowledge of the basic algebraic structures employed in informatics. It will enable them to understand better the theoretical foundations of informatics and to take an active part in the research work in the field.

Learning objectives

The aim of the subject is to improve the student's knowlende of the basic mathematical structures that are often utilized in different branches of informatics. In addition to the classical algebraic structures there will be discussed also foundations of the mathematical logic, the theory of Banach and Hilbert spaces, and the graph theory.

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 types, subalgebras and homomorphisms, congruences and factoralgebras, products, terms and free algebras.
  • Groupoids, semigroups, subgroupoids, homomorphisms, factorgroupoids and free semigroups.
  • Groups, subgroups and homomorphisms, factorgroups and cyclic groups, free and permutation groups.
  • Rings, homomorphisms, ideals, factorrings, fields.
  • Polynomial rings, integral domains and divisibility, 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, circilation in networks.

Progress assessment

Middle-semester written test.

Course inclusion in study plans

Back to top