Title:

Mathematical Structures in Computer Science

Code:MAT
Ac.Year:2014/2015
Sem:Winter
Curriculums:
ProgrammeField/
Specialization
YearDuty
IT-MSC-2MBI1stCompulsory
IT-MSC-2MBS1stCompulsory
IT-MSC-2MGM1stCompulsory
IT-MSC-2MIN1stCompulsory
IT-MSC-2MIS1stCompulsory
IT-MSC-2MMI1stCompulsory
IT-MSC-2MMM1stCompulsory
IT-MSC-2MPV1stCompulsory
IT-MSC-2MSK1stCompulsory
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)
Lecturer:Šlapal Josef, prof. RNDr., CSc. (DADM)
Instructor:Hrdina Jaroslav, doc. Mgr., Ph.D. (DADM)
Šlapal Josef, prof. RNDr., CSc. (DADM)
Faculty:Faculty of Mechanical Engineering BUT
Department:Department of Algebra and Discrete Mathematics FME BUT
 
Learning objectives:
  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.
Description:
  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.
Learning outcomes and competencies:
  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.
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, field theory, finite (Galois) fields.
  • Metric spaces, completeness, normed and Banach spaces.
  • Unitar and Hilbert spaces, orthogonality, closed orthonormal systems and Fourier series.
  • Simple graphs, connectedness, trees and spanning trees, minimal spanning trees (the Kruskal's and Prim's algorithms).
  • Eulerian and Hamiltonian graphs, colouring, planarity.
  • Directed graphs, directed Eulerian and Hamiltonian graphs, tournaments, the critical path problem (Dijkstra's and Floyd-Warshall's algorithms).
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
  • Štěpánek, P.: Predikátová logika, MFF UK Praha, 2000 (učební text)
  • Kolmogorov, A.N., Fomin, S.V.: Elements of the Theory of Functions anf Functional Analysis, Dover Publishers, 1999, ISBN: 0486406830 
  • Nešetřil J., Teorie grafů, SNTL, 1978 
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
  • Bondy J.A, Murty U.S.R, Graph Theory with Applications, North Holland, New York-Amsterdam-Oxford, 1979, ISBN 0444194517 
Progress assessment:
  Middle-semester written test.
 

Your IPv4 address: 52.200.130.163
Switch to https