Title:

Mathematical Structures in Computer Science

Code:MAT
Ac.Year:2017/2018
Term:Winter
Curriculums:
ProgrammeBranchYearDuty
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:Czech
Credits:5
Completion:examination (written)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:3913000
 ExaminationTestsExercisesLaboratoriesOther
Points:8020000
Guarantee:Šlapal Josef, prof. RNDr., CSc., DADM
Lecturer:Šlapal Josef, prof. RNDr., CSc., DADM
Instructor:Duránik Lukáš, DEAN
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
Schedule:
DayLessonWeekRoomStartEndLect.Gr.St.G.EndG.
MonlecturelecturesD10516:0017:501MIT10 MBI10 MBI
MonlecturelecturesD020616:0017:501MIT10 MBI10 MBI
MonlecturelecturesD020716:0017:501MIT10 MBI10 MBI
MonlecturelecturesD10516:0017:501MIT11 MBS11 MBS
MonlecturelecturesD020616:0017:501MIT11 MBS11 MBS
MonlecturelecturesD020716:0017:501MIT11 MBS11 MBS
MonlecturelecturesD10516:0017:501MIT12 MGM12 MGM
MonlecturelecturesD020616:0017:501MIT12 MGM12 MGM
MonlecturelecturesD020716:0017:501MIT12 MGM12 MGM
MonlecturelecturesD10516:0017:501MIT13 MIN13 MIN
MonlecturelecturesD020616:0017:501MIT13 MIN13 MIN
MonlecturelecturesD020716:0017:501MIT13 MIN13 MIN
MonlecturelecturesD10516:0017:501MIT14 MIS14 MIS
MonlecturelecturesD020616:0017:501MIT14 MIS14 MIS
MonlecturelecturesD020716:0017:501MIT14 MIS14 MIS
MonlecturelecturesD10516:0017:501MIT15 MMI15 MMI
MonlecturelecturesD020616:0017:501MIT15 MMI15 MMI
MonlecturelecturesD020716:0017:501MIT15 MMI15 MMI
MonlecturelecturesD10516:0017:501MIT16 MMM16 MMM
MonlecturelecturesD020616:0017:501MIT16 MMM16 MMM
MonlecturelecturesD020716:0017:501MIT16 MMM16 MMM
MonlecturelecturesD10516:0017:501MIT17 MPV17 MPV
MonlecturelecturesD020616:0017:501MIT17 MPV17 MPV
MonlecturelecturesD020716:0017:501MIT17 MPV17 MPV
MonlecturelecturesD10516:0017:501MIT18 MSK18 MSK
MonlecturelecturesD020616:0017:501MIT18 MSK18 MSK
MonlecturelecturesD020716:0017:501MIT18 MSK18 MSK
MonlecturelecturesD10516:0017:502MITxxxx
WedlecturelecturesD10516:0016:501MIT10 MBI10 MBI
WedlecturelecturesD020616:0016:501MIT10 MBI10 MBI
WedlecturelecturesD020716:0016:501MIT10 MBI10 MBI
WedlecturelecturesD10516:0016:501MIT11 MBS11 MBS
WedlecturelecturesD020616:0016:501MIT11 MBS11 MBS
WedlecturelecturesD020716:0016:501MIT11 MBS11 MBS
WedlecturelecturesD10516:0016:501MIT12 MGM12 MGM
WedlecturelecturesD020616:0016:501MIT12 MGM12 MGM
WedlecturelecturesD020716:0016:501MIT12 MGM12 MGM
WedlecturelecturesD10516:0016:501MIT13 MIN13 MIN
WedlecturelecturesD020616:0016:501MIT13 MIN13 MIN
WedlecturelecturesD020716:0016:501MIT13 MIN13 MIN
WedlecturelecturesD10516:0016:501MIT14 MIS14 MIS
WedlecturelecturesD020616:0016:501MIT14 MIS14 MIS
WedlecturelecturesD020716:0016:501MIT14 MIS14 MIS
WedlecturelecturesD10516:0016:501MIT15 MMI15 MMI
WedlecturelecturesD020616:0016:501MIT15 MMI15 MMI
WedlecturelecturesD020716:0016:501MIT15 MMI15 MMI
WedlecturelecturesD10516:0016:501MIT16 MMM16 MMM
WedlecturelecturesD020616:0016:501MIT16 MMM16 MMM
WedlecturelecturesD020716:0016:501MIT16 MMM16 MMM
WedlecturelecturesD10516:0016:501MIT17 MPV17 MPV
WedlecturelecturesD020616:0016:501MIT17 MPV17 MPV
WedlecturelecturesD020716:0016:501MIT17 MPV17 MPV
WedlecturelecturesD10516:0016:501MIT18 MSK18 MSK
WedlecturelecturesD020616:0016:501MIT18 MSK18 MSK
WedlecturelecturesD020716:0016:501MIT18 MSK18 MSK
WedlecturelecturesD10516:0016:502MITxxxx
WedexerciselecturesD10517:0017:501MIT10 MBI10 MBI
WedexerciselecturesD020617:0017:501MIT10 MBI10 MBI
WedexerciselecturesD020717:0017:501MIT10 MBI10 MBI
WedexerciselecturesD10517:0017:501MIT11 MBS11 MBS
WedexerciselecturesD020617:0017:501MIT11 MBS11 MBS
WedexerciselecturesD020717:0017:501MIT11 MBS11 MBS
WedexerciselecturesD10517:0017:501MIT12 MGM12 MGM
WedexerciselecturesD020617:0017:501MIT12 MGM12 MGM
WedexerciselecturesD020717:0017:501MIT12 MGM12 MGM
WedexerciselecturesD10517:0017:501MIT13 MIN13 MIN
WedexerciselecturesD020617:0017:501MIT13 MIN13 MIN
WedexerciselecturesD020717:0017:501MIT13 MIN13 MIN
WedexerciselecturesD10517:0017:501MIT14 MIS14 MIS
WedexerciselecturesD020617:0017:501MIT14 MIS14 MIS
WedexerciselecturesD020717:0017:501MIT14 MIS14 MIS
WedexerciselecturesD10517:0017:501MIT15 MMI15 MMI
WedexerciselecturesD020617:0017:501MIT15 MMI15 MMI
WedexerciselecturesD020717:0017:501MIT15 MMI15 MMI
WedexerciselecturesD10517:0017:501MIT16 MMM16 MMM
WedexerciselecturesD020617:0017:501MIT16 MMM16 MMM
WedexerciselecturesD020717:0017:501MIT16 MMM16 MMM
WedexerciselecturesD10517:0017:501MIT17 MPV17 MPV
WedexerciselecturesD020617:0017:501MIT17 MPV17 MPV
WedexerciselecturesD020717:0017:501MIT17 MPV17 MPV
WedexerciselecturesD10517:0017:501MIT18 MSK18 MSK
WedexerciselecturesD020617:0017:501MIT18 MSK18 MSK
WedexerciselecturesD020717:0017:501MIT18 MSK18 MSK
WedexerciselecturesD10517:0017:502MITxxxx
 
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 and networks.
Learning outcomes and competences:
  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 basic types: groupoids, semigroups, monoids, groups, rings, integral domains, fields, lattices and Boolean lattices.
  • Basic algebraic methods: subalgebras, homomorphisms and isomorphisms, congruences and direct products of algebras.
  • Congruences on groups and rings, normal subgroups and ideals.
  • Polynomial rings, divisibility in integral domains, Gauss and Eucledian rings.
  • Field theory: minimal fields, extension of fields, 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, circulation in networks.
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:
  Middle-semester written test.