Title:

Mathematical Structures in Computer Science

Code:MAT
Ac.Year:2007/2008
Sem:Winter
Curriculums:
ProgrammeField/
Specialization
YearDuty
IT-MSC-2MGM.1stCompulsory
IT-MSC-2MIN.1stCompulsory
IT-MSC-2MIS.1stCompulsory
IT-MSC-2MPS1stCompulsory
Language of Instruction:Czech
Credits:5
Completion:examination (written)
Type of
instruction:
Hour/semLecturesSeminar
Exercises
Laboratory
Exercises
Computer
Exercises
Other
Hours:3913000
ExamsTestsExercisesLaboratoriesOther
Points:8020000
Guarantor:Šlapal Josef, prof. RNDr., CSc. (DADM)
Faculty:Faculty of Mechanical Engineering BUT

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. An introduction to the category theory will be dealt with too.
Description:
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, basic concepts of the category theory.
Learning outcomes and competencies:
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.
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.
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
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
Progress assessment:
Test during the semester and submission of homework.