Course details

# Mathematical Structures in Computer Science

MAT Acad. year 2006/2007 Winter semester 5 credits

Guarantor

Language of instruction

Completion

Time span

Assessment points

Lecturer

Subject specific learning outcomes and competences

Learning objectives

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

- Predicates, kvantifiers, terms, formulas, first-order language anf its interpretation, models of formulas.
- First-order predicate calculus and and its properties, completeness and compactness theorems, extensions of the theory.
- Prenex normal forms, skolemization and the Herbrand theorem, foundations of the intuitionistic, modal and temporal logics.
- Universal algebras and their types, subalgebras and homomorphisms, congruences and factoralgebras, products, terms and free algebras.
- Partial and manysorted algebras, hyperalgebras, grupoids, subgroupoids and homomorphisms, cartesian products, factorgroupoids and free groupoids.
- Semigroups and free semigroups, groups, subgroups and homomorphisms, factorgroups and cyclic groups, free and permutation groups.
- Rings, ideals, homomorphisms, integral rings and fields.
- Finite fields, polynomials and divisibility.
- Topological and 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), transportation networks, flows and cuts.
- Categories and concrete categories, subobjects, factorobjects and free objects, products and sums, functors and natural transformations.

Progress assessment

Course inclusion in study plans